[자료구조] 큐(Queue) 완벽 정리: 작동 원리와 코딩 테스트 활용 전략

1. 🔍 큐의 개념

queue는 줄을 서다라는 뜻을 가지고 있다. 맛집에서 줄을 선 순서대로 식당에 입장할 때가 큐의 예시가 될 수 있다. 먼저 줄을 선 사람이 먼저 입장한다.

💯 큐의 특징

• 선입선출 또는 FIFO(First In First Out): 먼저 들어간 데이터가 먼저 나오는 자료구조
• 큐의 push(), pop(), front(), empty() 연산 모두 시간 복잡도가 $O(1)$이다.

📝 큐의 ADT

배열의 인덱스는 0부터 시작하므로 아무것도 넣지 않은 상황을 표현하기 위해 초깃값을 -1로 했다.

• 스택의 ADT와 비슷하지만 스택의 top 대신 front와 rear가 생긴 것을 볼 수 있다.
• front는 큐의 앞, rear는 큐의 뒤를 의미한다.
• 큐는 앞에서 데이터를 빼고 뒤에서 데이터를 넣으므로 이렇게 앞과 뒤의 데이터 최종 위치를 기억할 변수가 필요하다.
• 아래 그림은 데이터가 없는 상태이므로 front와 rear 모두 -1이다.

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터의 개수가 maxsize인지 확인해 boolean 값을 반환한다. 가득 차 있다면 True, 아니면 False이다.
연산	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다. 데이터가 하나라도 있으면 False, 아니면 True이다.
연산	void push(ItemType item)	큐에 데이터를 푸시한다.
연산	ItemType pop()	큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환한다.
상태	Int front	큐에서 가장 마지막에 팝한 데이터의 위치를 기록한다.
상태	int rear	큐에서 최근에 푸시한 데이터의 위치를 기록한다.
상태	ItemType data[maxsize]	큐의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

2. 🎨 큐에서 데이터가 이동하는 과정 살펴보기

🧠 선형 큐의 세부 동작 과정 예시

구체적인 예와 함께 큐에서 연산이 수행되면 어떻게 되는지 알아보자.

1단계 push(3)

1. isFull() 연산으로 현재 큐가 가득 찼는지 확인한다.
   • true이면 데이터를 push하지 않는다.
2. rear를 +1한다.
3. rear가 가리키는 위치에 3을 push한다.

2단계 pop

1. isEmpty() 연산으로 큐가 비었는지 확인한다.
   • front와 rear의 값이 같은지 확인해서 큐에 원소가 없는데 pop하는 동작을 방지한다.
2. 비어있지 않은 경우 front를 +1한다.
   • 데이터를 삭제하지 않고 삭제한 것처럼 관리가 가능하다.
3. 여기서 pop을 한 번 더 하는게 오른쪽 그림이다.
   • 이 케이스에서는 큐가 비어있는 것으로 판단(front == rear)하게 된다.

3단계 queue가 가득 찰 때까지 push

1. 앞선 작업에서 5, 6, 8을 push하면 아래와 같은 상황이 된다.
2. 이후 한 번 더 push를 하게되면 isFull() 연산의 결과가 true이므로 push가 불가능하다.

❗ 선형 큐의 문제점

• 앞선 예시에서 큐가 가득 찬 상태에서 생각을 해보면 실제 data에 저장된 데이터는 3, 5, 6, 8이지만 큐가 실제 관리하고 있는 데이터는 5, 6, 8로 3개이다.
• 다시 말해 front의 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 한다.
• 실제 data의 공간은 4개인데 큐가 관리하는 데이터는 3개이므로 메모리 공간을 낭비한 상황이다.

🚀 큐를 원형으로 개선하기

• 위에서 언급된 문제를 개선하려면 선형 큐가 아니라 원형 큐가 필요하다.
• 선형 큐는 front와 rear가 한 방향으로 이동하지만 원형 큐는 front와 rear가 돌게 된다.
• 원형 큐가 선형 큐보다 구현하기 복잡하지만 메모리 공간을 절약한다는 장점이 있다.

3. 💡 큐의 특성을 활용하는 분야

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용된다.

• 작업 대기열: 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다. 이때 큐를 활용할 수 있다.
• 이벤트 처리: 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있다.

4. 📦 큐 사용하기

구현할 필요 없이 STL이나 파이썬 라이브러리를 활용하여 큐를 사용할 수 있다.

⚡ C++

STL에서 큐를 제공한다. #include <queue>

#include <queue>

queue<int> q;

⚡ Python

파이썬에서는 collections.deque를 사용해 큐처럼 사용할 수 있다. deque는 양방향 큐를 의미하며 양쪽 끝에서 데이터를 추가하고 삭제할 수 있다. 사실상 queue보다 더 유연한 자료구조이다.

from collections import deque

queue = deque()

Algorithm Theory 카테고리 내 다른 글 보러가기