7. Queue

queue(큐)는 FIFO(First-In-First-Out) 방식으로 작동하는 템플릿 클래스이다. 헤더파일 <queue>를 인클루드하면 사용이 가능하다. queue 클래스는 <queue>에서 인클루드하는 헤더파일 <bits/stl_queue.h>에 정의되어 있다. <queue>는 헤더파일 <deque>뿐 아니라 <vector>도 인클루드하는데, 그 이유는 다음 글에서도 언급하겠지만 priority_queue가 기본 컨테이너로 vector를 사용하기 때문이다.

 

큐의 선언 방법도 스택의 선언 방법과 같다.

queue<int> q;

이렇게 선언하면 비어 있는 int형 큐가 생성된다.

 

큐의 멤버 함수는 다음과 같다:

q.push(x);	q의 끝에 x를 삽입한다.
q.pop();	q의 첫번째 원소를 삭제한다.
q.front();	q의 첫번째 원소를 참조한다.
q.back();	q의 마지막 원소를 참조한다.
q.size();	q에 들어 있는 원소의 개수를 반환한다.
q.empty();	q가 비었는지 확인한다.
q.emplace(x);	q의 끝에 x를 삽입한다.
q.swap(k);	q와 k를 맞바꾼다.

스택의 멤버 함수와 많이 다르지 않다. 차이점을 찾아보면, 스택은 원소가 삽입되는 곳과 삭제되는 곳이 같지만 큐는 서로 반대이다. 따라서 원소를 참조하는 함수가 서로 다르고, 큐의 경우 $2$개의 내장 함수(queue::front, queue::back)가 존재한다.

 

큐도 스택과 마찬가지로 원소를 모두 삭제하려면 이전 글에서 설명한 것과 같이 해야 한다.

 

큐의 경우 BFS(0-1 BFS는 제외)를 실행할 때 쓰게 되기 때문에 스택보다 더 자주 쓰게 될 가능성이 있다.

 

[연습문제]

 

BOJ 10845. 큐 (Silver IV)

큐 연습 문제이다. 주어지는 입력에 맞게 동작하도록 멤버 함수를 호출하면 된다.

 

BOJ 18258. 큐 2 (Silver IV)

이 문제는 입력이 많기 때문에 멤버 함수를 호출하는 식으로 하면 시간 초과가 발생한다. 배열 등으로 직접 큐를 구현하면 풀 수 있다.

 

→ solved.ac tag: queue