1. 가장 먼저 넣은 값을 가장 먼저 뺄 때(queue, 선입선출, FIFO)
이 경우 deque()가 흔히 사용한다. deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하거나 제거할 수 있다. queue를 구현하려면 넣은 방향과 반대 방향에서 제거되도록 하면 된다.
from collections import deque
que = deque()
que.append(x) #오른쪽에 추가
a = que.popleft() #왼쪽에서 제거. a는 가장 먼저 추가된 요소or
from collections import deque
que = deque()
que.appendleft(x) #왼쪽에 추가
a = que.popleft() #오른쪽에서 제거2. 가장 나중에 넣은 값을 가장 먼저 뺄 때(stack, 후입선출, LIFO)
deque()는 양방향에서 추가 및 제거가 가능하므로 스택도 구현 가능하다. 넣은 방향에서 제거되도록 하면 된다.
from collections import deque
que = deque()
que.append(x) #오른쪽에 추가
a = que.pop() #오른쪽에서 제거. a는 가장 나중에 추가된 요소or
from collections import deque
que = deque()
que.appendleft(x) #오른쪽에 추가
a = que.popleft() #오른쪽에서 제거3. 가장 작거나 큰 값을 가장 먼저 뺄 때(priority queue)
heapq가 흔히 사용된다.
heap은 최댓값,최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다.
최대 힙(maxp heap)의 경우는 부모 노드의 키가 자식 노드의 키보다 크거나 같고, 최소 힙(min heap)은 반대이다.
heapq는 최소 힙을 사용한 모델이다. 즉, 가장 작은 값이 가장 먼저 제거될 대상이다.
import heapq #deque와 다르게 기본모듈이 아니다
q=[] #heapq의 베이스가 될 리스트
heapq.heappush(q,x)
a= heapq.heappop(q) #a는 q안의 요소 중 가장 작은 값heapq는 deque와 다르게 heap을 구현할 베이스 리스트가 필요하며, 내장함수를 사용할때마다 그 리스트를 인자로 전달해야한다. 이 때, 리스트는 heap트리로 구현되어 있으므로 정렬돼있을거라고 착각하지 말자.
위에서 x 자리에는 튜플이 들어갈 수 있으며, 이 경우 튜플의 첫번째 요소를 우선순위 기준으로 pop순서가 결정된다.
#최대 힙의 구현
heapq는 최대힙의 구현을 지원하지 않으므로 x에 음의 부호를 붙여 크기를 바꿔주는 방식으로 최대 힙의 구현이 가능하다.
import heapq #deque와 다르게 기본모듈이 아니다
q=[] #heapq의 베이스가 될 리스트
heapq.heappush(q,-x)
a= -1*heapq.heappop(q) #a는 q안의 요소 중 가장 큰 값혹은, 위에서 설명한 튜플을 사용해도 된다.
import heapq #deque와 다르게 기본모듈이 아니다
q=[] #heapq의 베이스가 될 리스트
heapq.heappush(q,(-x,x))
a= heapq.heappop(q)[1] #a는 q안의 요소 중 가장 큰 값