큐는 스택에 비해 먼저 들어간 값이 먼저 나오는(FIFO) 자료 구조이다. 자료를 관리하는 기본적인 기능은 시퀀스의 것을 그대로 재사용할 수 있으며 FIFO 원리대로 동작하기 위해 꼭 필요한 인터페이스는 다음 4가지 밖에 없다.
push, pop : 앞뒤에서 값을 추가하거나 제거한다.
front, back : 앞뒤의 값을 읽는다.
이 4 개의 주요 함수와 size, empty 그리고 생성자가 큐의 함수 전부이다. 이 정도 기능만 있으면 큐를 얼마든지 사용할 수 있다. 스택과 마찬가지로 pop은 값을 제거하기만 하며 리턴하지 않으므로 front, back으로 값을 따로 읽어야 한다. 큐의 템플릿 선언은 다음과 같다.
template<class T, class Cont=deque<T> >
class queue { ... }
큐에 저장할 타입과 기본 컨테이너를 템플릿 인수로 지정하는데 디폴트 컨테이너는 데크로 되어 있다. 원한다면 리스트로 변경할 수도 있지만 벡터는 큐 구현에는 사용할 수 없다. 왜냐하면 벡터는 앞쪽에서 삽입, 삭제 기능을 제공하지 않으므로 큐 구현에는 적합하지 않기 때문이다. 간단한 컨테이너지만 그냥 넘어가면 섭섭하므로 예제나 하나 만들어 보자.
|
예 제 : queue |
#include <iostream>
#include <queue>
using namespace std;
void main()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
}
정수를 저장하는 큐 q를 선언하고 1, 2, 3을 순서대로 삽입했다. 그리고 큐가 빌 때까지 값을 빼내 출력했는데 큐는 먼저 넣은 값이 먼저 나오는 구조를 가지고 있으므로 삽입한 순서 그대로 1, 2, 3이 출력된다.
14장에서 큐를 이용한 snake 게임을 만들어 본 적이 있는데 이 게임의 주요 자료 구조인 큐를 STL의 queue로 작성할 수도 있다. 주요 자료 구조를 라이브러리에서 가져다 쓰면 신뢰성과 효율성을 공짜로 얻을 수 있으므로 프로그래머는 게임 고유의 논리 구현에만 치중하면 된다.