Python에서 큐 구현

Python에서 큐 구현

Python에서는 리스트나 **deque**를 사용하여 큐를 구현할 수 있습니다. deque는 큐를 효율적으로 구현하기 위해 설계되었으며, 리스트를 사용했을 때 발생할 수 있는 성능 문제를 해결할 수 있습니다.

1. 리스트를 사용한 큐 구현 (비효율적)

리스트에서 pop(0)은 큐의 앞에서 항목을 제거하는 데 O(n)의 시간 복잡도가 걸립니다. 따라서 큐를 구현할 때 성능이 중요한 경우에는 deque를 사용하는 것이 좋습니다.

# 리스트를 사용한 큐 구현
queue = []

# 큐에 항목 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

print("현재 큐:", queue)  # [1, 2, 3]

# 큐에서 항목 제거 (dequeue)
first_item = queue.pop(0)  # 첫 번째 항목을 제거
print("디큐한 항목:", first_item)  # 1
print("현재 큐:", queue)  # [2, 3]

2. deque를 사용한 큐 구현 (효율적)

deque는 양쪽 끝에서 빠르게 추가하고 제거할 수 있는 자료형이므로 큐를 구현할 때 더 효율적입니다. append()와 popleft()를 사용하여 큐의 끝에서 데이터를 추가하고, 앞에서 데이터를 제거할 수 있습니다.

from collections import deque

# deque를 사용한 큐 구현
queue = deque()

# 큐에 항목 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

print("현재 큐:", queue)  # deque([1, 2, 3])

# 큐에서 항목 제거 (dequeue)
first_item = queue.popleft()  # 첫 번째 항목을 제거
print("디큐한 항목:", first_item)  # 1
print("현재 큐:", queue)  # deque([2, 3])

FIFO 큐의 동작

• enqueue (입구): append()를 사용하여 큐의 뒤쪽에 항목을 추가합니다.
• dequeue (출구): popleft()를 사용하여 큐의 앞쪽에서 항목을 제거합니다.

결론

• FIFO는 큐(Queue) 자료구조를 의미하며, **deque**를 사용하여 효율적으로 구현할 수 있습니다.
• deque는 양쪽 끝에서 빠르게 항목을 추가하거나 제거할 수 있기 때문에, 큐 구현에 적합합니다.