005_큐 (std::queue)

큐 (std::queue)

큐(queue)는 컨테이너 어댑터(Container Adapter) 중 하나이다. (deque 기반)

queue 는 FIFO(First-In-First-Out) 구조로 제일 먼저 넣은 데이터가 처음으로 빠져나온다.

queue 는 제일 앞, 뒤가 아닌 원소들의 확인, 변경이 원칙적으로 불가능하다.

queue 에 대한 일반적인 연산의 복잡도는 다음과 같다.

원소의 추가 : O(1)
원소의 제거 : O(1)
제일 앞, 뒤의 원소 확인 : O(1)

queue 의 사용

queue 헤더파일

#include <queue>

queue의 선언

std::queue<Type> QueueName;

queue의 생성자 (편의상 int)

std::queue<int> q;	비어있는 큐 q를 생성
std::queue<int> q2(q1);	큐 q1를 복사하여 큐 q2를 생성

queue의 멤버 함수

std::queue<int> q;

q.push(n)	큐 맨 뒤에 원소 n 삽입
q.pop()	큐 맨 앞의 원소를 제거
q.front()	큐 맨 앞 원소의 참조를 반환
q.back()	큐 맨 뒤 원소의 참조를 반환
q.size()	원소의 개수를 반환
q.empty()	큐 q가 비어있으면 `true`를 반환
q2.swap(q1)	q1 큐와 q2 큐를 서로 바꿈

queue의 원소 삽입/삭제

#include <iostream>
#include <queue>

int main() 
{
	std::queue<int> q;
	for (int i = 1; i <= 5; ++i)
	{
		q.push(i);
		std::cout << q.front() << ", " << q.back() << std::endl;
	}

	std::cout << std::endl;
	for (int i = 1; i <= 5; ++i)
	{
		std::cout << q.front() << ", " << q.back() << std::endl;
		q.pop();
	}

	return 0;
}