[자료구조]파이썬 큐 자료구조 완벽 가이드: 기본 개념부터 실전 활용까지

큐(Queue)는 자료를 저장하는 방식 중 하나로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 구조를 가지고 있습니다. 큐는 일상생활에서도 많이 볼 수 있는 자료구조로, 예를 들어 은행의 대기 줄이 큐의 대표적인 예입니다. 이번 글에서는 파이썬에서 큐를 어떻게 구현하고 활용할 수 있는지 자세히 살펴보겠습니다.

≣ 목차

• 큐 자료구조란?📚
• 큐의 주요 연산🔄
• 큐의 종류🧩
• 파이썬에서 큐 구현 방법💻
• 큐의 활용 예시📊
• 큐의 장단점⚖️
• 핵심 내용👀

---

01. 큐 자료구조란?📚

큐 자료구조란 무엇인가?

큐(Queue)는 컴퓨터 과학에서 매우 중요한 자료구조 중 하나로, 데이터를 저장하고 관리하는 방법 중 하나입니다. 큐는 선입선출(FIFO, First In First Out) 구조를 따릅니다. 이는 먼저 들어온 데이터가 먼저 나가는 방식으로, 은행의 대기 줄이나 버스 정류장의 줄과 같은 일상생활에서도 쉽게 찾아볼 수 있는 구조입니다.

큐의 기본 원리와 작동 방식

큐는 두 가지 주요 연산인 삽입(Enqueue)과 삭제(Dequeue)로 구성됩니다. 삽입 연산은 새로운 데이터를 큐의 뒤(rear)로 넣는 것이고, 삭제 연산은 기존 데이터를 큐의 앞(front)에서 빼는 것입니다. 이 기본 원리를 통해 큐는 데이터를 효율적으로 관리하고 처리할 수 있습니다.

예를 들어, 은행의 대기 줄을 생각해봅시다. 새로운 고객이 오면 줄의 맨 뒤에 서게 되고, 줄의 맨 앞에 있는 고객이 먼저 창구로 이동해 서비스를 받습니다. 이와 같은 원리로 큐는 데이터의 순서를 유지하고, 차례대로 처리할 수 있도록 돕습니다.

큐는 단순하면서도 매우 강력한 자료구조로, 다양한 알고리즘과 프로그램에서 널리 사용됩니다. 예를 들어, 그래프 탐색 알고리즘인 BFS(Breadth-First Search)에서 큐는 중요한 역할을 합니다. 또한, 작업 스케줄링, 대기열 관리, 웹 서버 요청 처리 등 다양한 실생활 응용에서도 큐는 매우 유용합니다.

---

큐와 스택의 차이점은 무엇일까요?

큐는 선입선출(FIFO) 방식으로 데이터를 처리하고, 스택은 후입선출(LIFO) 방식으로 데이터를 처리합니다.
스택에 관한 내용은 아래 포스팅을 참고해 주세요😁

[자료구조]파이썬 스택 구조 완벽 가이드: 개념, 구현 및 활용 예제

---

02. 큐의 주요 연산🔄

큐 자료구조에서는 몇 가지 주요 연산이 있습니다. 이 연산들을 통해 큐의 기본 동작을 이해할 수 있습니다.
삽입(Enqueue), 삭제(Dequeue), 프론트(Front), 후방(Rear) 연산 외에도 큐의 상태를 확인하고 데이터를 접근하는 연산인 is_full, peek, size 연산에 대해 설명하겠습니다.

삽입(Enqueue) 연산

삽입 연산은 큐의 뒤(rear)로 데이터를 넣는 작업입니다. 새로운 데이터는 항상 큐의 마지막 위치에 추가됩니다. 이를 통해 큐는 데이터가 들어온 순서대로 처리할 수 있게 됩니다.

from collections import deque  # collections 모듈에서 deque 클래스를 가져옵니다.

queue = deque()  # 빈 큐를 생성합니다.

# 삽입(Enqueue)
queue.append(3)  # 큐의 뒤에 3을 추가합니다.

---

삭제(Dequeue) 연산

삭제 연산은 큐의 앞(front)에서 데이터를 빼는 작업입니다. 큐의 가장 앞에 있는 데이터가 제거되고 반환됩니다. 이를 통해 큐는 선입선출(FIFO) 원칙을 따르게 됩니다.

# 삭제(Dequeue)
queue.popleft()  # 큐의 앞에서 3을 제거하고 반환합니다.

---

프론트(Front) 연산

프론트 연산은 큐의 가장 앞에 있는 데이터를 확인하는 작업입니다. 이 연산은 데이터를 제거하지 않고 현재 큐의 첫 번째 요소를 반환합니다.

# 프론트(Front)
front = queue[0]  # 큐의 가장 앞에 있는 요소를 확인합니다.

---

후방(Rear) 연산

후방 연산은 큐의 가장 뒤에 있는 데이터를 확인하는 작업입니다. 이 연산 역시 데이터를 제거하지 않고 현재 큐의 마지막 요소를 반환합니다.

# 후방(Rear)
rear = queue[-1]  # 큐의 가장 뒤에 있는 요소를 확인합니다.

---

큐의 빈 상태 확인

큐가 비어 있는지 확인하는 것도 중요한 연산 중 하나입니다. 이를 통해 삭제 연산 또는 프론트 연산을 수행하기 전에 큐가 비어 있는지 여부를 확인할 수 있습니다.

# 큐가 비어 있는지 확인
is_empty = len(queue) == 0  # 큐의 길이가 0인지 확인하여 빈 상태를 확인합니다.
print(is_empty)  # 출력: False

---

큐의 꽉 찬 상태 확인

고정 크기의 큐에서는 큐가 꽉 찬 상태인지 확인하는 것이 중요합니다. 이는 CircularQueue와 같은 고정 크기 큐에서 유용합니다.

class CircularQueue:
    def __init__(self, size):
        self.size = size  # 큐의 크기를 설정합니다.
        self.queue = [None] * size  # 크기만큼의 리스트를 생성하여 큐를 초기화합니다.
        self.front = self.rear = -1  # front와 rear를 초기화합니다.

    def is_full(self):
        # rear 다음 위치가 front인 경우 큐가 가득 찬 상태입니다.
        return (self.rear + 1) % self.size == self.front

# 사용 예제
cq = CircularQueue(3)  # 크기가 3인 환형 큐를 생성합니다.
print(cq.is_full())  # 출력: False

---

맨 앞의 요소 확인(Peek)

Peek 연산은 큐의 맨 앞(front) 요소를 제거하지 않고 확인하는 작업입니다. 이를 통해 데이터를 제거하지 않고 큐의 상태를 파악할 수 있습니다.

# 맨 앞의 요소 확인(Peek)
def peek(queue):
    if len(queue) > 0:  # 큐의 길이가 0보다 큰 경우
        return queue[0]  # 큐의 맨 앞 요소를 반환합니다.
    else:
        return "Queue is empty"  # 큐가 비어 있으면 메시지를 반환합니다.

print(peek(queue))  # 출력: 5

---

큐의 크기 확인(Size)

Size 연산은 큐에 현재 저장된 요소의 개수를 반환합니다. 이를 통해 큐의 크기를 쉽게 확인할 수 있습니다.

# 큐의 크기 확인(Size)
queue_size = len(queue)  # 큐의 현재 크기를 반환합니다.
print(queue_size)  # 출력: 1

---

03. 큐의 종류🧩

큐는 다양한 형태로 존재하며, 각기 다른 특성과 용도를 가집니다. 이번 섹션에서는 큐의 주요 종류와 그 특징을 살펴보겠습니다.

선입선출(FIFO) 큐

선입선출 큐는 가장 기본적인 형태의 큐입니다. 이름 그대로 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있습니다. 이는 일상생활에서 많이 볼 수 있는 줄 서기 시스템과 유사합니다. FIFO 큐는 삽입 연산과 삭제 연산이 일어나며, 삽입 연산은 큐의 뒤에서 이루어지고, 삭제 연산은 큐의 앞에서 이루어집니다.

큐의 기본 원리와 작동 방식

선입선출 큐의 기본 원리는 다음과 같습니다:

1. 삽입(Enqueue): 새로운 데이터는 항상 큐의 뒤(rear)에서 추가됩니다.
2. 삭제(Dequeue): 데이터는 항상 큐의 앞(front)에서 제거되고 반환됩니다.

파이썬에서 선입선출 큐 구현하기

파이썬에서는 collections 모듈의 deque 클래스를 사용하여 선입선출 큐를 쉽게 구현할 수 있습니다.

from collections import deque

queue = deque()

# 삽입(Enqueue)
queue.append('a')
queue.append('b')

# 삭제(Dequeue)
queue.popleft()  # 'a'
queue.popleft()  # 'b'

이 예제에서는 deque 클래스를 사용하여 큐를 생성하고, append() 메서드로 데이터를 삽입하며, popleft() 메서드로 데이터를 삭제합니다.

선입선출 큐의 활용 예시

선입선출 큐는 다양한 분야에서 활용됩니다. 몇 가지 예시는 다음과 같습니다:

1. 작업 스케줄링: 운영체제에서 프로세스를 스케줄링할 때, 먼저 요청된 작업이 먼저 처리되도록 하는 방식에 사용됩니다.
2. 프린터 대기열: 프린터는 요청된 순서대로 문서를 출력합니다. 이때 선입선출 큐를 사용하여 문서 출력 순서를 관리합니다.
3. 네트워크 패킷 처리: 라우터는 네트워크 패킷을 순서대로 처리해야 하며, 이때 선입선출 큐를 사용합니다.
4. 그래프 탐색 알고리즘: BFS(Breadth-First Search) 알고리즘에서 큐를 사용하여 탐색할 노드를 순서대로 처리합니다.

---

원형 큐(순환 큐)

원형 큐는 일반적인 선입선출(FIFO) 큐의 문제인 공간 낭비를 해결하기 위해 고안된 자료구조입니다. 일반적인 선입선출(FIFO) 큐와 달리, 원형 큐는 큐의 마지막 위치에 도달하면 다시 처음 위치로 돌아가 데이터를 저장합니다. 이를 통해 공간을 효율적으로 사용할 수 있습니다.
원형 큐의 원리를 알기 위해 먼저 선형 큐의 문제점 부터 확인해보겠습니다.

선형큐(Linear Queue)의 문제점

선형큐는 배열을 이용하여 구현된 큐로, 데이터를 넣고(enqueue) 뺄 때(dequeue) 각각의 끝에서만 작업이 가능합니다. 이러한 구조에서 발생할 수 있는 주요 문제점은 다음과 같습니다:

1. 공간 낭비: 선형큐에서 dequeue 연산을 수행할 때, 앞쪽의 데이터를 삭제한 후 남은 공간을 활용하지 못하고 남게 될 수 있습니다. 이로 인해 사용 가능한 큐의 공간이 줄어들어 공간의 낭비가 발생할 수 있습니다.
2. 오버플로우 문제: 큐의 앞부분이 비워진 후에도 큐에 데이터를 계속해서 추가하게 되면, 배열의 끝에 도달하게 되면서 오버플로우가 발생할 수 있습니다.

원형큐(Circular Queue)의 원리

원형큐는 선형큐의 문제점을 해결하기 위해 개발된 자료구조로, 배열을 원형으로 사용하여 데이터를 순환하면서 저장하는 방식입니다. 원형큐는 다음과 같은 특징을 가집니다.

원형 큐의 특징

1. 배열 인덱스 처리: 배열의 인덱스를 사용할 때 원형적으로 처리하여, 배열의 끝에 도달하면 다시 배열의 처음으로 돌아가는 방식을 취합니다. 이는 원형큐의 장점으로, 공간의 효율성을 높이며 오버플로우 문제를 방지합니다.
2. 공간 활용: 큐의 마지막 위치와 처음 위치가 연결되어 원형 구조를 이룹니다. 원형큐에서는 데이터를 순환하기 때문에, 큐의 앞쪽이 비워져도 데이터를 추가할 수 있어 공간 활용이 효율적입니다.
3. 포인터 사용: 원형큐는 front와 rear라는 두 개의 포인터를 사용하여 원형 배열을 관리합니다. front는 데이터가 제거되는 위치를 가리키고, rear는 데이터가 추가되는 위치를 가리킵니다.

원형 큐의 연산

1. 삽입(Enqueue): 데이터를 큐의 뒤쪽(rear)에 삽입합니다.
2. 삭제(Dequeue): 데이터를 큐의 앞쪽(front)에서 삭제하고 반환합니다.
3. 프론트(Front): 큐의 가장 앞에 있는 데이터를 확인합니다.
4. 후방(Rear): 큐의 가장 뒤에 있는 데이터를 확인합니다.
5. 빈 상태 확인: 큐가 비어 있는지 확인합니다.
6. 꽉 찬 상태 확인: 큐가 가득 찬 상태인지 확인합니다.

파이썬에서 원형 큐 구현하기

파이썬에서는 배열을 사용하여 원형 큐를 구현할 수 있습니다. 아래는 원형 큐의 구현 예제입니다.

class CircularQueue:
    def __init__(self, size):
        self.size = size  # 큐의 크기를 설정합니다.
        self.queue = [None] * size  # 크기만큼의 리스트를 생성하여 큐를 초기화합니다.
        self.front = self.rear = -1  # front와 rear를 초기화합니다.

    def is_full(self):
        # rear 다음 위치가 front인 경우 큐가 가득 찬 상태입니다.
        return (self.rear + 1) % self.size == self.front

    def is_empty(self):
        # front와 rear가 동일한 경우 큐가 비어 있는 상태입니다.
        return self.front == -1

    def enqueue(self, data):
        if self.is_full():
            print("Queue is full")
        elif self.is_empty():
            self.front = self.rear = 0  # 큐가 비어 있는 경우 front와 rear를 0으로 설정합니다.
            self.queue[self.rear] = data
        else:
            self.rear = (self.rear + 1) % self.size  # rear를 다음 위치로 이동합니다.
            self.queue[self.rear] = data

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        elif self.front == self.rear:
            temp = self.queue[self.front]
            self.front = self.rear = -1  # 큐에 하나의 요소만 남아 있는 경우 front와 rear를 초기화합니다.
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size  # front를 다음 위치로 이동합니다.
            return temp

    def front(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        return self.queue[self.front]

    def rear(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        return self.queue[self.rear]

# 사용 예제
cq = CircularQueue(3)  # 크기가 3인 환형 큐를 생성합니다.

# 큐에 데이터 삽입
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)

# 큐가 가득 찬 상태 확인
print(cq.is_full())  # 출력: True

# 큐에서 데이터 삭제
print(cq.dequeue())  # 출력: 1

# 큐에 데이터 삽입
cq.enqueue(4)

# 큐의 현재 상태 출력
print(cq.queue)  # 출력: [4, 2, 3]

# 큐의 front와 rear 요소 확인
print("Front element:", cq.queue[cq.front])  # 출력: Front element: 2
print("Rear element:", cq.queue[cq.rear])  # 출력: Rear element: 4

이 예제에서는 CircularQueue 클래스를 정의하여 환형 큐를 구현했습니다. 주요 연산으로는 enqueue(), dequeue(), is_full(), is_empty(), front(), rear()가 있습니다.

원형 큐의 활용 예시

원형 큐는 다양한 분야에서 활용될 수 있습니다. 몇 가지 예시는 다음과 같습니다:

1. 작업 스케줄링: 프로세서에서 반복적인 작업을 관리할 때 환형 큐를 사용하여 작업을 순환적으로 처리할 수 있습니다.
2. 네트워크 버퍼: 네트워크 장치에서 데이터 패킷을 순환적으로 저장하고 처리할 때 사용됩니다.
3. 라운드 로빈 스케줄링: 운영체제에서 여러 프로세스를 공정하게 스케줄링할 때 사용됩니다.

---

우선순위 큐

우선순위 큐(Priority Queue)는 데이터를 저장할 때 각각의 데이터에 우선순위를 부여하고, 우선순위가 높은 데이터가 낮은 데이터보다 먼저 처리되는 자료구조입니다. 이는 일반적인 큐(Queue)와 다르게 데이터가 들어온 순서가 아니라 우선순위가 높은 데이터가 먼저 나가는 특성을 가지고 있습니다.

파이썬에서는 우선순위 큐를 구현하기 위해 여러 가지 방법이 있지만, 가장 대표적인 방법은 heapq 모듈을 사용하는 것입니다. heapq 모듈은 최소 힙(min-heap)을 기본으로 제공하며, 최대 힙(max-heap)을 구현할 때는 우선순위의 부호를 바꿔서 활용합니다.

import heapq  # heapq 모듈을 가져옵니다.

class PriorityQueue:
    def __init__(self):
        self.queue = []  # 빈 큐를 생성합니다.
        self.index = 0  # 우선순위가 동일한 경우를 위한 인덱스를 초기화합니다.

    def enqueue(self, item, priority):
        # 우선순위가 높은 순으로 정렬하기 위해 음수 우선순위를 사용합니다.
        heapq.heappush(self.queue, (-priority, self.index, item))
        self.index += 1  # 인덱스를 증가시킵니다.

    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.queue)[-1]  # 가장 높은 우선순위의 항목을 제거하고 반환합니다.
        else:
            return "Priority Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0  # 큐가 비어 있는지 확인합니다.

# 사용 예제
pq = PriorityQueue()  # 우선순위 큐를 생성합니다.
pq.enqueue("task1", 1)  # 우선순위가 1인 작업을 추가합니다.
pq.enqueue("task2", 2)  # 우선순위가 2인 작업을 추가합니다.
print(pq.dequeue())  # 우선순위가 가장 높은 작업을 제거하고 반환합니다.
print(pq.dequeue())  # 다음 우선순위가 높은 작업을 제거하고 반환합니다.
print(pq.dequeue())  # 큐가 비어 있음을 반환합니다.

---

이중 끝 큐(Deque)

이중 끝 큐(Deque, Double-ended Queue) 즉 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.
이중 끝 큐는 일반적인 큐와 달리 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있어 더 유연한 데이터 구조를 제공합니다. Python에서는 collections 모듈의 deque 클래스를 사용하여 Deque를 구현할 수 있습니다.

Deque의 주요 연산

다음은 collections.deque를 사용한 Deque의 주요 연산과 그 예제입니다:

1. 삽입 연산

• append(): Deque의 뒤쪽에 요소를 추가합니다.
• appendleft(): Deque의 앞쪽에 요소를 추가합니다.

from collections import deque  # collections 모듈에서 deque 클래스를 가져옵니다.

d = deque()  # 빈 deque를 생성합니다.

# 뒤쪽에서 삽입(append)
d.append(1)  # Deque의 뒤쪽에 1을 추가합니다.
d.append(2)  # Deque의 뒤쪽에 2를 추가합니다.
print(d)  # 출력: deque([1, 2])

# 앞쪽에서 삽입(appendleft)
d.appendleft(3)  # Deque의 앞쪽에 3을 추가합니다.
print(d)  # 출력: deque([3, 1, 2])

2. 삭제 연산

• pop(): Deque의 뒤쪽에서 요소를 제거하고 반환합니다.
• popleft(): Deque의 앞쪽에서 요소를 제거하고 반환합니다.

# 뒤쪽에서 삭제(pop)
last_element = d.pop()  # Deque의 뒤쪽에서 요소를 제거하고 반환합니다.
print(last_element)  # 출력: 2
print(d)  # 출력: deque([3, 1])

# 앞쪽에서 삭제(popleft)
first_element = d.popleft()  # Deque의 앞쪽에서 요소를 제거하고 반환합니다.
print(first_element)  # 출력: 3
print(d)  # 출력: deque([1])

3. 맨 앞의 요소 확인(Peek)

# 맨 앞의 요소 확인
first_element = d[0]  # Deque의 맨 앞 요소를 확인합니다.
print(first_element)  # 출력: 1

4. 맨 뒤의 요소 확인

# 맨 뒤의 요소 확인
last_element = d[-1]  # Deque의 맨 뒤 요소를 확인합니다.
print(last_element)  # 출력: 1

5. Deque의 크기 확인

# Deque의 크기 확인
deque_size = len(d)  # Deque의 현재 크기를 반환합니다.
print(deque_size)  # 출력: 1

6. Deque의 빈 상태 확인

# Deque가 비어 있는지 확인
is_empty = len(d) == 0  # Deque의 길이가 0인지 확인하여 빈 상태를 확인합니다.
print(is_empty)  # 출력: False

이처럼 deque는 양쪽 끝에서 삽입과 삭제를 모두 지원하여 유연한 데이터 처리 기능을 제공합니다. 이러한 특성 덕분에 Deque는 다양한 알고리즘과 문제 해결에서 매우 유용하게 사용됩니다.

---

04. 파이썬에서 큐 구현 방법💻

파이썬에서 큐(Queue)를 구현하는 방법에는 여러 가지가 있지만, 가장 일반적이고 간단한 방법은 다음과 같습니다.

리스트를 사용한 큐 구현

리스트를 이용한 큐 구현은 가장 간단하고 직관적인 방법입니다. 다만, 리스트의 맨 앞에서 원소를 삭제하는 연산(pop(0))은 시간복잡도가 O(n)이기 때문에 많은 원소가 들어있는 큐에서는 비효율적일 수 있습니다.

class Queue:
    def __init__(self):
        """큐 초기화"""
        self.items = []  # 리스트를 이용하여 큐 구현

    def enqueue(self, item):
        """큐에 원소 추가"""
        self.items.append(item)  # 리스트의 끝에 원소 추가 (enqueue)

    def dequeue(self):
        """큐에서 원소 삭제 및 반환"""
        if not self.is_empty():
            return self.items.pop(0)  # 리스트의 맨 앞에서 원소 삭제 및 반환 (dequeue)
        else:
            return None

    def is_empty(self):
        """큐가 비어있는지 확인"""
        return len(self.items) == 0

    def size(self):
        """큐의 크기 반환"""
        return len(self.items)

위의 코드에서 enqueue 메서드는 큐의 끝에 원소를 추가하고(append) dequeue 메서드는 큐의 맨 앞에서 원소를 삭제하고 반환합니다(pop(0)). is_empty 메서드는 큐가 비어있는지 여부를 확인하고, size 메서드는 큐의 길이를 반환합니다.

---

collections.deque을 이용한 큐 구현

덱(deque)은 양쪽 끝에서 O(1) 시간복잡도로 원소를 추가하거나 삭제할 수 있는 자료구조입니다. 따라서 매우 효율적인 큐 구현 방법입니다.

from collections import deque

class Queue:
    def __init__(self):
        """큐 초기화"""
        self.items = deque()  # deque을 이용하여 큐 구현

    def enqueue(self, item):
        """큐에 원소 추가"""
        self.items.append(item)  # deque의 오른쪽에 원소 추가 (enqueue)

    def dequeue(self):
        """큐에서 원소 삭제 및 반환"""
        if not self.is_empty():
            return self.items.popleft()  # deque의 왼쪽에서 원소 삭제 및 반환 (dequeue)
        else:
            return None

    def is_empty(self):
        """큐가 비어있는지 확인"""
        return len(self.items) == 0

    def size(self):
        """큐의 크기 반환"""
        return len(self.items)

이 경우에도 enqueue 메서드는 덱의 오른쪽에 원소를 추가하고(append) dequeue 메서드는 덱의 왼쪽에서 원소를 삭제하고 반환합니다(popleft). 나머지 메서드는 리스트를 이용한 구현과 동일합니다.

# 리스트를 이용한 큐 사용 예시
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 출력: 1
print(q.size())     # 출력: 2

# deque를 이용한 큐 사용 예시
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 출력: 1
print(q.size())     # 출력: 2

이와 같이 파이썬에서는 리스트나 덱을 이용하여 간단하게 큐를 구현할 수 있습니다. 덱을 사용하는 경우 성능 면에서 더 우수하며, 대부분의 상황에서 권장되는 방법입니다.

---

05. 큐의 활용 예시📊

큐는 데이터를 일시적으로 저장하고, 그 순서대로 처리해야 할 때 매우 유용합니다. 아래 예시들은 큐가 다양한 분야에서 어떻게 활용되는지를 보여줍니다. BFS 알고리즘의 구현부터 작업 처리, 버퍼 관리까지 다양한 상황에서 큐가 필수적인 자료구조임을 보여줍니다.

작업 처리 큐 예시

컴퓨터 시스템에서 작업이 들어오면 처리할 때 큐가 사용됩니다. 예를 들어, 프린터 큐에서는 인쇄 요청이 들어온 순서대로 처리됩니다. 또한, 서버에서 클라이언트의 요청을 처리하는 작업 큐도 큐의 개념을 사용하여 구현될 수 있습니다.

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 추적합니다.
    queue = deque([start])  # 시작 노드를 큐에 추가합니다.

    while queue:
        vertex = queue.popleft()  # 큐의 앞에서 노드를 제거하고 반환합니다.
        if vertex not in visited:
            visited.add(vertex)  # 노드를 방문한 것으로 표시합니다.
            queue.extend(graph[vertex] - visited)  # 방문하지 않은 인접 노드를 큐에 추가합니다.

    return visited

# 예제 그래프
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

print(bfs(graph, 'A'))  # 출력: {'A', 'B', 'C', 'D', 'E', 'F'}

---

BFS (너비 우선 탐색)

그래프에서 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 큐를 사용하여 구현됩니다. BFS는 같은 레벨의 노드를 모두 방문한 후 다음 레벨로 넘어가기 때문에 큐가 자연스럽게 알고리즘의 구현에 적합합니다.

from collections import deque

def bfs(graph, start_node):
    """너비 우선 탐색(BFS) 알고리즘"""
    visited = []
    queue = deque([start_node])

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

    return visited

# 그래프와 시작 노드 정의
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

start_node = 'A'
print(bfs(graph, start_node))  # 출력: ['A', 'B', 'C', 'D', 'E', 'F']

---

버퍼 관리

입출력 속도가 다른 시스템에서 데이터를 버퍼링 할 때 큐를 사용하여 버퍼를 관리할 수 있습니다. 데이터가 도착한 순서대로 버퍼에 저장하고, 처리 속도에 맞게 버퍼에서 데이터를 읽어 처리하는 방식으로 사용됩니다.

from collections import deque
import time

class Buffer:
    def __init__(self, capacity):
        """버퍼 초기화"""
        self.buffer = deque()
        self.capacity = capacity

    def add_data(self, data):
        """데이터를 버퍼에 추가"""
        if len(self.buffer) < self.capacity:
            self.buffer.append(data)
        else:
            print("Buffer is full. Unable to add data.")

    def process_data(self):
        """버퍼에서 데이터를 꺼내서 처리"""
        if self.buffer:
            return self.buffer.popleft()
        else:
            print("Buffer is empty. No data to process.")

# 버퍼 사용 예시
buffer = Buffer(capacity=3)

for i in range(5):
    buffer.add_data(f"Data {i}")

while True:
    data = buffer.process_data()
    if data:
        print(f"Processing: {data}")
        time.sleep(1)  # 데이터 처리 시뮬레이션을 위한 sleep
    else:
        break

---

06. 큐의 장단점⚖️

장점

1. 순서 보장: 큐는 데이터가 들어온 순서대로 처리됩니다. 따라서 데이터의 순서가 중요한 경우에 유용하게 활용됩니다.
2. 구현이 간단: 기본적인 큐의 구현은 매우 간단합니다. 리스트나 덱을 이용하여 쉽게 구현할 수 있습니다.
3. 너비 우선 탐색(BFS) 구현: 그래프 알고리즘에서 너비 우선 탐색(BFS)을 구현할 때 필수적으로 사용됩니다. BFS는 큐의 원리를 기반으로 하며, 같은 레벨의 노드들을 먼저 탐색하는 특성을 가지고 있습니다.
4. 데이터 스트림 처리: 데이터가 계속적으로 들어오고, 일정한 속도로 처리되어야 할 때 큐를 사용하여 데이터를 관리하고 처리할 수 있습니다. 예를 들어, 버퍼 관리나 스트리밍 데이터 처리에서 유용합니다.

단점

1. 저장 공간의 한계: 배열 기반의 큐 구현에서는 저장 공간의 크기가 제한되어 있어서, 데이터가 많이 쌓일 경우 오버플로우(Overflow)가 발생할 수 있습니다.
2. 삽입 및 삭제 연산의 시간복잡도: 일반적으로 큐에서는 데이터의 삽입(enqueue) 및 삭제(dequeue) 연산이 상수 시간 O(1)에 수행됩니다. 하지만 배열 기반의 큐에서는 데이터를 삭제할 때마다 다른 모든 데이터를 한 칸씩 앞으로 당겨야 하는 경우가 발생할 수 있어, 최악의 경우에는 O(n)의 시간이 소요될 수 있습니다.
3. 접근의 제한: 큐는 FIFO 원칙에 따라 데이터에 접근할 때, 먼저 들어온 데이터부터 순서대로 처리합니다. 따라서 특정 데이터에 빠르게 접근하거나 삭제하기 위해서는 다른 자료구조(예: 해시맵)를 함께 사용해야 할 수 있습니다.

결론

큐는 데이터를 순서대로 처리해야 할 때 매우 유용한 자료구조입니다. 그러나 데이터의 접근 패턴이나 저장 공간의 제약 등을 고려하여 적절히 선택하고 사용해야 합니다. BFS와 같은 알고리즘 구현이나 데이터의 FIFO 처리가 필요한 경우에는 큐를 사용하는 것이 자연스럽고 효율적일 수 있습니다.

---

08. 핵심 내용👀