[자료구조] 큐(Queue)

자료구조 큐(Queue)에 대해 알아보겠습니다. 큐는 프로그램에서 자주 사용되는 자료구조 중 하나로, 다양한 분야에서 효율적으로 데이터를 처리하는 데 유용합니다.

 

큐란?

큐(Queue)는 선입선출(FIFO, First In First Out) 방식을 따르는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 처리됩니다. 마치 줄 서기와 같은 개념으로, 줄의 앞쪽부터 순서대로 처리되는 구조를 떠올리시면 됩니다.

 

큐의 특징

1. FIFO(First In, First Out):
   • 먼저 삽입된 데이터가 먼저 삭제됩니다.
   • 예: 대기열, 프린터 작업, 고객 서비스 센터의 대기 시스템 등.
2. 두 가지 주요 연산:
   • Enqueue: 큐의 끝에 데이터를 추가.
   • Dequeue: 큐의 앞에서 데이터를 제거.
3. 방향성:
   • 한쪽 끝에서만 데이터가 추가되고, 반대쪽 끝에서만 데이터가 제거됩니다.

 

큐의 구현

큐는 배열이나 연결 리스트로 구현할 수 있습니다. Python을 사용하여 간단한 큐를 구현해 보겠습니다.

1. 리스트를 이용한 큐 구현

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

    def enqueue(self, item):
        self.queue.append(item)  # 데이터 추가

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)  # 가장 앞의 데이터 제거
        else:
            return "Queue is empty!"

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

    def peek(self):
        if not self.is_empty():
            return self.queue[0]  # 가장 앞의 데이터 확인
        else:
            return "Queue is empty!"

    def size(self):
        return len(self.queue)  # 큐의 크기 반환

# 사용 예제
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())  # 1 출력
print(q.peek())     # 2 출력
print(q.size())     # 2 출력

 

2. collections.deque를 이용한 큐 구현

Python의 collections 모듈에는 큐를 효율적으로 처리할 수 있는 deque(Double-Ended Queue) 자료구조가 있습니다.

from collections import deque

queue = deque()

queue.append(1)  # Enqueue
queue.append(2)
queue.append(3)

print(queue.popleft())  # Dequeue: 1 출력
print(queue[0])         # Peek: 2 출력
print(len(queue))       # Size: 2 출력

deque는 양쪽에서 데이터를 추가/삭제할 수 있지만, 큐처럼 사용하려면 한쪽 끝만 사용하면 됩니다.

 

큐의 활용 사례

큐는 다음과 같은 상황에서 유용하게 사용됩니다.

1. 운영체제의 프로세스 스케줄링:
   • 작업이 완료된 순서대로 프로세스를 처리합니다.
2. 네트워크 데이터 전송:
   • 패킷이 전송된 순서대로 처리됩니다.
3. 웹 브라우저의 요청 처리:
   • 사용자의 요청을 순서대로 처리합니다.
4. 그래프 탐색:
   • BFS(너비 우선 탐색)에서 큐를 활용합니다.