Queue (큐) | KAITRUST AI 백과사전

📖 상세 설명

큐(Queue)는 FIFO(First-In-First-Out, 선입선출) 원칙을 따르는 선형 자료구조입니다. 은행 창구의 대기열처럼 먼저 줄을 선 사람이 먼저 서비스를 받는 것과 같은 원리로 작동합니다. 데이터는 rear(뒤쪽)에서 삽입(enqueue)되고 front(앞쪽)에서 제거(dequeue)됩니다. 이는 LIFO(Last-In-First-Out) 구조인 스택(Stack)과 대비되는 특성입니다.

큐는 용도와 구현 방식에 따라 여러 종류로 나뉩니다. 일반 큐(Linear Queue)는 기본적인 FIFO 구조이며, 원형 큐(Circular Queue)는 배열의 끝과 처음을 연결하여 메모리를 효율적으로 사용합니다. 우선순위 큐(Priority Queue)는 각 요소에 우선순위를 부여하여 높은 우선순위의 요소가 먼저 처리됩니다. 덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 확장된 형태입니다.

큐의 핵심 연산들은 O(1) 시간복잡도를 가집니다. enqueue(삽입)와 dequeue(삭제) 연산은 포인터만 조정하면 되므로 상수 시간에 수행됩니다. peek/front 연산도 맨 앞 요소를 반환하기만 하므로 O(1)입니다. isEmpty(비어있는지 확인)도 O(1)이며, 배열 기반 구현에서 크기를 저장하면 size 연산도 O(1)입니다. 단, 큐에서 특정 요소를 검색하려면 O(n) 시간이 필요합니다.

실무에서 큐는 다양한 분야에서 핵심적으로 활용됩니다. 메시지 큐(RabbitMQ, Kafka 등)는 마이크로서비스 간 비동기 통신에 사용됩니다. BFS(너비 우선 탐색) 알고리즘은 큐를 기반으로 그래프를 탐색합니다. 운영체제의 프로세스/작업 스케줄링, 프린터 작업 관리, 웹 서버의 요청 처리, 캐시 구현(FIFO 교체 정책) 등에서 큐 구조가 필수적으로 사용됩니다.

📊 큐의 종류

일반 큐 (Linear Queue)

기본적인 FIFO 구조. 배열 또는 연결 리스트로 구현. 배열 구현 시 공간 낭비 발생 가능.

원형 큐 (Circular Queue)

배열의 끝과 처음을 연결. 메모리 재활용으로 공간 효율성 향상. 고정 크기 버퍼에 적합.

우선순위 큐 (Priority Queue)

우선순위가 높은 요소 먼저 처리. 힙(Heap)으로 구현. 다익스트라, 작업 스케줄링에 활용.

덱 (Deque)

양쪽 끝에서 삽입/삭제 가능. 스택과 큐 특성 모두 지원. 슬라이딩 윈도우 문제에 활용.

⏱️ 시간복잡도

연산	시간복잡도	설명
enqueue (삽입)	O(1)	rear에 요소 추가
dequeue (삭제)	O(1)	front에서 요소 제거
peek / front	O(1)	맨 앞 요소 확인 (제거 없음)
isEmpty	O(1)	비어있는지 확인
size	O(1)	요소 개수 반환
검색	O(n)	특정 요소 찾기 (순차 탐색)

💻 코드 예제

# Python 큐 구현 예제
from collections import deque
from typing import Any, Optional


class Queue:
    """배열 기반 큐 구현"""
    def __init__(self):
        self._items = deque()  # deque는 양쪽 O(1) 연산 지원

    def enqueue(self, item: Any) -> None:
        """큐의 rear에 요소 추가 - O(1)"""
        self._items.append(item)

    def dequeue(self) -> Any:
        """큐의 front에서 요소 제거 및 반환 - O(1)"""
        if self.is_empty():
            raise IndexError("빈 큐에서 dequeue 시도")
        return self._items.popleft()

    def peek(self) -> Any:
        """front 요소 확인 (제거 없음) - O(1)"""
        if self.is_empty():
            raise IndexError("빈 큐에서 peek 시도")
        return self._items[0]

    def is_empty(self) -> bool:
        """큐가 비어있는지 확인 - O(1)"""
        return len(self._items) == 0

    def size(self) -> int:
        """큐의 크기 반환 - O(1)"""
        return len(self._items)

    def __len__(self) -> int:
        return self.size()

    def __repr__(self) -> str:
        return f"Queue({list(self._items)})"


class CircularQueue:
    """고정 크기 원형 큐 구현"""
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._items = [None] * capacity
        self._front = 0
        self._rear = -1
        self._size = 0

    def enqueue(self, item: Any) -> bool:
        """원형 큐에 요소 추가 - O(1)"""
        if self.is_full():
            return False  # 또는 예외 발생
        self._rear = (self._rear + 1) % self._capacity
        self._items[self._rear] = item
        self._size += 1
        return True

    def dequeue(self) -> Optional[Any]:
        """원형 큐에서 요소 제거 - O(1)"""
        if self.is_empty():
            return None
        item = self._items[self._front]
        self._items[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return item

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity


# 사용 예제
if __name__ == "__main__":
    # 기본 큐 사용
    q = Queue()
    q.enqueue("작업1")
    q.enqueue("작업2")
    q.enqueue("작업3")

    print(f"큐: {q}")              # Queue(['작업1', '작업2', '작업3'])
    print(f"front: {q.peek()}")    # 작업1
    print(f"크기: {len(q)}")        # 3

    print(f"처리: {q.dequeue()}")  # 작업1
    print(f"처리: {q.dequeue()}")  # 작업2
    print(f"남은 큐: {q}")          # Queue(['작업3'])

    # BFS 예제 - 큐 활용
    from collections import deque

    def bfs(graph, start):
        """너비 우선 탐색 - 큐 활용"""
        visited = set()
        queue = deque([start])
        result = []

        while queue:
            node = queue.popleft()
            if node not in visited:
                visited.add(node)
                result.append(node)
                queue.extend(n for n in graph[node] if n not in visited)

        return result

    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print(f"BFS 순회: {bfs(graph, 'A')}")  # ['A', 'B', 'C', 'D', 'E', 'F']

// JavaScript 큐 구현 예제

class Queue {
    constructor() {
        this.items = [];
        this.frontIndex = 0;  // 가상의 front 인덱스
    }

    // 큐의 rear에 요소 추가 - O(1)
    enqueue(item) {
        this.items.push(item);
        return this;
    }

    // 큐의 front에서 요소 제거 - 평균 O(1)
    dequeue() {
        if (this.isEmpty()) {
            throw new Error("빈 큐에서 dequeue 시도");
        }
        const item = this.items[this.frontIndex];
        this.frontIndex++;

        // 메모리 최적화: 절반 이상 비었으면 정리
        if (this.frontIndex > this.items.length / 2) {
            this.items = this.items.slice(this.frontIndex);
            this.frontIndex = 0;
        }
        return item;
    }

    // front 요소 확인 - O(1)
    peek() {
        if (this.isEmpty()) {
            throw new Error("빈 큐에서 peek 시도");
        }
        return this.items[this.frontIndex];
    }

    // 큐가 비어있는지 확인 - O(1)
    isEmpty() {
        return this.frontIndex >= this.items.length;
    }

    // 큐의 크기 - O(1)
    get size() {
        return this.items.length - this.frontIndex;
    }

    // 배열로 변환
    toArray() {
        return this.items.slice(this.frontIndex);
    }

    toString() {
        return `Queue(${JSON.stringify(this.toArray())})`;
    }
}


// 원형 큐 구현
class CircularQueue {
    constructor(capacity) {
        this.capacity = capacity;
        this.items = new Array(capacity).fill(null);
        this.front = 0;
        this.rear = -1;
        this._size = 0;
    }

    enqueue(item) {
        if (this.isFull()) return false;
        this.rear = (this.rear + 1) % this.capacity;
        this.items[this.rear] = item;
        this._size++;
        return true;
    }

    dequeue() {
        if (this.isEmpty()) return null;
        const item = this.items[this.front];
        this.items[this.front] = null;
        this.front = (this.front + 1) % this.capacity;
        this._size--;
        return item;
    }

    isEmpty() { return this._size === 0; }
    isFull() { return this._size === this.capacity; }
    get size() { return this._size; }
}


// 사용 예제
const q = new Queue();
q.enqueue("작업1").enqueue("작업2").enqueue("작업3");

console.log(`큐: ${q}`);              // Queue(["작업1","작업2","작업3"])
console.log(`front: ${q.peek()}`);    // 작업1
console.log(`크기: ${q.size}`);        // 3

console.log(`처리: ${q.dequeue()}`);  // 작업1
console.log(`처리: ${q.dequeue()}`);  // 작업2
console.log(`남은 큐: ${q}`);          // Queue(["작업3"])


// BFS 예제 - 큐 활용
function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            visited.add(node);
            result.push(node);
            queue.push(...graph[node].filter(n => !visited.has(n)));
        }
    }
    return result;
}

const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};
console.log(`BFS 순회: ${bfs(graph, 'A')}`);  // A,B,C,D,E,F


// 비동기 작업 큐 예제 (실무 활용)
class AsyncTaskQueue {
    constructor(concurrency = 1) {
        this.queue = [];
        this.running = 0;
        this.concurrency = concurrency;
    }

    async add(task) {
        this.queue.push(task);
        await this.process();
    }

    async process() {
        while (this.queue.length > 0 && this.running < this.concurrency) {
            const task = this.queue.shift();
            this.running++;
            try {
                await task();
            } finally {
                this.running--;
            }
        }
    }
}

// 비동기 작업 큐 사용
const taskQueue = new AsyncTaskQueue(2);  // 동시 2개 작업
taskQueue.add(async () => {
    console.log("작업 1 시작");
    await new Promise(r => setTimeout(r, 1000));
    console.log("작업 1 완료");
});

🗣️ 실무 대화 예시

기술 면접에서 - Stack vs Queue 비교

"스택과 큐의 핵심 차이는 데이터 처리 순서입니다. 스택은 LIFO로 마지막에 들어온 게 먼저 나가서 함수 호출 스택이나 실행 취소(Undo)에 적합합니다. 큐는 FIFO로 먼저 들어온 게 먼저 나가서 작업 대기열이나 BFS 탐색에 씁니다. 예를 들어 웹 서버 요청 처리는 들어온 순서대로 처리해야 하니 큐를, 브라우저 뒤로가기는 최근 페이지부터 돌아가니 스택을 사용합니다. 시간복잡도는 둘 다 삽입/삭제 O(1)로 동일합니다."

아키텍처 회의에서 - 메시지 큐 도입 논의

"주문 처리 시스템에 메시지 큐를 도입하면 좋겠습니다. 지금은 주문 API가 결제, 재고, 알림 서비스를 동기로 호출하다 보니 하나라도 느려지면 전체 응답이 지연되고, 트래픽 급증 시 장애가 전파됩니다. RabbitMQ나 Kafka로 비동기 처리하면 주문 API는 큐에 메시지만 넣고 즉시 응답하고, 각 서비스가 자기 속도로 처리할 수 있어요. 서비스 간 결합도도 낮아지고 장애 격리도 됩니다. 다만 메시지 순서 보장과 중복 처리 방지 로직은 별도로 고려해야 합니다."

코드 리뷰 중 - 자료구조 선택

"이 작업 스케줄러에서 배열 shift() 대신 연결 리스트 기반 큐를 쓰면 좋겠어요. JavaScript 배열의 shift()는 O(n)이라 요소가 많아지면 성능이 급격히 떨어집니다. 작업이 수만 개까지 쌓일 수 있다고 했잖아요. 직접 큐 클래스를 만들거나, 두 개의 스택으로 큐를 구현하면 평균 O(1)에 dequeue가 가능합니다. 아니면 front 인덱스를 관리해서 실제 shift 없이 처리하는 방법도 있어요."

⚠️ 주의사항

1

큐 오버플로우

고정 크기 배열로 구현한 큐에서 용량을 초과하여 enqueue하면 오버플로우가 발생합니다. 특히 원형 큐가 아닌 일반 배열 큐에서는 dequeue 후에도 앞쪽 공간을 재사용하지 못해 공간 낭비가 심합니다. 동적 크기 조절이 필요하면 연결 리스트 기반 구현이나 deque를 사용하세요.

2

스레드 안전성 (Thread Safety)

멀티스레드 환경에서 일반 큐를 공유하면 경쟁 조건(Race Condition)이 발생할 수 있습니다. 여러 스레드가 동시에 enqueue/dequeue하면 데이터 손실이나 무한 루프가 발생할 수 있습니다. Python의 queue.Queue, Java의 ConcurrentLinkedQueue처럼 스레드 안전한 구현을 사용하거나, 락(Lock)으로 동기화해야 합니다.

3

메모리 관리와 메모리 릭

연결 리스트 기반 큐에서 노드 제거 후 메모리 해제를 잊으면 메모리 릭이 발생합니다. 가비지 컬렉션이 있는 언어에서도 큐에 대용량 객체를 넣고 dequeue만 하면, 참조가 남아있어 GC되지 않을 수 있습니다. 메시지 큐 시스템에서는 처리 완료된 메시지의 ACK(확인) 처리가 중요합니다.

🔗 관련 용어

📚 더 배우기

VisuAlgo - 큐 시각화 학습 GeeksforGeeks - 큐 완벽 가이드 LeetCode - 큐 코딩 문제