[자료 구조 #3] 큐(queue)

기회는 준비된 자에게 온다 !

큐의 정의

큐(queue)는 무엇일까?

게임 좋아하는 사람이면 큐 잡는데 시간이 오래 걸린다라는 말을 한번쯤은 해보았을 것이다.

이 때 말하는 큐도 지금 말하는 큐와 같다.

영어로는 대기열이라는 뜻이다.

큐의 개념

쉽게 생각해서 은행에 갔다고 생각하자.

번호표를 먼저 뽑은 사람이 업무를 먼저 보는 것이다. (물론 VIP는 우선 순위 큐)

따라서 먼저 넣은 데이터가 먼저 출력되는 일명 FIFO(First In First Out) 구조로 데이터를 저장하는 자료 구조다.

큐의 연산

앞선 모든 자료 구조에서는 4가지 동작 (읽기, 검색, 삽입, 삭제)의 기본 연산을 지원한다.

큐에서 많이 사용되는 메소드는 다음과 같다.

• push() : 큐에 원소를 삽입, 이 때 큐의 크기가 1 증가
• pop() : 큐에서 제일 먼저 저장된 원소를 뺀다. 이 때 큐의 크기가 1 감소
• front() : 큐에서 제일 먼저 저장된 원소를 반환한다. pop()은 원소 반환을 하지 않음
• empty() : 큐가 비었는 지 검사하여 bool 값을 반환
• size() : 현재 큐에 저장된 데이터의 개수를 반환

큐 사용법 (C++)

기본적인 선언은 아래와 같이 한다.

#include <queue>

std::queue<int> num_queue;

이렇게 되면 큐에 [3 6 9] 순서대로 입력이 된다.

num_queue.push(3);
num_queue.push(6);
num_queue.push(9);

따라서 큐에 제일 먼저 들어간 순서대로 반환이 되는데,

auto num = num_queue.front();
num_queue.pop();
std::cout << "num: " << num << std::endl;

큐에서 단지 제일 앞에 저장된 데이터가 보고 싶을 때는 front()를 사용하지만, 그 데이터를 대기열에서 없애고 싶을 때는 pop() 해주는 것을 잊지 말자.

큐는 clear() 기능이 없다.

그래서 일일히 없애줘야 한다.

큐 clear() 구현

간단하다. 비어 있지 않으면? pop()을 계속 하자!

while (!num_queue.empty()) num_queue.pop();

큐의 사용 사례

FIFO 구조에서 알 수 있듯이 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 순간에 사용된다.

예를 들어,

• 인쇄 대기열
• 콜센터 고객 대기시간
• 티켓팅 카운터
• (고급) 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 처리해야할 노드 리스트를 저장할 때 큐 사용

Reference

• [자료구조] 큐(Queue)란