Queue va deque (FIFO): shift tuzog'i, ikki stek, ring buffer

Qisqacha: Queue (navbat) — birinchi kirgan birinchi chiqadigan tuzilma: FIFO (first in, first out). Asosiy amallar: enqueue — oxiriga qo'shish, dequeue — boshidan olish. JavaScript massivida push + shift bilan navbat yasash mumkin, lekin shift katta massivda O(n): o'lchovimizda (Node 24) navbat 15 000 dan 16 000 ga o'sganda vaqt bir zumda yuzlab baravar sakradi. To'g'ri yo'llar — linked list, ikki stek yoki ring buffer (doiraviy bufer): hammasida amallar O(1). Deque esa ikkala uchidan ham qo'shib-olish mumkin bo'lgan navbat.

Bu darsda

• Navbatning FIFO tamoyilini va enqueue/dequeue amallarini tushuntira olasiz.
• shift nega katta navbatda xavfli ekanini o'lchov bilan ko'rsatasiz.
• Navbatni ikki stek bilan va ring buffer bilan yoza olasiz, ularning murakkabligini asoslaysiz.
• Ikki tomonlama navbat (deque) yozasiz va u qachon kerakligini bilasiz.

Oldin bilishingiz kerak: Stack (LIFO), Linked list: tuzilishi va asosiy amallar, JS o'rnatilgan amallarining narxi, Sonlar nazariyasi asoslari.

1. Nega bu kerak?

Stek darsida likopchalar "oxirgi qo'yilgan — birinchi olinadi" qoidasi bilan ishladi. Oshxona buyurtmalari uchun esa bu adolatsiz bo'lardi. Birinchi kelgan mehmon birinchi ovqatlanishi kerak. Bu — navbat: kassadagi qator, telefon qo'ng'iroqlari, printerga yuborilgan cheklar.

Sardor navbatni eng sodda yo'l bilan yozdi: yangi buyurtma — push, oshpaz oladigan — shift. Oddiy kunlarda ekran a'lo ishladi. Lekin onlayn buyurtmalar ulangan kuni, navbat o'n minglarga yetganda, ekran birdan qota boshladi. Kecha 15 000 buyurtma bilan hammasi joyida edi, bugun 16 000 bilan — sekin. Sababi "sekin o'sish" emas, keskin sakrash edi. Bugun shu sirni ochamiz va to'g'ri navbat quramiz.

2. Navbat nima

2.1 FIFO va amallar

Navbat (queue) — elementlar bir uchidan (oxiri, tail) kirib, ikkinchi uchidan (boshi, head) chiqadigan tuzilma. Tamoyili — FIFO (first in, first out): "birinchi kirgan — birinchi chiqadi".

Stek va navbat farqi bitta so'zda: qaysi uchidan olinadi. Stek — qo'shilgan uchidan, navbat — qarama-qarshi uchidan.

2.2 shift tuzog'i

Massivda push oxiriga qo'shadi — arzon. shift esa birinchi elementni olib tashlaydi va qolganlarining hammasini bir o'ringa chapga suradi — nazariyada O(n) (JS o'rnatilgan amallarining narxi). Sinab ko'rdik: n ta buyurtmani push bilan qo'shib, keyin hammasini shift bilan oldik. Usul — benchmarking darsidagidek: har n alohida jarayonda, isitish, mediana:

Jadvalni diqqat bilan o'qing. 15 000 gacha shift deyarli tekin — vaqt chiziqli o'sadi. 15 000 dan 16 000 ga o'tganda esa vaqt 340 baravar sakradi. Keyin n ikki baravar — vaqt to'rt baravar (20 000 → 40 000: ×3,9). Bu O(n²) belgisi.

Nima bo'ldi? V8 kichik massivlarda hiyla ishlatadi: elementlarni surish o'rniga massiv boshlanish manzilini bitta o'ringa oldinga siljitadi. Bu "chapdan kesish" (left-trimming) — O(1). JS o'rnatilgan amallarining narxi darsida chegarani aniq topgan edik. Node 24 (V8 13.6) da massiv ichki zaxirasi 16 382 katakkacha bo'lsa, shift — O(1). Zaxira 16 383 katak va undan katta bo'lsa — O(n).

Bizning tushuntirishimiz — V8 manba kodiga tayangan taxmin: bunday zaxira taxminan 128 KB dan oshadi (16 384 × 8 bayt ≈ 128 KB). V8 uni "katta obyektlar maydoni"ga (large object space) joylaydi. U yerda chapdan kesish qilinmaydi — har shift hamma elementni haqiqatan suradi.

Unda nega jadvalda sakrash 16 383 da emas, 15 000 va 16 000 orasida? Chunki chegara elementlar soniga emas, sig'im (capacity) — ajratilgan zaxira hajmiga bog'liq. push joy tugaganda zaxirani taxminan 1,5 baravar kengaytiradi (amortizatsiya). Node 24 da 15 045-push dan keyin zaxira 22 583 katakka yetadi — 16 383 dan katta. Ikkiga bo'lib qidirib tekshirdik: push bilan qurilgan navbat 15 044 elementgacha tez, 15 045 dan boshlab sekin.

Xulosa ikki qavatli. Birinchisi: kichik navbatda (yuzlab, minglab) shift muammo emas — o'lchamay turib optimallashtirmang. Ikkinchisi: navbat katta bo'lishi mumkin bo'lsa (server so'rovlari, graf bo'ylab qidiruv, log oqimi), shift ga tayanmang. Dvigatelning hiylasi kafolat emas — u versiyadan versiyaga o'zgarishi mumkin. Big-O esa kafolat beradi.

Tekshirib ko'ring: Nega bitta shift emas, n ta shift jami O(n²) bo'ladi?

3. Navbatning uch to'g'ri implementatsiyasi

3.1 Linked list bilan

Eng to'g'ridan-to'g'ri yo'l Linked list darsida tayyor: append — oxiriga (tail tufayli O(1)), removeFirst — boshidan (O(1)). Hech kim surilmaydi. Kamchiligi — har element alohida obyekt: ko'proq xotira va axlat yig'uvchiga ko'proq ish. Afzalligi — navbat o'rtasidan ham tez olib tashlash mumkin (doubly list va Map bilan, Linked list masalalari darsidagidek): masalan, bekor qilingan buyurtmani navbat tartibini buzmasdan chiqarib yuborish.

3.2 Ikki stek bilan

Kutilmagan, lekin chiroyli g'oya: ikki stekdan navbat yasash. Stek tartibni teskari qiladi. Ikki marta teskari qilinsa — asl tartib qaytadi. Yangi kelganlar inbox stekiga tushadi. Olish kerak bo'lganda outbox dan olinadi. outbox bo'sh bo'lsa — inbox ni bittalab ag'darib outbox ga ko'chiramiz:

Ba'zi dequeue lar qimmat: ichida butun inbox ko'chadi — O(n). Lekin har element hayoti davomida ko'pi bilan bir marta ko'chadi: inbox dan outbox ga. Demak, n ta amal jami O(n) ish — har biriga o'rtacha O(1). Bu amortizatsiya: push dagi kabi, qimmat amallar kam uchraydi va narxi hammaga bo'linadi.

Bu usulning yutug'i — u faqat massivning tez amallarini (push, pop) ishlatadi. Massiv kesh uchun qulay, alohida obyektlar yaratilmaydi.

3.3 Ring buffer: doiraviy bufer

Uchinchi yo'l — shift qilish o'rniga boshni indeks bilan eslab qolish. Massiv joyida turadi, faqat head raqami oldinga suriladi. Lekin unda massiv boshida bo'sh joylar yig'iladi. Yechim — oxiriga yetganda 0-katakka aylanib o'tish: (indeks + 1) % sig'im. Massiv doira kabi ishlatiladi — bu ring buffer (doiraviy bufer, circular buffer):

Indekslar modul arifmetikasi bilan aylanadi: tail = (head + size) % capacity. Massiv bir marta ajratiladi va hech qachon surilmaydi — enqueue va dequeue sof O(1), amortizatsiyasiz. size alohida saqlangani muhim: busiz head === tail holatida "bufer bo'shmi yoki to'la?" degan savolga javob bo'lmaydi.

Bufer to'lganda ikki yo'l bor. Birinchisi — yangisini rad etish (false), vizualdagi kabi. Ikkinchisi — eng eskisini ustidan yozish: "oxirgi 100 ta log yozuvi" kabi vazifalar uchun. Cheksiz navbat kerak bo'lsa — to'lganda sig'imni ikki baravar oshirib, elementlarni yangi massivga tartib bilan ko'chirish mumkin (3-mashqdagi Deque shunday qiladi).

Endi o'zingiz hisoblang. Sig'im 5, head = 3, size = 4. Keyingi element qaysi indeksga yoziladi? (3 + 4) % 5 = .

3.4 O'lchov: uch implementatsiya

n ta enqueue, keyin n ta dequeue:

Uchalasida ham n ikki baravar — vaqt taxminan ikki baravar: hammasi O(n) jami, O(1) har amal. Ring buffer eng barqaror: uning ustunida nisbatlar 1,9–2,1. Linked list medianalari sakraydi — bir xil o'lchovda 72 dan 261 ms gacha. Sababi stekdagi kabi: millionlab obyekt va axlat yig'uvchi. Ikki stek har elementni bir marta ortiqcha ko'chiradi — shuning uchun ring buffer'dan taxminan ikki baravar sekin. Taqqoslash uchun: shift bilan navbat 40 ming elementda 1,9 soniya oldi. Bu yerda 8 million element 0,1–0,3 soniyada o'tdi.

4. Deque: ikki tomonlama navbat

Deque (double-ended queue, ikki tomonlama navbat) — ikkala uchidan ham qo'shish va olish mumkin bo'lgan tuzilma: pushFront, pushBack, popFront, popBack — hammasi O(1). U bir vaqtda ham stek, ham navbat.

«Bahor»da qayerda kerak? Oddiy buyurtmalar oxiriga tushadi (pushBack), shoshilinch — boshiga (pushFront). Oshpaz boshidan oladi (popFront). Mijoz oxirgi buyurtmasini darhol bekor qilsa — oxiridan olinadi (popBack). Monotonic queue darsida deque asosiy asbob bo'ladi.

Deque ring buffer ustiga quriladi. Yangi narsa — boshiga qo'shishda head orqaga suriladi. Bu yerda tuzoq bor: (0 - 1) % 8 JavaScript'da −1, 7 emas (Sonlar nazariyasi darsidagi manfiy qoldiq). Shuning uchun sig'im qo'shiladi:

const capacity = 8;
let head = 0;
console.log((head - 1) % capacity); // -1 — noto'g'ri indeks
head = (head - 1 + capacity) % capacity;
console.log(head); // 7 — oxirgi katak

To'liq Deque klassi 3-mashqda. JavaScript'da tayyor deque yo'q, lekin boshqa tillarda bor: Python'da collections.deque, Java'da ArrayDeque, C++ da std::deque.

Tekshirib ko'ring: Deque'da faqat pushBack va popBack ishlatilsa, u qanday tuzilma bo'ladi? Faqat pushBack va popFront ishlatilsa-chi?

5. Navbat amalda: kim keyingi?

Navbatning eng muhim ishlatilishi — "ishlarni kelish tartibida bajarish". Ikki misol:

• Event loop. Event loop dagi task navbati va microtask navbati — haqiqiy navbatlar. setTimeout callback'lari kelish tartibida bajariladi.
• Graf bo'ylab qidiruv (BFS). "Yaqindan uzoqqa" qidirish navbat bilan qilinadi: avval qo'shnilar, keyin qo'shnilarning qo'shnilari. Bu yerda navbat millionlab elementga yetishi mumkin — shuning uchun shift tuzog'i aynan BFS'da eng ko'p uchraydi (Graflarda BFS va DFS).

Kichik misol — oshxona navbatini ikki stekli navbat bilan yuritamiz va har buyurtma qancha kutganini hisoblaymiz:

class TwoStackQueue {
  #inbox = [];
  #outbox = [];
  enqueue(value) {
    this.#inbox.push(value);
  }
  dequeue() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length > 0) {
        this.#outbox.push(this.#inbox.pop());
      }
    }
    return this.#outbox.pop();
  }
  get size() {
    return this.#inbox.length + this.#outbox.length;
  }
}

const kitchen = new TwoStackQueue();
// [buyurtma, kelgan daqiqa]; har taomga 5 daqiqa ketadi
for (const order of [[101, 0], [102, 1], [103, 2], [104, 3]]) {
  kitchen.enqueue(order);
}
let clock = 0;
while (kitchen.size > 0) {
  const [id, arrived] = kitchen.dequeue();
  clock = Math.max(clock, arrived) + 5; // tayyor bo'ldi
  console.log(id, "kutdi:", clock - arrived, "daqiqa");
}

Konsolda:

101 kutdi: 5 daqiqa
102 kutdi: 9 daqiqa
103 kutdi: 13 daqiqa
104 kutdi: 17 daqiqa

Har yangi buyurtma oldingilari tugashini kutadi — kutish vaqti o'sib boradi. Oshxona soatiga 12 ta taom tayyorlasa-yu, buyurtma 15 ta kelsa, navbat cheksiz uzayadi. Bu — navbatlar nazariyasining asosiy saboqi: kelish tezligi xizmat tezligidan oshsa, hech qanday ma'lumotlar tuzilmasi yordam bermaydi — oshpaz kerak.

6. Chegaraviy holatlar

7. Ko'p uchraydigan xatolar

7.1 Katta navbatda shift

BFS yoki server navbatida queue.shift() — kichik testda tez, ishlab chiqarishda sekin. Tuzatish: ring buffer, ikki stek yoki linked list. Yoki oddiy hiyla: shift o'rniga head indeksini oshirib borish (queue[head++]) va massivni vaqti-vaqti bilan tozalash.

7.2 outbox bo'sh bo'lmasa ham ag'darish

Har dequeue da inbox ni outbox ga to'kish — eski elementlar ustiga yangilari tushadi, FIFO buziladi. Tuzatish: faqat outbox.length === 0 bo'lganda ko'chiring.

7.3 Ring buffer'da size siz ishlash

Faqat head va tail bilan: bo'sh va to'la holat bir xil ko'rinadi (head === tail). Tuzatish: size hisoblagichi yoki bitta katakni doim bo'sh qoldirish.

7.4 Manfiy qoldiq

(head - 1) % capacity — −1. buf[-1] — undefined, xato xabarisiz. Tuzatish: + capacity qo'shib, keyin qoldiq.

8. Mashqlar

1-mashq (oson): Qog'ozda

Ikki stekli navbatda: enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4), dequeue(), dequeue(). Har amaldan keyin inbox va outbox ni yozing. Qaysi dequeue ko'chirish qildi?

2-mashq (o'rta): Oxirgi 5 ta buyurtma

Oshxona ekranida doim oxirgi 5 ta buyurtma ko'rinsin: yangisi qo'shilganda eng eskisi tushib qolsin. RecentOrders klassini ring buffer asosida yozing: add(id) (to'lganda eskisi ustidan yoziladi) va list() — eskisidan yangisiga massiv. Ishora: to'la buferda yozish joyi — aynan head, keyin head bir qadam suriladi.

class RecentOrders {
  #buf;
  #head = 0;
  #size = 0;
  constructor(capacity) {
    this.#buf = new Array(capacity);
  }
  add(id) {
    const cap = this.#buf.length;
    if (this.#size < cap) {
      this.#buf[(this.#head + this.#size) % cap] = id;
      this.#size++;
    } else {
      this.#buf[this.#head] = id; // eng eskisi ustidan
      this.#head = (this.#head + 1) % cap;
    }
  }
  list() {
    const out = [];
    for (let k = 0; k < this.#size; k++) {
      out.push(this.#buf[(this.#head + k) % this.#buf.length]);
    }
    return out;
  }
}

const screen = new RecentOrders(5);
for (let id = 101; id <= 108; id++) screen.add(id);
console.log(screen.list()); // [ 104, 105, 106, 107, 108 ]

3-mashq (qiyin): Deque va testlar

kurs/mashqlar/14/19-navbat/navbat.test.mjs faylida o'suvchi ring buffer asosidagi Deque klassini yozing: pushFront, pushBack, popFront, popBack, peekFront, peekBack, size. To'lganda sig'im ikki baravar oshsin. node:test bilan sinang: navbat va stek sifatida, shoshilinch buyurtma oldinga, bo'sh deque va 1 000 ta tasodifiy amal — oddiy massiv (push/unshift/shift/pop) bilan solishtirib. Ishora: urug'li generator ishlating, massiv — "sekin, lekin ishonchli" model.

// kurs/mashqlar/14/19-navbat/navbat.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class Deque {
  #buf = new Array(4);
  #head = 0;
  #size = 0;
  get size() {
    return this.#size;
  }
  #at(k) { // k-element (0 — eng oldingisi) buferdagi indeksi
    return (this.#head + k) % this.#buf.length;
  }
  #grow() {
    const bigger = new Array(this.#buf.length * 2);
    for (let k = 0; k < this.#size; k++) {
      bigger[k] = this.#buf[this.#at(k)];
    }
    this.#buf = bigger;
    this.#head = 0;
  }
  pushBack(value) {
    if (this.#size === this.#buf.length) this.#grow();
    this.#buf[this.#at(this.#size)] = value;
    this.#size++;
  }
  pushFront(value) {
    if (this.#size === this.#buf.length) this.#grow();
    const len = this.#buf.length;
    this.#head = (this.#head - 1 + len) % len; // manfiyga tushmasin
    this.#buf[this.#head] = value;
    this.#size++;
  }
  popFront() {
    if (this.#size === 0) return undefined;
    const value = this.#buf[this.#head];
    this.#buf[this.#head] = undefined;
    this.#head = this.#at(1);
    this.#size--;
    return value;
  }
  popBack() {
    if (this.#size === 0) return undefined;
    const i = this.#at(this.#size - 1);
    const value = this.#buf[i];
    this.#buf[i] = undefined;
    this.#size--;
    return value;
  }
  peekFront() {
    return this.#size ? this.#buf[this.#head] : undefined;
  }
  peekBack() {
    if (this.#size === 0) return undefined;
    return this.#buf[this.#at(this.#size - 1)];
  }
}

test("navbat sifatida (FIFO)", () => {
  const d = new Deque();
  for (const id of [101, 102, 103]) d.pushBack(id);
  assert.equal(d.popFront(), 101);
  assert.equal(d.popFront(), 102);
  assert.equal(d.size, 1);
});

test("stek sifatida (LIFO)", () => {
  const d = new Deque();
  for (const id of [101, 102, 103]) d.pushBack(id);
  assert.equal(d.popBack(), 103);
  assert.equal(d.peekBack(), 102);
});

test("shoshilinch — oldinga", () => {
  const d = new Deque();
  d.pushBack(101);
  d.pushBack(102);
  d.pushFront(900); // shoshilinch
  assert.equal(d.peekFront(), 900);
  assert.deepEqual([d.popFront(), d.popFront(), d.popFront()],
    [900, 101, 102]);
});

test("bo'sh deque", () => {
  const d = new Deque();
  assert.equal(d.popFront(), undefined);
  assert.equal(d.popBack(), undefined);
  assert.equal(d.peekFront(), undefined);
});

test("1000 ta aralash amal — massiv bilan bir xil", () => {
  const d = new Deque();
  const model = []; // sekin, lekin ishonchli
  let seed = 3;
  const next = () => (seed = (seed * 48271) % 2147483647);
  for (let i = 0; i < 1000; i++) {
    const op = next() % 4;
    if (op === 0) { d.pushBack(i); model.push(i); }
    if (op === 1) { d.pushFront(i); model.unshift(i); }
    if (op === 2) assert.equal(d.popFront(), model.shift());
    if (op === 3) assert.equal(d.popBack(), model.pop());
    assert.equal(d.size, model.length);
  }
});

✔ navbat sifatida (FIFO) (1.1574ms)
✔ stek sifatida (LIFO) (0.3662ms)
✔ shoshilinch — oldinga (1.6056ms)
✔ bo'sh deque (1.4348ms)
✔ 1000 ta aralash amal — massiv bilan bir xil (1.4911ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 122.3495

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md dagi "Ma'lumotlar tuzilmalari" jadvaliga navbat (to'rt implementatsiya) va deque ustunlarini qo'shing. shift qatoriga o'lchovingizdagi "sakrash" nuqtasini yozing.

| Navbat | enqueue | dequeue | Izoh |
|---|---|---|---|
| Massiv push + shift | O(1) amort. | O(n) | Node 24: ≈ 15 000 gacha tez, keyin sakraydi |
| Linked list | O(1) | O(1) | ko'p obyekt, GC |
| Ikki stek | O(1) | O(1) amort. | faqat push/pop |
| Ring buffer | O(1) | O(1) | sig'im kerak yoki o'sish |
| Deque (ring) | O(1) amort. ikkala uchda | O(1) ikkala uchda | |

git add 14/MURAKKABLIK.md 14/19-navbat
git commit -m "14/19: navbat, ring buffer, deque va testlar"

9. Real ishda

• Serverlar va xabarlar. So'rovlar navbati, fon vazifalari navbati (BullMQ, RabbitMQ, Kafka) — ishlarni kelish tartibida va yuklamani tekislab bajaradi. Ularni Algoritmlar real ishda darsida va backend qismida ko'rasiz.
• Brauzer. Event loop navbatlari, requestAnimationFrame callback'lari, tarmoq so'rovlari navbati.
• Audio, video, tarmoq. Ring buffer — ovoz kartasi buferi, video oqimi, klaviatura bosishlari, log yozuvlari. Node.js'ning ichki navbatlari ham ring buffer'dan foydalanadi.
• Intervyu. "Implement Queue using Stacks" (LeetCode 232), "Design Circular Queue" (622), "Design Circular Deque" (641) va BFS'li har qanday masala.

Xulosa

• Navbat — FIFO: oxiriga enqueue, boshidan dequeue. Stekdan farqi — qarama-qarshi uchidan olinadi.
• shift — O(n). V8 kichik massivda uni tez qiladi, lekin Node 24 da zaxira 16 383 katakka yetganda (push bilan ≈ 15 000 elementda) vaqt 340 baravar sakradi va O(n²) ga o'tdi. Katta navbatda shift ishlatmang.
• Ikki stek: inbox → outbox faqat outbox bo'sh bo'lganda; amortizatsiyalangan O(1).
• Ring buffer: (head + size) % capacity, size ni alohida saqlang; sof O(1), eng barqaror o'lchov.
• Deque — ikkala uchida O(1); boshiga qo'shishda (head - 1 + capacity) % capacity.

Keyingi dars: Monotonic stack va monotonic queue — tartibli saqlangan stek va deque bilan "keyingi kattaroq element" va "oyna maksimumi" masalalarini O(n) da yechish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 10-bob (navbatlar), 16-bob (amortizatsiya).
• V8 manba kodi: Heap::LeftTrimFixedArray va katta obyektlar maydoni (large object space) — github.com/v8/v8
• Node.js manba kodi: lib/internal/fixed_queue.js (doiraviy buferlar zanjiri) — github.com/nodejs/node
• LeetCode: 232, 622, 641 — leetcode.com/problems