1.9.2 std::queue

LIFO 구조를 사용하는 std::stack과 달리 FIFO(First In First Out, 선입선출) 구조가 필요한 경우도 많이 있으며, 이러한 경우에는 std::queue 어댑터를 사용할 수 있습니다. std::queue는 스택과 비슷한 형태의 함수를 지원하며, 다만 LIFO 대신 FIFO를 지원하기 위해 그 의미와 동작이 조금 다르게 정의되어 있습니다. 예를 들어 std::queue에서 push()는 std::stack에서의 push_back()을 의미하지만, pop() 명령은 pop_front()를 의미합니다. 원소를 제거하는 pop() 함수와 달리, 단순히 양 끝단에 있는 원소에 접근하고 싶을 때에는 front() 또는 back() 함수를 사용합니다.

다음은 std::queue를 사용하는 예제 코드입니다.

std::queue<int> q;
q.push(1);       // 맨 뒤에 1을 추가: {1}
q.push(2);       // 맨 뒤에 2를 추가: {1, 2}
q.push(3);       // 맨 뒤에 3을 추가: {1, 2, 3}
q.pop();         // 맨 앞 원소를 제거: {2, 3}
q.push(4);       // 맨 뒤에 4를 추가: {2, 3, 4}

앞 예제 코드에서는 큐(queue)에 원소 1, 2, 3을 차례대로 삽입합니다. 그다음에 큐에서 원소 하나를 제거합니다. 제일 먼저 추가된 원소가 1이므로 원소를 제거할 때에도 1이 먼저 제거됩니다. 그런 다음 4를 추가하면 큐의 맨 뒤에 들어가게 됩니다.

std::queue는 std::stack과 같은 이유로 std::deque을 기본 컨테이너로 사용하며, 앞서 사용한 모든 함수는 시간 복잡도 O(1)로 동작합니다.