큐의 정의와 성질

• 한쪽 끝에서 원소를 넣고 반대쪽에서 빼는 자료구조 (FIFO)

큐의 성질

• 원소의 추가 O(1) → rear
• 원소의 제거 O(1) → front
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 → STL queue에는 제공 되지 않음

큐의 구현

• dat[5] = {21, 30} 라고 가정

• head 첫번째 원소의 인덱스 (21)

• tail 마지막 원소의 다음 인덱스 (30의 다음 인덱스)

• 큐는 기본적으로 head와 tail이 뒤로 밀리면서 데이터를 꺼내오게 된다.

• ex) push() → dat[tail] = data; tail++;

• ex) pop() → data = dat[head] head++;

• 지속적으로 head와 tail이 밀리기 때문에 앞에 공간이 있음에도 불구하고 데이터를 새로 추가할 수 없다.

• tail이 끝인덱스까지 가게 되면 다시 0으로 되돌려서 이 문제를 해결할 수 있다. 이러한 형태의 개념을 원형 큐라고 한다.