[C++, STL] 알고리즘 문제풀이를 위한 큐(queue)

by

서론

줄을 세우다

어느 중학교, 점심시간을 알리는 종과 함께 학생들이 달린다. 배식을 먼저 받기 위해서는 달려야한다. 한참을 달리던 학생들은 식당 입구에서 식권을 내고 한줄로 천천히 배식구를 향해 걸어간다. 이들은 더이상 뛰지 않는다. 먼저 식권을 낸 학생이 먼저 배식을 받을것을 알기 때문이다.

그래서 큐는 뭐지?

https://ko.wikipedia.org/wiki/%EC%84%A0%EC%9E%85_%EC%84%A0%EC%B6%9C

큐는 먼저 들어온 자료가 먼저 나가는 자료구조다.(=선입선출, First In First Out) 위의 예에서 학생들이 식당에서 걷는 대기열은 큐에 해당한다. 식권을 내는 행위는 큐에 자료를 집어넣는 Enqueue(=Push), 배식을 받는 행위는 큐에서 자료를 빼내는 Dequeue(=Pop)이다.

어디에 사용되는가?

큐에서는 자료의 순서가 바뀌거나 변형되지 않기 때문에 자료를 임시 저장하는 대기열(버퍼)로 유용하게 사용된다. 대기열은 다수의 자료가 접근하고자 할때 줄을 세워 충돌을 방지할 수 있다.\

큐의 사용 예

  • 윈도우 메시지 큐
  • CPU 스케쥴링 방법 중 하나인 FCFS(First In First Serve)
  • 프린트 스풀링

큐는 알고리즘 문제풀이에서도 필수적이다. 단지 큐를 활용할 수 있는지 물어보는 문제도 많으며 큐를 확장시킨 우선순위 큐, 코딩테스트가 좋아하는 BFS(Breadth First Search)등 다양한곳에서 사용된다.

STL을 이용하면 큐를 편리하게 이용할 수 있다.

큐는 배열이나 링크드리스트로 구현할 수 있다. 그런데 알고리즘 문제풀이에서 이것을 구현하고 있을 필요는 없다. STL에 큐가 있기 때문이다.

벡터 vs 큐

벡터는 push_back함수로 Enqueue 구현이 가능하고 erase함수를 통해 Dequeue 구현이 가능하다. 즉 벡터로 큐를 만들 수 있다. 게다가 벡터는 큐와 다르게 원소에 직접접근이 가능하다. 그래서 큐를 벡터로 구현하면 편리할 때가 있다. 그러나 벡터는 erase에서 시간복잡도가 O(N)으로 매우 느리다. 따라서 상황에 맞게 큐 혹은 벡터를 사용해야 한다.

vector<int>v;
v.push_back(1); // v = {1}
v.push_back(2); // v = {1, 2}
v.push_back(3); // v = {1, 2, 3}
v.erase(v.begin()); // v = {2, 3}
v.erase(v.begin()); // v = {3}
v.erase(v.begin()); // v = {}

헤더파일

큐를 사용하기 위해서는 헤더파일이 필요하다.

#include<queue>

큐 선언

std::queue<템플릿>이름

글의 가독성을 위해 std를 생략한다. std는 네임스페이스(using namespace std)로 대체될 수 있다. 템플릿은 int, string, vector, struct 등 다양하게 들어갈 수 있다. 즉 큐의 원소는 다양한 자료형이 들어갈 수 있다.

queue<int>q // q = {}

멤버 함수

push(원소)

큐에 원소를 넣는다.

queue<int>q; // q = {}
q.push(4); // q = {4}
q.push(3); // q = {4, 3}
pop()

큐의 가장 앞 원소를 제거한다.(큐에 들어간지 가장 오래된 원소를 제거한다.)

queue<int>q; // q = {}
q.push(4); // q = {4}
q.push(3); // q = {4, 3}
q.pop(); // q = {3}
front(), back()

front는 큐의 첫 원소(가장 오래된 원소)를 참조한다.

back은 큐의 마지막 원소(가장 최근 들어간 원소)를 참조한다.

queue<int>q; // q = {}
q.push(4); // q = {4}
q.push(3); // q = {4, 3}
cout <<q.front(); // 출력 : 4
cout <<q.back(); // 출력 : 3
size()

큐의 원소의 개수를 출력한다.

queue<int>q; // q = {}
q.push(4); // q = {4}
q.push(3); // q = {4, 3}
cout <<q.size(); // 출력 : 2
empty()

큐가 비어있으면 1, 아니면 0을 출력한다.

queue<int>q; // q = {}
cout << q.empty(); // 출력 : 1
q.push(4); // q = {4}
cout << q.empty(); // 출력 : 0

empty()는 반복문과 함께 유용하게 쓰일 수 있다. 큐의 원소가 하나씩 제거되는 반복문에서 조건문이 !empty()라면 큐의 원소가 모두 제거될 때까지 반복하고 빠져나온다.

while(!q.empty()){
	q.pop();
}

참고

https://docs.microsoft.com/en-us/cpp/standard-library/queue-class?view=vs-2019

Leave a Comment