큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 됩니다. 공항에서 입국수속을 하는 줄과 같은 상황이라고 볼 수도 있습니다.스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 합니다.
큐에서 연산의 시간복잡도를 보면 스택처럼 원소의 추가와 제거가 모두 O(1)입니다. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 합니다. 아무튼 가장 앞쪽에 위치해있거나 가장 뒤쪽에 위치한 원소의 확인도 O(1)입니다.
큐도 스택처럼 배열 혹은 연결 리스트 둘 중 어느 것을 이용해도 구현을 하는데 문제가 없지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열로 어떻게 구현하면 될지만 짚고 넘어가겠습니다. 큐를 구현할 때는 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개가 필요합니다. 이 head와 tail을 어떻게 두는지는 예시를 보고 이해해보겠습니다.
head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 + 1입니다. 꼭 이렇게 안두고 tail을 가장 뒤에 있는 원소의 인덱스로 두어도 괜찮지만 저는 지금 보시는 것 처럼 두겠습니다.
이와 같이 스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생기게 됩니다. 이 문제를 해결하는 방법은 의외로 간단한데 큐의 원소가 들어갈 배열을 원형으로 만드는 것입니다. 관념적으로는 배열이 원형인거고, 실제 구현을 할 땐 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만들면 됩니다.
즉, dat의 5, 6, 7번지를 사용하는 상황에서 원소 1개가 추가되면 0번지를 점유하는 것입니다. 이렇게 원형의 배열을 가정하고 구현한 큐를 원형 큐(Circular Queue)라고 부릅니다.
그냥 선형 배열에서 만든 큐는 삭제가 될 때 마다 쓸모없는 공간이 계속 생겨서 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 생길 수 있는데, 원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제가 없습니다. 그래서 실무에서 굳이 STL 말고 큐를 직접 구현해서 쓰겠다고 하면 원형 큐로 만드는게 좋습니다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 뺌
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다..