Queues

Queues — FIFO

from collections import deque

# First In First Out
# enqueue at back, dequeue from front -- both O(1)

class Queue:
    def __init__(self): self._data = deque()
    def enqueue(self, x): self._data.append(x)       # O(1)
    def dequeue(self):    return self._data.popleft() # O(1)
    def peek(self):       return self._data[0]        # O(1)
    def is_empty(self):   return len(self._data) == 0

# Priority Queue (min-heap)
import heapq
pq = []
heapq.heappush(pq, (1, 'high'))
heapq.heappush(pq, (3, 'low'))
heapq.heappush(pq, (2, 'medium'))
print(heapq.heappop(pq))  # (1, 'high')

# Deque (double-ended queue)
d = deque([1,2,3])
d.appendleft(0)   # O(1)
d.popleft()       # O(1)
d.append(4)       # O(1)
d.pop()           # O(1)

# Sliding window max -- monotonic deque
def sliding_max(nums, k):
    result = []
    dq = deque()  # indices, decreasing values
    for i, n in enumerate(nums):
        while dq and dq[0] < i-k+1: dq.popleft()
        while dq and nums[dq[-1]] < n: dq.pop()
        dq.append(i)
        if i >= k-1: result.append(nums[dq[0]])
    return result