stack

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.