Stack va Queue JavaScript'da — LIFO, FIFO, monotonic stack (3.4-bob)

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:

  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:

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

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

// ❌ 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:

// ✅ 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.

2.8. Senior Architect: Monotonic Stack naqshi va Ring Buffer (Circular Queue)

1. Monotonic Stack — $O(n^2)$ masalalarni $O(n)$ da yechish siri

Intervyularda eng ko'p uchraydigan naqshlardan biri — Monoton Stek (Monotonic Stack). Masala (Next Greater Element — LeetCode 496/739 Daily Temperatures): Har bir element uchun undan keyin keladigan o'zidan birinchi kattaroq elementni topish kerak.

• Sodda yechim: Ichma-ich tsikl — $O(n^2)$ (sekin).
• Monoton Stek yechimi: $O(n)$ vaqt! Har bir element stekka faqat 1 marta kiradi va 1 marta chiqadi.

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // Indekslarni saqlaydi

  for (let i = 0; i < n; i++) {
    // Agar joriy element stek tepasidagi elementdan katta bo'lsa:
    // demak, stekdagi elementlar uchun "keyingi katta" topildi!
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      result[prevIndex] = nums[i];
    }
    stack.push(i);
  }

  return result;
}

console.log(nextGreaterElements([2, 1, 2, 4, 3])); 
// Natija: [4, 2, 4, -1, -1] — Sof O(n) vaqt va O(n) xotira!

2. Ring Buffer (Circular Queue) — Xotira sizishisiz O(1) Navbat

2.4-bo'limda ko'rgan obyektli navbatimizda front va rear ko'rsatkichlari cheksiz o'sib boradi. Tarmoq drayverlari, audio oqimlari yoki yuqori tezlikdagi log tizimlarida qat'iy sobit o'lchamli Ring Buffer (Aylanma Bufer) ishlatiladi:

class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity;
    this.buffer = new Array(capacity);
    this.front = 0;
    this.size = 0;
  }

  enqueue(item) {
    if (this.isFull()) return false; // To'lgan
    const rear = (this.front + this.size) % this.capacity; // Modulo aylanishi!
    this.buffer[rear] = item;
    this.size++;
    return true;
  }

  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.buffer[this.front];
    this.buffer[this.front] = null; // Garbage Collection uchun
    this.front = (this.front + 1) % this.capacity; // Modulo bilan keyingi katakka
    this.size--;
    return item;
  }

  isFull() { return this.size === this.capacity; }
  isEmpty() { return this.size === 0; }
}

const q = new CircularQueue(3);
q.enqueue("A"); q.enqueue("B"); q.enqueue("C");
console.log(q.dequeue()); // "A"
q.enqueue("D"); // Boshiga aylanib "A" ning o'rniga yoziladi!

Bu tizimda yangi xotira ajratilmaydi (zero garbage collection overhead), apparat CPU keshiga ideal mos keladi.

3. Sintaksis — tez ma'lumotnoma

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

// "({[]})" 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)

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)

class Matn {
  constructor() { this.matn = ""; this.tarix = []; }   // tarix — stack
  yoz(s) {
    this.tarix.push(this.matn);   // hozirgi holatni saqlash (push)
    this.matn += s;
  }
  undo() {
    if (this.tarix.length) this.matn = this.tarix.pop();   // oxirgini tiklash (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)

// 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)
}

Misol 5 — Monoton Stack: Keyingi kattaroq element (Next Greater Element)

Har bir son uchun undan o'ng tomonda joylashgan birinchi kattaroq sonni topish kerak. Oddiy ikki qavatli tsikl $O(n^2)$ vaqt oladi. Monoton Stack esa buni bir martalik yurishda — $O(n)$ vaqtda hal qiladi:

function nextGreaterElement(arr) {
  const natija = new Array(arr.length).fill(-1);
  const stack = []; // indekslarni saqlaymiz

  for (let i = 0; i < arr.length; i++) {
    // Joriy son stack uchidagi indeksli sondan katta bo'lsa — uning jufti topildi!
    while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
      const topIndeks = stack.pop();
      natija[topIndeks] = arr[i];
    }
    stack.push(i);
  }

  return natija;
}

console.log(nextGreaterElement([2, 1, 2, 4, 3])); 
// [4, 2, 4, -1, -1] — O(n) vaqt va O(n) xotira!

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

1) Queue uchun shift()

// ❌ 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

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

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

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

❌ 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

❌ navbat (FIFO) uchun Stack (LIFO) ishlatish — tartib teskari
✅ Tartibni aniqlang: 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)