큐 & 원형 큐

정의

• 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 FIFO 구조를 가진다.
• 특정 위치에서만 원소를 넣거나 뺄 수 있다.

성질

1. 원소의 추가/제거 : O(1)
2. 제일 앞/뒤쪽의 원소 확인 : O(1)
3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하기 때문에 STL queue에서는 인덱스로 내부 원소에 접근하는 기능을 제공하지 않는다.

구현

배열을 이용하여 큐를 직접 구현해보자.

const int MX = 1000005;
int dat[MX]; // 원소 저장 배열
int head = 0, tail = 0; // 각각 큐의 앞쪽과 뒤쪽을 가리킬 변수

void push(int x) { dat[tail++]; }
void pop() { head++; }
int front() { return head; }
int back() { return dat[tail - 1]; }

// 배열 속 원소들을 가리키며 이동하면서 데이터를 변경/삭제하지 않고도 해당 기능을 구현할 수 있다.

• 원소가 추가/제거되는 곳을 각각 rear , front 라고 한다.
• head는 가장 앞에 있는 원소의 인덱스 이고 tail은 가장 뒤에 있는 원소의 인덱스 + 1 이다.
• 큐가 비어있을 때 front(), pop(), back() 연산 시 런타임 에러가 발생할 수 있다.

원형 큐

원형의 배열을 가정하고 구현한 큐

push과 pop 연산 시 dat 배열에서 (head와 tail이 가리키는) 큐의 원소들이 들어있는 장소가 점점 오른쪽으로 밀린다. 스택과 다르게, 큐는 선형 배열로 구현할 경우 삭제가 발생할 때마다 점점 오른쪽으로 밀려 앞쪽에 공간이 많음에도 새 원소를 추가할 수 없는 상황이 생긴다. 이를 해결하기 위해서는 큐의 원소가 들어갈 배열을 원형으로 만들면 된다.

• tail이 7인 상태에서 1이 더해지면 0번지로 다시 와서 가리키도록 한다.
• 위 상황에서 1이 더해지면 다시 0번지에 원소를 저장하도록 구현한다.
• head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 개수가 배열의 크기보다 커지지 않는 이상 문제 없다.
• STL queue를 사용하지 않고 직접 구현 시 원형 큐를 사용하는 것이 좋다.

STL queue