WisarWisar
Dasturlash kitobi/3-QISM — Algoritmlar11 daqiqa

3.4-bob: Stack va Queue

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 4-mavzu

1. Kirish va motivatsiya

Linked List 3.3-bob — moslashuvchan, lekin "cheksiz erkin". Ba'zan ataylab cheklangan tuzilma kerak — bu cheklov tartibni va ishonchni beradi. Stack va Queue — aynan shunday: ular faqat ma'lum joydan qo'shish/o'chirishga ruxsat beradi, va aynan shu cheklov ularni nihoyatda foydali qiladi.

  • Stack (stek) — LIFO (Last In, First Out — oxirgi kirgan birinchi chiqadi). Tarelkalar uyumi, brauzer "orqaga" tugmasi, undo, va 2.4-bobdagi call stack.
  • Queue (navbat) — FIFO (First In, First Out — birinchi kirgan birinchi chiqadi). Do'kondagi navbat, printer navbati, task queue 5.22-bob.

O'xshatish: Stack — yuvilgan tarelkalar uyumi: ustiga qo'yasiz (push), ustidan olasiz (pop). Eng oxirgi qo'yilgan tarelka birinchi olinadi. Queue — do'kon navbati: oxiriga turasiz, oldidan xizmat olasiz. Birinchi kelgan birinchi chiqadi — adolatli.

Nega muhim?

  • Call stack 2.4-bob, event loop 2.11-bob, undo/redo — Stack ustida.
  • Task/message queue 5.22-bob, BFS 3.7-bob, rate limiting — Queue ustida.
  • Intervyu klassikasi: qavslar muvozanati, ko'rsatkich tarixi.
  • Tree/Graph yurishlari (3.6, 3.7) — Stack/Queue ga tayanadi.

2. Nazariya — chuqur tushuntirish

2.1. Stack — LIFO

Stack — faqat bir uchidan (tepa, "top") qo'shish va o'chirish:

text
  push(30)         pop()  30
  ┌────┐           ┌────┐
  │ 30 │  top     │    │
  ├────┤           ├────┤
  │ 20 │           │ 20 │  top
  ├────┤           ├────┤
  │ 10 │           │ 10 │
  └────┘           └────┘
  Oxirgi kirgan (30) birinchi chiqadi (LIFO)

Asosiy amallar (barchasi O(1) — 3.1):

  • push(x) — tepaga qo'shish
  • pop() — tepadan olish (va qaytarish)
  • peek() — tepani ko'rish (olmasdan)
  • isEmpty() — bo'shmi?

2.2. Queue — FIFO

Queue — bir uchidan (orqa, "rear") qo'shish, boshqa uchidan (old, "front") o'chirish:

text
  enqueue   [10][20][30]   dequeue
  (orqaga)    ▲          ▲   (olddan)
             front     rear
  Birinchi kirgan (10) birinchi chiqadi (FIFO)

Asosiy amallar (O(1)):

  • enqueue(x) — orqaga qo'shish
  • dequeue() — olddan olish (va qaytarish)
  • peek/front() — oldni ko'rish
  • isEmpty() — bo'shmi?

2.3. Stack — JS massivi bilan (eng oddiy)

JS massivining push/pop 2.7-bob — aynan Stack (ikkalasi ham oxiridan, O(1)):

js
class Stack {
  constructor() { this.items = []; }
  push(x) { this.items.push(x); }          // O(1) (2.7)
  pop() { return this.items.pop(); }        // O(1) — oxirgi
  peek() { return this.items[this.items.length - 1]; }
  isEmpty() { return this.items.length === 0; }
  get size() { return this.items.length; }
}

2.4. Queue — massiv tuzog'i va to'g'ri yechim

JS massivida push + shift bilan Queue qilish oson, lekin sekin: shift() (boshdan olish) — O(n) (qolganlarni surish — 3.1, 3.2)!

js
//  SEKIN Queue — shift O(n) (katta ma'lumotda muammo)
class SlowQueue {
  constructor() { this.items = []; }
  enqueue(x) { this.items.push(x); }    // O(1)
  dequeue() { return this.items.shift(); }  // O(n) —  qolganlarni surish (3.2)
}

To'g'ri yechim — ikki ko'rsatkich (yoki Linked List — 3.3), shiftsiz:

js
//  TEZ Queue — ko'rsatkich bilan, shift'siz (O(1))
class Queue {
  constructor() { this.items = {}; this.front = 0; this.rear = 0; }
  enqueue(x) { this.items[this.rear++] = x; }       // O(1)
  dequeue() {
    if (this.isEmpty()) return undefined;
    const x = this.items[this.front];
    delete this.items[this.front++];                 // O(1) — surish yo'q
    return x;
  }
  peek() { return this.items[this.front]; }
  isEmpty() { return this.front === this.rear; }
  get size() { return this.rear - this.front; }
}

Eng ko'p uchraydigan xato: Queue uchun arr.shift() ishlatish. Kichik ma'lumotda sezilmaydi, lekin katta navbatda O(n) — sekinlik 3.1-bob. Ko'rsatkich yoki Linked List 3.3-bob bilan O(1).

2.5. Stack qayerda ishlatiladi

  • Call stack 2.4-bob — funksiya chaqiruvlari (LIFO).
  • Undo/Redo — har amal stack'ga; undo — pop.
  • Brauzer tarixi — "orqaga" tugmasi.
  • Qavslar muvozanati — ({[]}) to'g'rimi (Misol 1).
  • DFS (depth-first search — 3.7), ifoda hisoblash.
  • Rekursiyani tsiklga aylantirish 3.11-bob.

2.6. Queue qayerda ishlatiladi

  • Task/message queue (5.22: BullMQ) — fon vazifalari (FIFO).
  • BFS (breadth-first search — 3.7) — daraja-baraja yurish.
  • Printer/so'rov navbati — kelish tartibida xizmat.
  • Rate limiting — so'rovlarni navbatga qo'yish 5.20-bob.
  • Event/xabar oqimi — kelish tartibida qayta ishlash.

2.7. Deque, Circular Queue va Priority Queue (qisqacha)

  • Deque (double-ended queue, "ikki tomonlama navbat") — ikki uchidan ham qo'shish/o'chirish (stack + queue birga). To'rt amal: pushFront/pushBack, popFront/popBack — barchasi O(1). Sliding window (siljuvchi oyna) algoritmlarida asosiy vosita.
  • Circular Queue (halqasimon navbat) — sobit o'lchamli massivni "halqa" qilib ishlatish: front/rear ko'rsatkichlar oxiriga yetganda boshiga (% n) qaytadi. Bo'shab qolgan oldingi joylarni qayta ishlatadi — xotira o'smaydi (2.4-dagi ko'rsatkichli Queue indeks cheksiz o'sadi). Buferlar, IoT/audio oqimi va rate limiting'da 5.20-bob qulay.
  • Monoton stack (monotonic stack) — elementlari doim o'sib (yoki kamayib) boruvchi tartibda saqlanadigan Stack: yangi element kelganda tartibni buzuvchilar pop qilinadi. "Keyingi kattaroq element", "eng katta to'rtburchak", harorat masalalari kabi klassik intervyu savollarini O(n) da yechadi (sodda yondashuv O(n²)).
  • Priority Queue — element muhimligi (priority) bo'yicha chiqadi (FIFO emas) — odatda heap ustida 3.8-bob. Masalan kasalxona shoshilinch navbati.

3. Sintaksis — tez ma'lumotnoma

js
// STACK (LIFO) — JS massivi bevosita ishlaydi
const stack = [];
stack.push(x);              // qo'shish O(1)
stack.pop();                // olish O(1)
stack[stack.length - 1];    // peek
stack.length === 0;         // bo'shmi

// QUEUE (FIFO) — shift O(n)! ko'rsatkich/Linked List bilan O(1)
enqueue(x)  dequeue()  peek()  isEmpty()
//  arr.shift() — O(n)

4. Batafsil kod namunalari

Misol 1 — Stack: qavslar muvozanati (2.5)

js
// "({[]})" qavslari to'g'ri yopilganmi? (klassik intervyu)
function qavslarTogrimi(s) {
  const stack = [];
  const juftlik = { ")": "(", "]": "[", "}": "{" };
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);                       // ochuvchini stack'ga (2.3)
    } else if (juftlik[ch]) {
      if (stack.pop() !== juftlik[ch]) return false;   // mos yopuvchimi?
    }
  }
  return stack.length === 0;                 // hammasi yopilganmi?
}
qavslarTogrimi("({[]})");   // true
qavslarTogrimi("([)]");     // false (noto'g'ri tartib)
// O(n) — har belgi bir marta

Misol 2 — Queue: ko'rsatkich bilan (2.4)

js
class Queue {
  constructor() { this.items = {}; this.front = 0; this.rear = 0; }
  enqueue(x) { this.items[this.rear++] = x; }       // O(1)
  dequeue() {
    if (this.isEmpty()) return undefined;
    const x = this.items[this.front];
    delete this.items[this.front++];
    return x;                                         // O(1) — shift'siz
  }
  peek() { return this.items[this.front]; }
  isEmpty() { return this.front === this.rear; }
  get size() { return this.rear - this.front; }
}

const q = new Queue();
q.enqueue("Ali"); q.enqueue("Vali"); q.enqueue("Guli");
console.log(q.dequeue());   // "Ali" (birinchi kirgan — FIFO)
console.log(q.peek());      // "Vali"

Misol 3 — Stack: undo tizimi (2.5)

js
class Matn {
  constructor() { this.matn = ""; this.tarix = []; }   // tarix — stack
  yoz(s) {
    this.tarix.push(this.matn);   // hozirgi holatni saqla (push)
    this.matn += s;
  }
  undo() {
    if (this.tarix.length) this.matn = this.tarix.pop();   // oxirgini tikla (pop)
  }
}
const m = new Matn();
m.yoz("Salom"); m.yoz(" Dunyo");
console.log(m.matn);   // "Salom Dunyo"
m.undo();
console.log(m.matn);   // "Salom" (oxirgi amal bekor)

Misol 4 — Queue: BFS uchun asos (3.7 ga ko'prik)

js
// Daraja-baraja yurish (oddiy graph/tree — 3.6, 3.7)
function bfsTartib(boshlanish, qoshnilar) {
  const korilgan = new Set([boshlanish]);   // (2.9)
  const queue = [boshlanish];               // (oddiylik uchun massiv)
  const natija = [];
  let front = 0;                             // ko'rsatkich (shift'siz — 2.4)
  while (front < queue.length) {
    const node = queue[front++];             // dequeue (O(1))
    natija.push(node);
    for (const qoshni of qoshnilar(node)) {
      if (!korilgan.has(qoshni)) {           // ko'rilmaganni navbatga
        korilgan.add(qoshni);
        queue.push(qoshni);                  // enqueue
      }
    }
  }
  return natija;   // O(V + E) — daraja bo'yicha (3.7)
}

5. To'g'ri va noto'g'ri holatlar

1) Queue uchun shift()

js
//  shift O(n) — katta navbatda sekin (2.4, 3.2)
dequeue() { return this.items.shift(); }

//  ko'rsatkich bilan O(1)
dequeue() { const x = this.items[this.front]; delete this.items[this.front++]; return x; }

2) Bo'sh stack/queue'da pop/dequeue

js
//  bo'shda pop  undefined, keyin xato (0.6)
const x = stack.pop().value;   // undefined.value

//  avval tekshir
if (!stack.length) return;
const x = stack.pop();

3) Stack o'rniga noto'g'ri tuzilma (LIFO kerak bo'lganda)

text
 undo uchun massivni boshidan o'chirish (noto'g'ri tartib + sekin)
 Stack (push/pop oxiridan) — LIFO tartibi tabiiy (2.5)

4) FIFO vs LIFO chalkashligi

text
 navbat (FIFO) uchun Stack (LIFO) ishlatish — tartib teskari
 Tartibni aniqla: oxirgi kerakmi (Stack) yoki birinchi (Queue)?

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Katta Queue sekin ishlaydi

Sababi: shift() har dequeue'da O(n) (2.4, 3.2). Yechimi: ko'rsatkich (front index) yoki Linked List 3.3-bob — O(1).

Xato 2 — Cannot read properties of undefined

Sababi: bo'sh stack/queue'da pop/dequeue natijasi undefined 0.6-bob. Yechimi: isEmpty() tekshiring.

Xato 3 — Qavs muvozanatida noto'g'ri natija

Sababi: faqat sanab (stack'siz) — tartibni tekshirmaslik (Misol 1). Yechimi: Stack bilan har yopuvchini oxirgi ochuvchiga moslash.

Xato 4 — Stack overflow (rekursiya)

Sababi: chuqur rekursiya — call stack (2.4, 0.1) to'ldi. Yechimi: o'z Stack'ingiz bilan tsiklga aylantiring 3.11-bob yoki base case.

Xato 5 — Memory leak (ko'rsatkichli Queue'da)

Sababi: delete qilinmasa, eski elementlar xotirada qoladi. Yechimi: dequeue'da delete this.items[front] (Misol 2).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

  • Call stack/event loop (2.4, 2.11): Stack (LIFO) + Queue (microtask/macrotask).
  • Linked List 3.3-bob: Stack/Queue ko'pincha uning ustida (O(1)).
  • Tree/Graph (3.6, 3.7): DFS — Stack; BFS — Queue (Misol 4).
  • Task queue 5.22-bob: BullMQ — fon vazifalari (FIFO).
  • Rate limiting 5.20-bob: so'rov navbati.
  • Heap/Priority Queue 3.8-bob: muhimlik bo'yicha navbat.
  • Undo/redo, brauzer tarixi: Stack (real ilovalar).

8. Eng yaxshi amaliyotlar (best practices)

  • Stack — JS massivi (push/pop) bevosita ishlaydi (O(1) — 2.3).
  • Queue uchun shift ishlatmang — ko'rsatkich yoki Linked List (O(1) — 2.4).
  • Tartibni aniqlang: oxirgi kerak (LIFO/Stack) yoki birinchi (FIFO/Queue)?
  • Bo'sh holatni tekshiring (isEmpty) pop/dequeue'dan oldin 0.6-bob.
  • Ko'rsatkichli Queue'da delete — memory leak'dan saqlaydi (Misol 2).
  • Qavs/ifoda muvozanati uchun Stack — tabiiy yechim (Misol 1).
  • BFS Queue, DFS Stack (yoki rekursiya — 3.7).
  • Priority kerak bo'lsa — Heap 3.8-bob, oddiy Queue emas.

9. Amaliy loyiha: "Stack & Queue Amaliy To'plami"

Stack va Queue'ni real masalalarda qo'llash.

Maqsad

LIFO/FIFO tuzilmalarini qurib, ularning real qo'llanishini (undo, qavs, navbat, BFS) amalda mustahkamlash; Queue'da O(1) ni ta'minlash.

Talablar (requirements)

  1. Stack class: push, pop, peek, isEmpty, size (massiv bilan — Misol 2.3).
  2. Queue class: ko'rsatkich bilan, shiftsiz, O(1) (Misol 2).
  3. Qavslar muvozanati: ({[]}) tekshiruvchi (Stack — Misol 1).
  4. Undo/Redo: matn muharriri (ikki Stack — undo va redo — Misol 3).
  5. Postfix/ifoda hisoblash: oddiy ifodani Stack bilan hisoblash (bonus).
  6. BFS: oddiy graph/labirintni daraja-baraja yurish (Queue — Misol 4).
  7. Hot Potato (o'yin): Queue bilan har n-chi o'yinchini chiqarish (circular queue g'oyasi).
  8. Chegaraviy holatlar: bo'sh stack/queue, bitta element 0.6-bob.
  9. Har amal Big-O bilan; Queue'da shift ishlatilmasligi isbotlansin (3.1, 2.4).

Maslahatlar (hint)

  • Stack — JS massivi yetadi (push/pop — 2.3).
  • Queue — front/rear ko'rsatkich (Misol 2); shift yo'q.
  • Undo/Redo — ikki stack: amal qilganda redo tozalanadi.
  • Qavs: ochuvchini push, yopuvchida pop+moslik (Misol 1).
  • BFS: korilgan Set 2.9-bob + Queue (Misol 4).
  • Bo'sh holatni tekshiring (6-bo'lim).

"Tayyor" mezonlari (acceptance criteria)

  • Stack va Queue class'lar ishlaydi (barcha amal O(1)).
  • Queue shift ishlatmaydi (ko'rsatkich bilan).
  • Qavs muvozanati to'g'ri/noto'g'rini aniqlaydi.
  • Undo/Redo ishlaydi (ikki stack).
  • BFS daraja-baraja to'g'ri yuradi.
  • Hot Potato to'g'ri o'yinchini chiqaradi.
  • Bo'sh/bitta chegaraviy holatlar qulamaydi.
  • Har amal Big-O bilan izohlangan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda ikki cheklangan, lekin nihoyatda foydali tuzilmani o'rgandik:

  • Stack — LIFO (oxirgi kirgan birinchi chiqadi); push/pop/peek O(1). JS massivi bevosita ishlaydi. Call stack 2.4-bob, undo, DFS, qavs muvozanati.
  • Queue — FIFO (birinchi kirgan birinchi chiqadi); enqueue/dequeue O(1). shift O(n) — ko'rsatkich/Linked List bilan O(1). Task queue 5.22-bob, BFS, navbat.
  • Deque (ikki uchli), Circular Queue (halqasimon — xotira o'smaydi), Monoton stack (O(n) yechimlar), Priority Queue (muhimlik — heap ustida, 3.8).
  • Best: tartibni aniqlang (LIFO/FIFO), shiftdan qoching, bo'sh holatni tekshiring.

Keyingi bob — 3.5-bob: Hash Table / Map. Stack/Queue tartibli edi; endi eng tez qidiruv tuzilmasini — Hash Table'ni o'rganamiz. 2.9-bobda Map/Set'ni ishlatdik; endi ular ichkarida qanday O(1) qidiruvni ta'minlashini (hash funksiya, kolliziya) chuqur ochamiz. Bu — DB indeks 6.3-bob, cache 5.21-bob va ko'p optimizatsiyaning asosi.

Foydalanilgan rasmiy/ishonchli manbalar

  • bigocheatsheet.com — Stack/Queue operatsiyalari murakkabligi
  • Universal CS — LIFO/FIFO, deque, priority queue
  • MDN Web Docs — Array push/pop/shift murakkabligi (2.7)

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
3.4-bob: Stack va Queue — Wisar