Stack, queue, deque ve ring buffer

Stack LIFO, queue FIFO sözleşmesi sunar; deque iki ucu destekler. Stack undo, parantez eşleme ve explicit DFS için uygundur. Queue BFS ve iş sırası için kullanılır; işlerin FIFO alınması çok iş parçacığında FIFO tamamlanacakları anlamına gelmez.

Ring buffer sabit kapasiteli dizide head/tail indekslerini mod capacity ile sarar. Boş/dolu ayrımı için size sayacı, bir boş slot veya nesil biti gerekir. Üzerine yazma, bloklama veya reddetme davranışlarından hangisinin geçerli olduğunu tanımla. Queue implementasyonunda dizinin başını silmek yerine indeks ilerletmek kopyalamayı önler.

Monotonic deque, pencere maksimumunu tutarken artık cevap olamayacak küçük eski adayları çıkarır. Her indeks en fazla bir kez girip bir kez çıkar; iç içe while görünmesine rağmen toplam O(n)'dir. Bu, amortize analiz ile invariant'ın birlikte kullanıldığı güçlü bir örnektir. Empty pop ve capacity sınırları test edilmelidir.

from collections import deque

def window_max(a, k):
    if not 1 <= k <= len(a):
        raise ValueError("invalid window")
    q, out = deque(), []
    for i, x in enumerate(a):
        while q and q[0] <= i-k: q.popleft()
        while q and a[q[-1]] <= x: q.pop()
        q.append(i)
        if i >= k-1: out.append(a[q[0]])
    return out
assert window_max([2,1,5,3], 3) == [5,5]