자료구조 - Queue

큐 (Queue)

Queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다.

• enqueue : Queue의 rear(뒤)에서 데이터를 추가하는 것
• dequeue : Queue의 front(앞)에서 데이터를 꺼내는 것

구현 방법으로는 List와 Linked List기반으로 구현할 수 있습니다.

List 기반 구현

Python에서 Queue를 가장 간단하게 구현하는 방법은 list를 이용하는 것입니다.

list의 append 메소드를 사용하면 맨 뒤에 데이터를 추가할 수 있으며

list의 pop 메소드에서 인덱스를 지정하여 사용하면 맨 앞에 데이터를 꺼낼 수 있기 때문입니다.

q = []

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]

# dequeue O(n)
q.pop(0) # [2, 3]
q.pop(0) # [3]

Linked list 기반 구현

Python에서 정의된 deque의 구조를 보면 doubly linked list로 구현되어 있습니다.

deque는 맨 앞, 맨 뒤 모두 데이터의 삽입과 제거가 가능한 자료구조입니다.

deque의 모든 연산은 O(1)의 시간복잡도를 갖습니다.

from collections import deque

q = deque()

# enqueue O(1)
q.append(1)     # [1]
q.append(2)     # [1, 2]
q.append(3)     # [1, 2, 3]
q.appendleft(0) # [0, 1, 2, 3]

# dequeue O(1)
q.popleft() # [1, 2, 3]
q.popleft() # [2, 3]
q.pop()     # [2]

 

따라서 Python에서 정의된 deque를 사용하는 것이 시간복잡도 부분에서 효율적이라고 볼 수 있습니다.