Queue

1. 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 ADT
2. 먼저 들어간 Data가 먼저나오는(First in First out) 자료구조
3. 터널을 생각하면 쉽다

stack과의 차이

1. stack : Push Pop
2. queue : enqueue, dequeue

---

CircularQueue

문제점 2가지
1. 배열요소들의 이동으로 인한부하
2. 제거 연산을 수행할때마다 가용용량 ↓

모든 시작은 또 다른 시작의 끝으로부터 비롯된다.

해결방법
1. 시작과 끝을 연결
2. Dummy Node 이용하여 시작과 끝 사이를 비운다.

---

LinkedQueue

• 순환큐는 구현이 쉽지 않지만 사용하기는 쉽다.

• 순환큐는 큐의 용량을 사전에 알아야 한다.

• 링크드 큐는 이론적으로는 용량 제한이 없다. 즉 큐가 가득찬 상태인지 확인할 필요가 없다.

하지만 링크드 큐는 순환큐보다 느리다(노드를 생성하고 삭제하는데 malloc 필요)

연습문제

• 01
  후단의 위치가 [2]로 이동
• 02
  전단의 위치가 [5]로 이동
• 03
  전단의 위치와 후단의 위치가 동일한 것은 공백상태 이다.
  포화상태일때는 2가지 경우이다.

1. 전단이 후단보다 앞에 있는 경우
   전단이 배열의 첫번째 원소이고 후단이 배열의 마지막을 가리킴
2. 후단이 전단보다 앞에 있는 경우
   후단+1의 index가 전단과 동일

• 04
  1. 구현의 용이성: 순환큐의 경우 front와 rear이 배열에 끝에 다다랐을때 이를 어떻게 처리할 것 인지, 포화 상태와 공백 상태를 어떻게 구분할 것인지를 구현해야하지만 링크드큐는 노드를 연결하기만 하면 된다.
  2. 성능: 링크드큐는 노드를 생성할때마다 malloc을 해야된다. 순환큐는 배열에 노드를 추가하기 때문에 성능은 링크드큐보다 순환큐가 더 좋다