Stek va navbat: ma’lumotlar tuzilmalari oddiy tilda, misollar bilan

Qisqa javob

• Stek — oxirgi kelgan birinchi ketadi (LIFO). Likopchalar taxlami kabi: tepasiga qo‘yasiz va tepasidan olasiz. Amallar: push, pop, peek.
• Navbat — birinchi kelgan birinchi ketadi (FIFO). Kassadagi navbat kabi: yangilar oxiriga turadi, birinchisiga xizmat ko‘rsatiladi. Amallar: enqueue, dequeue.

Bular xotiraning yangi turlari emas, balki cheklovlar. Ular faqat bir yoki ikki uchiga kirishga ruxsat beradi, shuning uchun kod soddaroq, amallar esa O(1) da ishlaydi.

Stek, navbat va dek

Dek (deque, ikki tomonlama navbat) ikkala uchidan qo‘shish va olishga imkon beradi. U stek sifatida ham, navbat sifatida ham ishlay oladi.

Stekni amalga oshirish

Dinamik massiv — ideal stek: tepa massivning oxiri, oxiridan qo‘shish va o‘chirish esa amortizatsiyalangan O(1).

stack = []
stack.append("a")   # push
stack.append("b")
top = stack[-1]     # peek -> "b"
stack.pop()         # pop  -> "b"

const stack = [];
stack.push("a");
stack.push("b");
stack.at(-1); // peek -> "b"
stack.pop();  // pop  -> "b"

Navbatni amalga oshirish

Bu yerda sodda yondashuv zarar qiladi. Python dagi list.pop(0) va JavaScript dagi array.shift() boshidan o‘chiradi va qolgan barcha elementlarni suradi — har bir amalga O(n).

Python da collections.deque dan foydalaning:

from collections import deque

queue = deque()
queue.append("task1")    # enqueue
queue.append("task2")
first = queue.popleft()  # dequeue -> "task1"

JavaScript da o‘rnatilgan navbat yo‘q. Kichik navbatlar uchun shift() bemalol yaraydi. Kattalari uchun o‘qish indeksini saqlang yoki bog‘langan ro‘yxatdan foydalaning:

class Queue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(x) { this.items.push(x); }
  dequeue() {
    if (this.head >= this.items.length) return undefined;
    const x = this.items[this.head++];
    if (this.head > 1024 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head); // o‘qilgan qismni tashlaymiz
      this.head = 0;
    }
    return x;
  }
  get size() { return this.items.length - this.head; }
}

Boshqa variantlar — bog‘langan ro‘yxat (dumga qo‘shish, boshdan olish) yoki halqali bufer: boshi va oxiri indekslari aylana bo‘ylab qaytadigan qat’iy o‘lchamli massiv.

Stek qayerda ishlatiladi

• Bekor qilish tarixi. Har bir amal stekka qo‘yiladi, Ctrl+Z oxirgisini oladi. Qaytarish (redo) odatda ikkinchi stekda saqlanadi.
• Chaqiruvlar steki. Har bir funksiya chaqiruvi lokal o‘zgaruvchilar va qaytish manzili bilan kadrni qo‘yadi, return uni oladi. Juda chuqur rekursiya stack overflow ga olib keladi.
• Qavslarni tekshirish. Har bir ochuvchi qavs stekka qo‘yiladi; yopuvchida tepadagini olib, juftligini tekshiramiz.
• Chuqurlik bo‘yicha qidiruv (DFS) va qaytib izlash — aniq stek yoki rekursiya orqali.

Qavslarni tekshirish — klassik masala:

def balanced(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced("{[()]}")  # True
balanced("([)]")    # False

Navbat qayerda ishlatiladi

• Vazifalar navbati. Fon vazifalari, xatlar, rasmlarni qayta ishlash: ishlab chiqaruvchilar vazifa qo‘shadi, worker lar ularni tartib bilan oladi. Production da bu ko‘pincha alohida broker, lekin g‘oya o‘sha FIFO.
• Kenglik bo‘yicha qidiruv (BFS). Tugunga kiramiz, qo‘shnilarini navbatga qo‘shamiz, takrorlaymiz. Shu tarzda vaznsiz grafda eng qisqa yo‘l topiladi.
• Buferlar. Klaviatura kiritishi, tarmoq paketlari, hodisalar oqimi — kelish tartibida qayta ishlanadigan hamma narsa.

from collections import deque

def bfs(graph, start):
    seen, order = {start}, []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

Ko‘p uchraydigan xatolar

• Katta navbatlarda shift() yoki pop(0) ishlatib, kvadratik vaqt olish.
• Bo‘sh stekda tekshiruvsiz pop chaqirish: Python IndexError beradi, JavaScript jimgina undefined qaytaradi.
• Tartibni chalkashtirish: BFS da navbatni stek bilan almashtirsangiz, chuqurlik bo‘yicha aylanish hosil bo‘ladi.
• Aniq stek chaqiruvlar steki limitiga yetmaslikka yordam beradigan joyda chuqur rekursiya ishlatish.