[파이썬] 큐

리스트를 사용한 큐

 

보통 파이썬에서는 deque를 사용해서 큐를 구현한다

리스트 내장 함수를 사용해서 큐 기능을 구현할 수도 있다.

q = []
q.append(1)
q.pop(0)

`append()`: 리스트 뒤쪽에 요소 넣기

`pop(0)`: 리스트 맨 앞 요소 꺼내기

 

하지만 append나 pop은 일반적으로 '가장 뒤쪽의 원소'를 기준으로 수행한다.

따라서 앞쪽에 있는 원소를 처리할 때에는 리스트에 포함된 데이터의 개수에 따라 많은 시간이 소요될 수도 있다는 점을 기억하자.

---

deque를 사용한 큐

 

데이터의 시작 부분이나 끝 부분에 데이터를 삽입하거나 삭제할 때 매우 효과적으로 사용될 수 있다.

시간복잡도가 O(1)이다.

from collections import deque

data = deque([2,3,4])
data.appendleft(1)
data.append(5)

print(data) #deque([1,2,3,4,5])
print(list(data)) #list로 자료형 변환

 

`appendleft()`: 첫번째 인덱스에 원소 삽입

`append()`: 마지막 인덱스에 원소 삽입

`popleft()`: 첫번째 인덱스 원소 삭제

 

큐 자료구조를 이용할 때는 `append()`를 사용하고,

원소 삭제할 때는 `popleft()`를 사용하면 된다.