데크, 우선순위 큐

데크(Deque)

양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있는 추상 자료형(ADT).

우선순위 큐(Priority Queue)

어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형
ex) 최댓값 추출

Heap 구조와 관련이 깊으며, Dijkstra 알고리즘 등에 영향을 끼침.
python에서는 heapq로 구현됨.

해결가능한 문제) 백준 1655번 - 가운데를 말해요
https://www.acmicpc.net/problem/1655

import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
leftheap = []
rightheap = []
for i in range(n):
    num = int(input())
    if len(leftheap) == len(rightheap):
        hq.heappush(leftheap, -num)
    else:
        hq.heappush(rightheap, num)

    if rightheap and -leftheap[0] > rightheap[0]:
        left, right = hq.heappop(leftheap), hq.heappop(rightheap)
        hq.heappush(leftheap, -right)
        hq.heappush(rightheap, -left)
    print(-leftheap[0])

출처 : 파이썬 알고리즘 인터뷰