내가 사용하는 STL (2) - 큐 (queue)

Queue

FIFO. First In First Out의 자료구조이다. 즉, 큐에 먼저 들어간 원소가 먼저 빠져 나오게 된다. 즉 아래와 같은 형식으로 자료구조가 원소들을 관리한다는 것이다. 

문법

queue<ll> q	ll 형식의 자료를 담는 큐 q 생성
q.push(x)	q의 가장 뒤쪽에 원소 x삽입
q.front()	q의 가장 앞에 있는 원소 참조
q.back()	q의 가장 뒤에 있는 원소 참조
q.pop()	q의 가장 앞에 있는 원소 삭제
q.size()	q에 들어있는 원소의 수 반환
q.empty()	q에 원소가 없는지(비었는지) 판별
while(!q.empty()) or while(q.size())	q가 빌 때까지. 보통 q의 원소를 하나씩 모두 뺄 때 사용
q1=q2	q1에 그대로 q2를 대입
swap(q1,q2)	q1과 q2를 서로 교체

Queue의 활용

제일 익숙하고 queue를 많이 사용한 것은 bfs에서 였을 것이다. 물론 stack 처럼 답을 담아놓는 용도로 사용할 수도 있지만, queue는 역순으로 뽑아낸다는 것과 같은 강점이나 특징이 없다. 그냥 vector를 쓰는 것이 몇백배 유용하다. 그래서 좀 더 일반적으로 Queue를 사용하는 경우에 대해 말하려고 한다.

Queue는 현재의 시점에서 미래에 어떤 일을 하겠다고 확정지을 때 그 리스트를 담기 위해서 사용한다. 이때 현재의 시점에서 하는 행동은 미래 시점에서 하려는 행동과 거의 일치한다.
예시를 들어서 설명을 해보려고 한다. BFS의 경우를 생각하면 현재 위치에서 탐색을 한다. 그러면서 갈 수 있는 노드들에 대해서 다음에 방문하겠다고 queue에 담아 둔다. 그리고서는 나중에 그 노드의 차례가 오면 그 노드에서 탐색을 진행한다.
또 다른 queue를 활용하는 예시로는 위상정렬이 있다. 현재 시점에서 노드에 확정을 지으면서 indegree가 없는 다른 노드를 탐색하며 queue에 담아 놓는다. 예시와 함께 생각하면 훨씬 더 감이 잡힐 것이다. 사실 잘 모르고 있어도 사용을 하는데 감을 못잡는 것도 아니고, 딱히 지장이 있는것도 아니긴 하다.