queue

Navbat — «birinchi kirgan birinchi chiqadi» (FIFO). Python’da collections.deque ishlating: ro‘yxatdan pop(0) O(n), deque.popleft() esa O(1).

from collections import deque

q = deque()
q.append(5)        # oxiriga
q.appendleft(1)    # boshiga
x = q.popleft()    # boshidan olish

Qayerda kerak

• BFS (kenglik bo‘yicha qidiruv) — navbatsiz bo‘lmaydi.
• Jarayonlarni kelish tartibida qayta ishlash (simulyatsiya).
• Oyna maksimumi: deque’da indekslarni kamayish tartibida saqlab, har oyna maksimumini O(1) da olish.

dq, out = deque(), []
for i, x in enumerate(a):
    while dq and a[dq[-1]] <= x:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()
    if i >= k - 1:
        out.append(a[dq[0]])