CS학습2026년 8월 16일

Queue: FIFO(First-In, First-Out) 원칙을 따르는 자료구조

큐는 먼저 들어온 요소가 먼저 나가는 선형 자료구조이다. 데이터 처리 순서 관리에 유용하며, 다양한 알고리즘 및 시스템 구현에 활용된다. 대표적인 예로는 작업 스케줄링, 메시지 버퍼링 등이 있다.

송민성3분 읽기

1. 개념

큐(Queue)는 First-In, First-Out (FIFO) 원칙을 따르는 추상 데이터 타입(Abstract Data Type, ADT)이다. 이는 가장 먼저 들어온 요소가 가장 먼저 나가는 방식을 의미하며, 마치 줄 서기 상황과 유사하다. 큐는 데이터를 저장하고 순서대로 꺼내어 처리하는 데 적합하다.

2. 왜 사용하는가

작업 스케줄링: 운영체제에서 프로세스 또는 작업을 실행할 순서를 결정하는 데 사용된다.
메시지 버퍼링: 네트워크 통신이나 비동기 처리 시 메시지를 일시적으로 저장하고 순서대로 전달하는 데 사용된다.
너비 우선 탐색(Breadth-First Search, BFS): 그래프 탐색 알고리즘에서 정점을 방문하는 순서를 관리하는 데 사용된다.
프린터 큐: 여러 개의 인쇄 작업을 순서대로 처리한다.

3. 동작 원리

큐는 일반적으로 다음과 같은 연산을 지원한다:

Enqueue (enqueuing): 큐의 끝(rear)에 요소를 추가하는 연산이다.
Dequeue (dequeuing): 큐의 앞(front)에서 요소를 제거하고 반환하는 연산이다.
Peek: 큐의 맨 앞에 있는 요소를 확인하지만, 제거하지는 않는다.
IsEmpty: 큐가 비어 있는지 여부를 확인한다.

4. 코드 예제

python

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)  # O(1)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0) # O(n) - list의 pop(0)은 O(n)
        else:
            return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

# 사용 예시
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.dequeue())  # Output: 1
print(queue.peek())     # Output: 2
print(queue.is_empty())   # Output: False

5. 시간 복잡도 또는 성능 특성

Enqueue: O(1) (일반적으로 리스트의 끝에 추가하므로)
Dequeue: O(n) (리스트의 맨 앞에서 제거하는 경우, 모든 요소를 한 칸씩 이동해야 함). collections.deque 를 사용하면 O(1)로 개선 가능하다.
Peek: O(1)
IsEmpty: O(1)

6. 실무 사용 사례

웹 서버에서 들어오는 요청을 처리하는 데 큐를 사용할 수 있다. 각 요청은 큐에 추가되고, 서버는 큐에서 요청을 하나씩 꺼내어 처리한다. 이를 통해 서버는 과부하를 방지하고 안정적인 서비스를 제공할 수 있다. 또한, 메시지 큐 (Message Queue) 시스템 (예: RabbitMQ, Kafka) 역시 큐의 원리를 기반으로 구축되어 비동기 통신과 마이크로서비스 간 연동을 지원한다.

7. 주의할 점

Deque 사용 고려: Python의 list 대신 collections.deque를 사용하면 양쪽 끝에서 삽입/삭제 연산이 모두 O(1)이 되어 성능을 향상시킬 수 있다.
큐 용량 제한: 무한히 큐에 요소를 추가하면 메모리 부족 문제가 발생할 수 있으므로, 큐의 최대 크기를 설정하고 관리하는 것이 중요하다.
동기화 문제: 멀티스레드 환경에서 여러 스레드가 동시에 큐에 접근하는 경우 동기화 문제를 고려해야 한다. 락(Lock) 등을 사용하여 race condition을 방지해야 한다.

8. 핵심 정리

큐는 FIFO 원칙을 따르는 기본적인 자료구조이며, 다양한 시스템 및 알고리즘 구현에 활용된다. 성능 향상을 위해 collections.deque를 사용하는 것을 고려하고, 실무에서는 큐의 용량 제한과 동기화 문제를 주의해야 한다.