[Python] 알고리즘 개념8 - 큐(Queue)

 

 

🚀 1. 큐(Queue)란?

**큐(Queue)**는 데이터를 순서대로 저장하고 꺼내는 자료구조로, FIFO(First In, First Out, 선입선출) 원칙을 따릅니다.
➡ 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 새로운 데이터는 뒤(rear)에서 추가(Enqueue) 되고, 기존 데이터는 앞(front)에서 제거(Dequeue) 됩니다.
 
💡 큐의 특징

• 선입선출(FIFO): 먼저 추가된 데이터가 먼저 제거됨
• 데이터가 한쪽 끝(뒤)에서 추가되고, 다른 한쪽 끝(앞)에서 제거됨
• 배열(Array)과 달리, 중간 삽입/삭제가 어려움
• 대기열, 작업 스케줄링, 네트워크 패킷 처리 등에 활용

 
📌 큐의 예시

• 은행 창구 대기줄: 먼저 온 손님이 먼저 창구에서 서비스를 받음
• 프린터 작업 대기열: 먼저 요청된 인쇄 작업이 먼저 실행됨
• 운영체제의 작업 스케줄링: 먼저 도착한 프로세스가 먼저 실행됨

➡ 큐는 데이터를 순서대로 처리해야 하는 상황에서 유용하게 사용됩니다.

---

 

 

🚀 2. 큐의 동작 원리

큐는 enqueue(추가)와 dequeue(제거) 연산을 사용하여 데이터를 관리합니다.
 
연산 설명

enqueue(item)	큐의 끝(뒤)에 새로운 요소 추가
dequeue()	큐의 앞에서 요소 제거 후 반환
peek()	큐의 앞 요소를 확인(제거하지 않음)
is_empty()	큐가 비어 있는지 확인

💡 큐는 리스트로 구현할 수도 있지만, collections.deque를 사용하면 더 효율적입니다.
➡ 큐는 데이터를 순차적으로 처리하는 데 최적화된 구조입니다.

---

 

 

🚀 3. 큐 구현하기

 

✅ 리스트(List)로 큐 구현 (비추천)

Python의 리스트를 이용하여 큐를 구현할 수 있지만, 성능 문제가 발생할 수 있습니다.

queue = []

# 데이터 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # 출력: [1, 2, 3]

# 데이터 제거 (dequeue)
print(queue.pop(0))  # 출력: 1
print(queue.pop(0))  # 출력: 2
print(queue)  # 출력: [3]

💡 리스트의 pop(0)은 O(n) 연산이므로, 큐의 효율성이 떨어질 수 있습니다.
➡ 대안으로 collections.deque를 사용하면 성능을 더 최적화할 수 있습니다.

---

 

✅ collections.deque로 큐 구현 (추천)

collections.deque는 **양방향 큐(double-ended queue)**로, 리스트보다 큐 연산에 최적화되어 있습니다.

from collections import deque

queue = deque()

# 데이터 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # 출력: deque([1, 2, 3])

# 데이터 제거 (dequeue)
print(queue.popleft())  # 출력: 1
print(queue.popleft())  # 출력: 2
print(queue)  # 출력: deque([3])

💡 deque는 리스트보다 빠르고, 메모리 효율성이 좋습니다.
➡ 큐 연산을 효율적으로 수행하려면 collections.deque를 사용하는 것이 좋습니다.

---

 

 

🚀 4. 큐의 활용 예제

 

✅ 1) BFS(너비 우선 탐색) 구현

📌 문제: 그래프에서 BFS를 사용하여 모든 노드를 방문하세요.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(graph[node])

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

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

💡 큐를 사용하면 BFS 탐색을 효율적으로 구현할 수 있습니다.
➡ 큐의 선입선출(FIFO) 특성을 활용하여 방문할 노드를 차례로 처리합니다.

---

 

 

✅ 2) 프로세스 스케줄링 시뮬레이션

📌 문제: CPU가 여러 개의 프로세스를 처리할 때, 먼저 도착한 프로세스를 먼저 실행하도록 시뮬레이션하세요.

from collections import deque

def process_scheduling(processes):
    queue = deque(processes)
    while queue:
        process = queue.popleft()
        print(f"프로세스 {process} 실행")

# 프로세스 리스트
process_list = ['P1', 'P2', 'P3', 'P4']
process_scheduling(process_list)

💡 큐를 사용하면 프로세스를 순서대로 실행할 수 있습니다.
➡ 운영체제의 프로세스 관리에서 큐는 필수적인 역할을 합니다.

---

 

 

✅ 마무리 정리

• **큐(Queue)**는 FIFO(First In, First Out, 선입선출) 방식으로 동작하는 자료구조입니다.
• 주요 연산: enqueue(추가), dequeue(제거), peek(확인), is_empty(비어있는지 확인)
• 큐 구현 방법:
  • 리스트(list.append(), list.pop(0)) 사용 가능하지만 비효율적일 수 있음
  • collections.deque를 사용하면 더 효율적인 큐 구현 가능
• 큐 활용 예제:
  • BFS(너비 우선 탐색)
  • 운영체제의 프로세스 스케줄링
  • 네트워크 패킷 처리, 작업 대기열(프린터 스풀러) 등