큐 (자료 구조)

큐(queue)는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하고 관리하는 선형 자료 구조이다. 큐에서는 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.

개요

큐는 한쪽 끝에서는 데이터를 삽입(Enqueue)하고, 다른 한쪽 끝에서는 데이터를 삭제(Dequeue)하는 방식으로 동작한다. 이처럼 입출력 방향이 분리되어 있어, 데이터가 들어간 순서대로 처리되어야 하는 상황에서 적합하다. 일상적인 예로는 줄 서기(대기열)가 있다.

주요 연산

• Enqueue
  • 큐의 뒤쪽(Rear) 끝에 새로운 데이터를 추가하는 연산.
• Dequeue
  • 큐의 앞쪽(Front) 끝에서 데이터를 제거하고 반환하는 연산.
• Peek (Front)
  • 큐의 앞쪽에 있는 데이터를 삭제하지 않고 확인하는 연산.
• isEmpty
  • 큐가 비어 있는지 확인하는 연산.
• isFull (고정 크기 큐의 경우)
  • 큐가 가득 찼는지 확인하는 연산.

특징

• 선입선출(FIFO) 방식을 따른다.
• 데이터가 들어간 순서대로 처리된다.
• 일반적으로 배열이나 연결 리스트를 사용하여 구현된다.
• 고정 크기의 큐에서는 오버플로우(Overflow)나 언더플로우(Underflow) 상태를 관리해야 한다.

종류

• 선형 큐(Linear Queue)
  • 단순히 삽입과 삭제를 선형으로 처리하는 큐.
• 원형 큐(Circular Queue)
  • 큐의 양 끝을 연결하여 공간을 재활용할 수 있도록 한 큐.
• 우선순위 큐(Priority Queue)
  • 삽입된 순서가 아니라 우선순위(priority)에 따라 요소를 처리하는 큐.
• 이중 큐(Deque, Double-Ended Queue)
  • 양쪽 끝에서 모두 삽입과 삭제가 가능한 큐.

활용 예시

• 프로세스 스케줄링(운영체제)
• 프린터 작업 대기열
• 네트워크 패킷 처리
• BFS(너비 우선 탐색) 알고리즘에서 노드 탐색
• 실시간 데이터 스트림 처리

큐와 스택의 차이

• 큐: 선입선출(FIFO) 방식
• 스택: 후입선출(LIFO, Last In First Out) 방식

간단한 구현 예시

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

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("peek from empty queue")

    def size(self):
        return len(self.items)

# 사용 예시
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 출력: 10
print(q.peek())     # 출력: 20

같이 보기

• 스택
• 우선순위 큐
• 원형 큐
• 이중 큐
• 연결 리스트

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.