Queue - 컴퓨터공학 > 자료구조 | AI Insight Note

큐(Queue)는 선입선출(FIFO, First In First Out) 원칙으로 동작하는 선형 자료구조다. 먼저 들어온 데이터가 먼저 나가는 구조로, 줄 서기(대기열)를 추상화한 것이다. 운영체제의 프로세스 스케줄링, 네트워크 패킷 처리, 너비 우선 탐색(BFS) 등 다양한 곳에 활용된다.

핵심 연산

초기 상태:  front → [] ← rear

enqueue(1): front → [1] ← rear
enqueue(2): front → [1, 2] ← rear
enqueue(3): front → [1, 2, 3] ← rear
dequeue():  front → [2, 3] ← rear  (1 반환)
peek():     front = 2 (제거 없이 조회)

연산	설명	시간복잡도
enqueue(x)	rear(뒤)에 삽입	O(1)
dequeue()	front(앞)에서 제거·반환	O(1)
peek() / front()	앞 요소 조회 (제거 없음)	O(1)
isEmpty()	비어있는지 확인	O(1)
size()	원소 개수	O(1)

큐 vs 스택

항목	큐 (Queue)	스택 (Stack)
원칙	FIFO (선입선출)	LIFO (후입선출)
삽입 위치	rear(뒤)	top(위)
제거 위치	front(앞)	top(위)
비유	줄 서기	접시 쌓기

큐의 종류

원형 큐 (Circular Queue)

배열 끝에 도달하면 처음으로 순환. 공간 낭비 없이 고정 크기 큐 구현.

덱 (Deque, Double-Ended Queue)

양쪽 끝에서 삽입·삭제 모두 가능한 큐. 큐와 스택 기능을 동시에 제공.

우선순위 큐 (Priority Queue)

FIFO 대신 우선순위(Priority) 가 높은 요소를 먼저 꺼냄. 힙(Heap)으로 구현.

구현	enqueue	dequeue
배열	O(1)	O(n)
힙	O(log n)	O(log n)

언어별 구현

python

# Python
from collections import deque
q = deque()
q.append(1)      # enqueue
q.append(2)
q.popleft()      # dequeue → 1

java

// Java
Queue<Integer> q = new LinkedList<>();
q.offer(1);      // enqueue
q.offer(2);
q.poll();        // dequeue → 1
q.peek();        // front 조회 → 2

javascript

// JavaScript (배열로 간단 구현)
const q = [];
q.push(1);       // enqueue
q.push(2);
q.shift();       // dequeue → 1 (O(n), 비효율)

주요 활용

분야	활용 예시
OS 스케줄링	프로세스·스레드 대기열
네트워크	패킷 버퍼, 라우터 대기열
그래프 탐색	너비 우선 탐색(BFS)
프린터	인쇄 작업 스풀링
비동기 처리	메시지 큐 (Kafka, RabbitMQ)
캐시	LRU 캐시 (덱 활용)

BFS에서의 큐

python

from collections import deque

def bfs(graph, start):
    visited = set()
    q = deque([start])
    visited.add(start)

    while q:
        node = q.popleft()          # dequeue
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)  # enqueue

참고문헌

•Cormen et al. (2009). Introduction to Algorithms — Chapter 10
•Sedgewick & Wayne. Algorithms, 4th Edition

Queue큐

핵심 연산

큐 vs 스택

큐의 종류

원형 큐 (Circular Queue)

덱 (Deque, Double-Ended Queue)

우선순위 큐 (Priority Queue)

언어별 구현

주요 활용

BFS에서의 큐

관련 개념

참고문헌

관련 노트

트리Tree

이진 트리Binary Tree

스택Stack