자료구조 스택_큐_링크드리스트
- 2. Linked List ? 노드가 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조. 노드 : 자기 자신의 값과 다음 노드를 가리키는 노드 포인터로 구성된다. 인덱스를 이용한 접근이 불가능하고 노드 포인터를 통해 다른 노드에 접근이 가능하다.
- 3. Linked List 장점 동적 자료구조로써 프로그램이 실행 중 메모리 할당이 가능하다. 노드의 삽입, 삭제 작업은 쉽게 이루어진다. 스택, 큐와 같은 선형 데이터 구조에서 쉽게 사용 된다. 단점 포인터가 별도의 저장 공간을 요구하기 때문에 더 많은 메모리를 사용하는 경향이 있다.
- 4. Linked List 종류 – 단순 연결 리스트 각 노드에 자료 공간과 한 개의 포인터 공간이 있다. 노드의 포인터는 다음 노드를 가리킨다.
- 5. Linked List 종류 – 이중 연결 리스트 단순 연결 리스트와 구조는 비슷하다. 포인터 공간이 2개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.
- 6. Linked List 종류 – 원형 연결 리스트 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결 시켜 원형으로 만든 구조
- 7. Stack ? 제한적으로 접근할 수 있는 자료구조 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 접근은 목록의 끝에서만 일어난다. (LIFO – Last In First Out) push pop
- 8. Stack Class Stack{ int top; // 스택의 가장 윗 데이터, 비어있다면 연산은 정의 불가능 void push(int); // 스택의 가장 윗 데이터, top 가리키는 자리에 메모리를 생성해 데이터를 넣는다. void pop(int); // 스택의 가장 윗 데이터를 내보내고 데이터를 삭제한다. Boolean isEmpty() // 스택이 비어있는지 여부를 판단한다. };
- 9. Queue ? 먼저 집어넣은 데이터가 먼저 나오는 구조, FIFO(First In First Out) 구조 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념 프린터 출력 처리, 윈도우 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시 간 순서대로 처리할 필요가 있는 상황에 이용된다. Front Rear
- 10. Queue Class Queue{ int front, rear; // 큐의 데이터 위치 void put(int); // 큐의 뒤에 자료를 넣는다. int get(); //큐의 앞에서 자료를 꺼낸다. } • Overflow = 큐가 꽉차서 더 이상 자료를 넣을 수 없는 경우 • Underflow = 큐가 비어 있어 자료를 꺼낼 수 없는 경우
- 11. Queue의 종류 – 선형 큐 배열을 선형으로 사용해 큐를 구현 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨 야 한다는 단점이 있다. Front Rear
- 12. Queue의 종류 – 원형 큐 배열을 원형으로 사용해 큐를 구현 항상 front는 비어있어야 한다. 삽입시 큐가 full 여부를 확인해야 한다. Front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식. Front Rear
- 13. Queue의 종류 – 링크드 큐 링크드 리스트로 구현한 큐, 연결리스트를 사용해 자료들을 연결 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는다. 필요에 따라 환형으로 만들 수 있다. 삽입과 삭제가 제한되지 않아 편리하다.