[Python] Dequeue 사용하기

큐는 어떤 자료구조인가?

큐는 자료의 선입선출, FIFO(First-In-First-Out)을 보장하는 자료구조이다. 흔히 줄을 서 있는 사람들을 생각하면 쉽게 이해할 수 있다. 먼저 줄을 선 사람이 먼저 줄에서 벗어나는 것과 같다.

 

 

Reference

https://www.youtube.com/watch?v=W3jNbNGyjMs

 

---

deque 객체

deque는 스택과 큐를 합친 자료구조이다. 가장자리에 원소를 넣거나 뺄 수 있다.

메서드	설명
deque(iterable, [, maxlen])	초기화 함수이다. iterable(리스트 등)을 인자로 건내면 이를 deque화 시켜준다.
append(x)	x를 덱의 오른쪽에 삽입한다.
popleft()	덱의 가장 왼쪽에 있는 원소를 덱에서 제거하고, 그 값을 리턴한다.
clear()	모든 원소를 지운다.

※ 큐 사용에 필요한 메서드만 나열함.

 

 

스택과 달리 큐를 list로 이용하지 않는 이유

스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

 

deque - Init

deque(iterable, [, maxlen])를 사용해 초기화한다.

from collections import deque

# 빈 큐 만들기
deque1 = deque()

# 원소가 있는 큐 만들기
deque2 = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소를 이보다 많이 넣으면 maxlen이 자동 갱신됨)
deque3 = deque(maxlen=5)

 

deque - append(x)

큐에 원소를 넣을때 사용한다.

my_deque = deque()
my_deque.append(3)

print(my_deque)

# deque([3])

 

deque - popleft()

큐에 원소를 제거할 때 사용한다.

my_deque = deque([1,2,3])

while my_deque:
    print("{}을/를 pop했습니다".format(my_deque.popleft()))

# 1을/를 pop했습니다
# 2을/를 pop했습니다
# 3을/를 pop했습니다

 

deque - clear()

모든 원소를 지운다.

my_deque = deque([1,2,3])

print("전:", my_deque)
my_deque.clear()
print("후:", my_deque)

# 전: deque([1, 2, 3])
# 후: deque([])

 

원소 수 알아내기

len() 함수를 사용한다.

my_deque = deque([1,2,3], maxlen=5)

print(len(my_deque))

# 3