Stek va navbat

Stek

Stek — «oxirgi kirgan birinchi chiqadi» (LIFO). Python’da oddiy ro‘yxat: append — qo‘shish, pop — olish, st[-1] — tepadagi element. Hammasi O(1).

Qavslar balansi

pairs = {")": "(", "]": "[", "}": "{"}
st = []
for ch in s:
    if ch in "([{":
        st.append(ch)
    elif not st or st.pop() != pairs[ch]:
        print("NO"); break
else:
    print("YES" if not st else "NO")

Monoton stek

Har element uchun «o‘ngdagi birinchi katta element»ni O(n) da topish:

ans, st = [-1] * n, []          # st — indekslar, qiymatlari kamayuvchi
for i, x in enumerate(a):
    while st and a[st[-1]] < x:
        ans[st.pop()] = x
    st.append(i)

Qo‘llanishi: ifodalarni hisoblash, «undo», DFS ni rekursiyasiz yozish.

Navbat

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]])

Bog‘langan ro‘yxat

Bog‘langan ro‘yxat — har tugun qiymat va keyingi tugunga havola saqlaydi. Boshiga qo‘shish O(1), lekin i-elementga borish O(n).

class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

Tez-tez uchraydigan usullar

• Sekin va tez ko‘rsatkich: o‘rtani topish, sikl borligini aniqlash (Floyd).
• Soxta bosh tugun (dummy) — boshini o‘chirishda alohida holatlarni yo‘qotadi.

Musobaqa masalalarida bog‘langan ro‘yxat kamdan-kam kerak bo‘ladi — odatda massiv yoki deque yetadi. Lekin intervyularda klassik mavzu.