Queue(큐)에 대해서 알아보기

안녕하세요, 여러분! 오늘은 자료구조의 또 다른 중요한 개념인 ‘큐(Queue)‘에 대해 알아보려고 합니다. 큐는 우리 일상생활에서도 자주 볼 수 있는 개념이에요. 한번 같이 살펴볼까요?

먼저, 큐가 무엇인지 간단히 설명드리겠습니다. 큐는 데이터를 저장하고 관리하는 방법 중 하나로, ‘선입선출(First-In-First-Out, FIFO)’ 원칙을 따릅니다. 쉽게 말해, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조예요.

실생활에서 큐의 예를 찾아볼까요? 바로 은행이나 음식점의 대기줄이에요. 먼저 온 사람이 먼저 서비스를 받고 나가는 것처럼, 큐도 먼저 들어온 데이터가 먼저 처리되어 나갑니다.

이해를 돕기 위해 큐의 구조를 그림으로 표현해 보겠습니다.

FrontRear

이 그림에서 볼 수 있듯이, 큐는 한쪽 끝(Rear)에서 데이터를 넣고, 다른 쪽 끝(Front)에서 데이터를 뺍니다. 마치 줄을 서는 것처럼 새로운 데이터는 뒤에 추가되고, 처리될 데이터는 앞에서부터 빠져나가는 거죠.

이제 큐의 주요 연산들에 대해 자세히 알아볼까요?

Enqueue (삽입) 연산 Enqueue는 큐의 뒤쪽(Rear)에 새로운 요소를 추가하는 연산입니다. 마치 줄의 맨 뒤에 새로운 사람이 서는 것과 같아요. 이 연산은 항상 O(1)의 시간 복잡도를 가집니다. 즉, 큐의 크기와 상관없이 항상 일정한 시간이 걸린다는 뜻이에요.
Dequeue (제거) 연산 Dequeue는 큐의 앞쪽(Front)에서 요소를 제거하고 반환하는 연산입니다. 줄의 맨 앞 사람이 서비스를 받고 나가는 것과 같죠. 이 연산 역시 O(1)의 시간 복잡도를 가집니다.
Front (or Peek) 연산 Front는 큐의 맨 앞에 있는 요소를 확인하는 연산입니다. Dequeue와 달리 요소를 제거하지 않고 단순히 어떤 요소가 맨 앞에 있는지만 살펴봅니다. 이것도 O(1)의 시간 복잡도를 가집니다.
IsEmpty 연산 IsEmpty는 큐가 비어있는지 확인하는 연산입니다. 큐에 요소가 하나도 없으면 true를, 그렇지 않으면 false를 반환합니다. 이 연산 역시 O(1)의 시간 복잡도를 가집니다.

이제 파이썬으로 큐를 어떻게 구현하는지 살펴볼까요? 파이썬에서는 리스트를 사용해 간단히 큐를 구현할 수 있습니다. 하지만 더 효율적인 구현을 위해 파이썬의 collections 모듈에 있는 deque를 사용하는 것이 좋습니다.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()

    def front(self):
        if not self.is_empty():
            return self.items[0]

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

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

# 큐 사용 예시
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 출력: 1
print(queue.front())    # 출력: 2
print(queue.size())     # 출력: 2

이 코드에서 deque를 사용한 이유는 popleft() 메서드 때문입니다. 일반 리스트의 pop(0)은 O(n)의 시간 복잡도를 가지지만, deque의 popleft()는 O(1)의 시간 복잡도를 가집니다. 따라서 큐의 모든 연산이 O(1)의 시간 복잡도를 갖게 되어 매우 효율적입니다.

큐는 실제로 많은 곳에서 사용됩니다. 몇 가지 예를 들어볼까요?

프로세스 스케줄링: 운영체제에서 실행 대기 중인 프로세스들을 관리할 때 사용합니다.
너비 우선 탐색(BFS): 그래프나 트리 구조에서 노드를 탐색할 때 사용합니다.
캐시(Cache) 구현: 웹 브라우저의 방문 기록 등을 관리할 때 사용할 수 있습니다.
버퍼(Buffer): 데이터를 한 곳에서 다른 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역을 구현할 때 사용합니다.

여러분, 이제 큐에 대해 어느 정도 이해가 되셨나요? 처음에는 조금 낯설게 느껴질 수 있지만, 실제로 우리 일상 생활에서도 자주 볼 수 있는 개념이랍니다.

큐를 더 잘 이해하기 위해 직접 실습해보는 것은 어떨까요? 예를 들어, 간단한 프린터 대기열 시뮬레이션을 만들어보세요. 문서를 큐에 추가하고, 프린트하는 과정을 구현해보면 큐의 동작 원리를 더 깊이 이해할 수 있을 거예요.

큐는 단순해 보이지만 매우 강력한 자료구조입니다. 이를 잘 이해하고 활용하면 복잡한 문제도 효율적으로 해결할 수 있게 됩니다. 앞으로 알고리즘 문제를 풀거나 프로그램을 개발할 때 큐를 활용할 수 있는 상황이 없는지 한 번씩 생각해보세요. 여러분의 문제 해결 능력이 한층 더 성장할 거예요!

다음에는 큐의 변형된 형태인 ‘우선순위 큐(Priority Queue)‘나 ‘양방향 큐(Deque)‘에 대해 알아보겠습니다.