[STL] 06. std::queue

std::queue는 C++ 표준 라이브러리(STL)에서 제공하는 큐(Queue) 자료구조를 구현한 클래스다.

큐는 선입선출(FIFO, First-In-First-Out) 방식으로 데이터를 관리하는 자료구조로, std::queue 역시 이러한 동작을 한다.

다음은 std::queue의 주요 특징과 사용법이다.

 

 

특징

 

1. 표준 라이브러리의 일부 : std::queue는 C++ STL의 일부이며 <queue> 헤더에 정의되어 있다.

 

2. 큐의 기능 제공 : std::queue는 큐 자료구조의 기능을 제공한다.

즉 데이터를 큐에 추가하는(push) 동작과 큐에서 데이터를 제거하는(pop) 동작을 지원한다.

 

3. 컨테이너 어댑터 : std::queue는 다른 시퀀스 컨테이너를 내부적으로 사용해 큐를 구현한다.

따라서 큐의 특성을 그대로 유지하면서 다양한 컨테이너를 사용할 수 있다.

 

 

사용법

 

#include <iostream>
#include <queue>

int main() {

	std::queue<int> q;

	q.push(10);	// 10
	q.push(20);	// 10 -> 20
	q.push(30);	// 10 -> 20 -> 30
	q.push(40); // 10 -> 20 -> 30 -> 40

	q.pop();	// 20 -> 30 -> 40

	std::cout << q.front() << std::endl;	// 20
	std::cout << q.back() << std::endl;		// 40

	if (q.empty()) { //큐가 비었다면 아래의 메시지를 출력

		std::cout << "size : " << q.size() << "\nisEmpty" << std::endl; //큐의 사이즈 출력
	}
}

 

 

큐의 주요 멤버 함수와 기능

 

멤버 함수	설명	시간 복잡도
push()	큐에 요소를 추가	O(1)
pop()	큐 맨 앞의 요소를 제거	O(1)
front()	큐 맨 앞의 요소를 참조	O(1)
back()	큐 맨 뒤의 요소를 참조 ( 일부 컨테이너에선 미지원 )	O(1)
empty()	큐가 비었는지 확인	O(1)
size()	큐에 저장된 요소의 수를 반환	O(1)

 

 

std::queue 역시 std::stack처럼 컨테이너 어댑터이기에 실제 데이터 저장 시 다른 시퀀스 컨테이너를 내부적으로 사용하며

시간 복잡도는 주로 내부 컨테이너의 동작에 의해 결정된다.

내부 컨테이너에 따라 추가적인 오버헤드가 발생할 수 있는 것 또한 std::stack과 동일하다.

std::queue도 보통은 std::deque를 내부 컨테이너로 사용하는 경우가 일반적이기에

위의 표에선 std::deque를 내부 컨테이너로 사용한다는 전제 조건으로 시간 복잡도를 작성했다.