큐 자료구조 이론 및 예제 (python)

큐 자료구조

• 큐는 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 
• 입구가 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다. 
• 대기열이라고 생각하면 쉽다.

 

큐 구현 방법

1) collection 모듈의 deque 객체 활용

• 큐는 스택과 같이 리스트로 구현할 수 있다. 하지만 리스트로 사용할 경우 pop(0)은 시간복잡도 O(N)를 가지고 있고,  popleft()은 시간복잡도 O(1)을 가지고 있다. 따라서 popleft()를 쓰는게 더 효율적이기 때문에 deque를 사용한다.
• 시간복잡도는 O(1)이다.
•  deque은 'double-ended queue'의 줄임말로서 스택과 큐를 합친 것과 같이 양방향에서 데이터를 삽입 및 추출할 수 있는 자료형이다. deque은 'deck'(덱)으로 발음한다. 

2) queue 모듈의 Queue 클래스 활용

큐 구현 예제 (파이썬)

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

from collections import deque

queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

 

• 입력을 위해서 append()를 사용하고 출력을 위해 popleft()를 사용한다.
• append()는 원소를 오른쪽 즉, 맨 마지막에 삽입한다.
• popleft()는 원소를 왼쪽 즉, 맨 처음부터 뺀다.