[파이썬/자료구조] 큐(queue) 덱(deque)

[파이썬] 큐(queue)

 

큐는 선입선출, FIFO(First In First Out)

 

list

append : 마지막에서 삽입

pop : 마지막꺼 제거

pop(n) : n번째 인덱스 값 제거

insert(n, x) : n번째 인덱스에 x값 삽입

queue = [1, 2, 3]
queue.append(4)
print(queue)

queue.pop()
print(queue)

queue.pop(0)
print(queue)

queue.insert(0, 3)
print(queue)

[1, 2, 3, 4]
[1, 2, 3]
[2, 3]
[3, 2, 3]

 

그러나 list는 무작위 접근(random access)에 최적화된 자료 구조이며 시간 복잡도가 O(N)이므로 데이터가 많아질 수록 느려짐.

 

deque

double-ended queue

데이터를 양방향에서 추가, 제거 가능함.

popleft() : 첫번째 데이터 제거가능

appendleft(x) : 첫번째 인덱스에 x값 삽입

from collections import deque
queue = deque([1, 2, 3])
queue.append(4)
print(queue)

queue.popleft()
print(queue)

queue.pop()
print(queue)

queue.appendleft(5)
print(queue)

deque([1, 2, 3, 4])
deque([2, 3, 4])
deque([2, 3])
deque([5, 2, 3])

 

popleft(), appendleft()는 시간 복잡도가 O(1)이므로 list의 경우보다 빠름.

그러나 무작위 접근(random access)의 시간 복잡도가 O(N)이다.

내부적으로 linked list를 사용하고 있기 때문에 i번째 데이터에 접근하려면 맨 앞, 뒤부터 i번의 순회(iteration)가 필요하기 때문이다.