[C++ STL] Queue

1. 개념

STL 중 Queue에 대해 정리해보겠다.

Queue는 FIFO (first-in, first-out) 구조의 자료구조이다.

데이터 개수가 정확히 예측되지 않을 때 Queue는 동적으로 크기를 늘려주므로 사용이 편리하다.

물론 순환 큐는 STL에 없기 때문에, 이 경우에는 배열로 직접 구현해야 하겠다.

 

템플릿 파라미터로는 저장되는 원소의 자료형 T, 원소를 보관하는 컨테이너 Container가 있다.

기본적으로 deque를 사용하지만, 필요에 따라 list를 명시해서 사용할 수도 있다.

Queue 클래스는 내부 컨테이너의 기능을 제한하여 제공하는 Wrapper 역할을 한다(Container adapter).

 

 

2. 주요 멤버함수

기능	함수	설명	시간 복잡도
조회	front()	맨 앞에 있는 원소 리턴	O(1)
조회	back()	맨 뒤에 있는 원소 리턴	O(1)
확인	empty()	비어있는지 여부 확인	O(1)
확인	size()	원소의 수 리턴	O(1)
추가	push(x)	맨 뒤에 원소 삽입	O(1)
삭제	pop()	맨 앞 원소 제거	O(1)

• reference front(): Queue의 맨 앞에 있는 원소(가장 처음에 push된 원소)를 빼지 않고, 단순히 리턴한다. (상수 객체용 const_reference 버전도 존재한다)
• reference back(): Queue의 맨 뒤에 있는 원소(가장 마지막에 push된 원소)를 빼지 않고, 단순히 리턴한다. (상수 객체용 const_reference 버전도 존재한다)
• bool empty() const: Queue가 비어있는지 확인한다. 비어있다면 true를, 아니라면 false를 리턴한다. 함수 뒤의 const는 이 함수가 Queue의 내부 상태를 변경하지 않음을 보장한다.
• size_type size() const: Queue에 있는 원소의 수를 리턴한다.
• void push(const value_type& value): 원소를 Queue의 맨 뒤에 넣는다. (C++11부터는 성능 최적화를 고려한 버전도 제공된다)
• void pop(): Queue의 맨 앞에 있는 원소(가장 처음에 push된 원소)를 뺀다. 삭제된 원소를 리턴하지 않는다.

참고로 비어있는 Queue에서 front()나 back(), pop()을 호출하면 정의되지 않은 동작(undefined behavior)이 발생하므로, 반드시 empty()로 확인 후 호출해야 한다.

 

이외에도 push_range, emplace, swap 등의 멤버함수를 제공한다.

emplace는 객체를 생성한 다음에 넣는 push와는 달리, 인자만 전달하여 내부에서 객체를 생성하므로 불필요한 이동/복사를 줄일 수 있다.

 

 

3. 실전 예제

아래의 코드에서 주요 멤버함수를 활용해보았다.

입력 예시는 백준 10845번의 것을 활용했다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
	queue<int> q;
	
	q.push(1);
	q.push(2);
	
	cout << q.front() << "\n";
	cout << q.back() << "\n";
	
	cout << q.size() << "\n";
	
	if(q.empty()) cout << "Empty" << "\n";
	else cout << "Not empty" << "\n";
	
	cout << q.front() << "\n"; // 1
	q.pop();
	cout << q.front() << "\n"; // 2
	q.pop();
	
	// queue가 비어있을 경우, front와 pop이 정의되지 않은 동작을 할 수 있음.
	// cout << q.front() << "\n";
	// q.pop();
	
	// 대안
	if(q.empty()) cout << "Empty" << "\n"; // Empty
	else {
		cout << q.front() << "\n";
		q.pop();
	}
	
	cout << q.size() << "\n";
	if(q.empty()) cout << "Empty" << "\n";
	else cout << "Not empty" << "\n";
	
	if(q.empty()) cout << "Empty" << "\n"; // Empty
	else {
		cout << q.front() << "\n";
		q.pop();
	}
	
	q.push(3);
	
	if(q.empty()) cout << "Empty" << "\n";
	else cout << "Not empty" << "\n";
	
	cout << q.front() << "\n";
	
	return 0;
}

 

4. Deep Dive

- Vector를 Queue의 컨테이너로 사용할 수 없는 이유

• Queue는 맨 앞의 원소를 제거하는 pop_front() 함수가 필요하다. 하지만 Vector는 pop_front() 함수를 제공하지 않기 때문에, Queue의 요구조건을 충족하지 못하여 Queue의 내부 컨테이너로 사용할 수 없다.

 

- Queue의 default container로 list가 아닌 deque을 사용하는 이유

• 이는 메모리 관리 효율과 캐시 지역성에 따른 것이다. 간단하게 보면, list는 노드마다 이전/다음 주소에 대한 포인터를 저장해야 한다. 반면 deque는 여러 원소를 하나의 메모리 블럭에 담아 관리하므로, 개별 노드마다 포인터를 저장해야 하는  list에 비해 메모리 낭비가 적다.

자세한 비교는 추후 포스팅에서 다뤄보겠다.

 

 

5. 참고자료

• https://en.cppreference.com/w/cpp/container/queue.html