Queue (navbat)

Tasavvur qiling, bank kassasi oldida odamlar navbatda turibdi. Yangi kelgan odam navbat oxiriga qo‘shiladi. Kassir esa eng oldin kelgan odamga birinchi xizmat ko‘rsatadi. Keyin ikkinchi kelgan, undan so‘ng uchinchi kelgan odamning navbati keladi.

Queue, ya’ni navbat, elementlarni shu tartibda boshqaradigan ma’lumotlar tuzilmasi. Unga birinchi qo‘shilgan element birinchi bo‘lib olinadi. Bu qoida FIFO (First In, First Out) — “birinchi kirgan, birinchi chiqadi” deb ataladi.

                         xizmat ko‘rsatish yo‘nalishi
                                      ←

rear                                                   front
 ↓                                                       ↓
[ yangi: D ] → [ C ] → [ B ] → [ eng oldin kelgan: A ] → chiqish

Yangi element navbatning rear, ya’ni orqa tomoniga qo‘shiladi. Element front, ya’ni old tomonidan olinadi. Ikki tomonning vazifasi ataylab ajratilgan: qo‘shish bir chetda, olish boshqa chetda bajariladi.

Queue ham stack kabi avvalo abstrakt ma’lumotlar turi (abstract data type, ADT). U ma’lumot xotirada aynan qanday joylashishini emas, elementlar qaysi tartibda kirib-chiqishini va qaysi amallar ruxsat etilishini belgilaydi. Queueni array, circular buffer yoki linked list asosida qurish mumkin. Tashqaridan FIFO xatti-harakati bir xil qoladi, ichki xotira va murakkablik esa implementatsiyaga bog‘liq.

Kundalik navbatdan texnik modelga

Oddiy navbatda uchta asosiy qoida bor:

1. yangi kelgan element oxiriga turadi;
2. eng oldingi element birinchi chiqadi;
3. o‘rtadagi element boshqalardan o‘tib ketmaydi.

Queue amallari ham shu qoidalarga mos:

• orqaga element qo‘shish — ENQUEUE;
• oldingi elementni olib tashlash — DEQUEUE;
• oldingi elementni o‘chirmasdan ko‘rish — PEEK yoki FRONT;
• navbat bo‘shligini tekshirish — IS_EMPTY;
• elementlar sonini bilish — SIZE.

Boshlanish:
front → [10] [20] [30] ← rear

ENQUEUE(40):
front → [10] [20] [30] [40] ← rear

DEQUEUE(): 10 chiqadi
front → [20] [30] [40] ← rear

Rasmda elementlar chapdan o‘ngga joylashgan. Bu faqat mantiqni ko‘rsatadi. Kompyuter xotirasida array elementlari yonma-yon, linked list node’lari esa tarqoq bo‘lishi mumkin.

Asosiy terminlar

Front

Front — navbatdagi keyingi DEQUEUE yoki PEEK ishlaydigan old tomon. Eng uzoq kutgan element shu yerda turadi.

Rear

Rear — yangi element qo‘shiladigan orqa tomon. Ayrim manbalarda bu tomon back yoki tail deb ham ataladi.

Enqueue

ENQUEUE(value) yangi qiymatni rear tomonga qo‘shadi. Mavjud elementlarning chiqish tartibi o‘zgarmaydi.

Dequeue

DEQUEUE() frontdagi elementni navbatdan olib tashlaydi va odatda uning qiymatini qaytaradi. Bu amal navbat holatini o‘zgartiradi.

Peek yoki front

PEEK() oldingi qiymatni ko‘rsatadi, ammo o‘chirmaydi. DEQUEUEdan farqli ravishda navbat uzunligi o‘zgarmaydi.

FIFO

FIFO kirish tartibi bilan chiqish tartibi bir xil bo‘lishini bildiradi:

ENQUEUE(A), ENQUEUE(B), ENQUEUE(C)

DEQUEUE tartibi: A, B, C

Underflow va overflow

• underflow — bo‘sh queuedan element olish yoki ko‘rishga urinish;
• overflow — sig‘imi cheklangan queue to‘la bo‘lganda yangi element qo‘shishga urinish.

Dynamic queue joyni kengaytirishi mumkin, lekin umumiy xotira cheklangan. Tizim dizaynida bounded queue’ning to‘lishi ba’zan xato emas, balki yukni nazorat qilish uchun ataylab tanlangan holatdir.

Queue nima sababdan ikki tomondan ishlaydi?

Queue adolatli kelish tartibini saqlash uchun yangi element va olinadigan elementni turli chetlarda boshqaradi. Yangi element frontga qo‘shilsa, u oldin kelganlardan o‘tib ketadi. Element rear’dan olinsa, eng yangi element birinchi chiqib, tuzilma stackga aylanadi.

Front va rear’ni alohida saqlash quyidagi foydani beradi:

• eng oldingi va eng keyingi joyni qidirmasdan topish mumkin;
• to‘g‘ri implementatsiyada ENQUEUE va DEQUEUE odatda O(1);
• kelish tartibi tabiiy saqlanadi;
• producer va consumer o‘rtasidagi vaqtinchalik farqni bufferlash mumkin.

Bu tartibning evaziga o‘rtadagi yoki eng oxirgi elementni ixtiyoriy olish klassik queue interfeysida mavjud emas.

Oddiy array implementatsiyasidagi muammo

Queueni array bilan sodda tasavvur qilish mumkin. Front doim 0-indexda tursa, DEQUEUEdan keyin bo‘shliqni yopish uchun barcha elementlarni chapga surishga to‘g‘ri keladi:

Oldin:
Index:    0     1     2     3
        +-----+-----+-----+-----+
        | 10  | 20  | 30  | 40  |
        +-----+-----+-----+-----+

10 olindi:
        |bo‘sh| 20  | 30  | 40  |

Siljitilgach:
        | 20  | 30  | 40  |bo‘sh|

Har DEQUEUEda n - 1 tagacha element ko‘chirilsa, vaqt O(n) bo‘ladi. Queue uchun bu kerak emas. Elementlarni siljitish o‘rniga front indexni oldinga surish mumkin:

front = front + 1

Ammo faqat oldinga yuradigan front yana boshqa muammo tug‘diradi.

Linear array queue va “soxta to‘lish”

Capacity 5 bo‘lgan arrayda front va rear indexlarini saqlaylik:

Index:      0       1       2       3       4
          +-------+-------+-------+-------+-------+
          | bo‘sh | bo‘sh |  30   |  40   |  50   |
          +-------+-------+-------+-------+-------+
                            ↑               ↑
                          front            rear

0 va 1-indexlar oldingi DEQUEUElardan keyin bo‘shagan. Rear array oxiriga yetgan bo‘lsa, oddiy linear implementatsiya yangi elementga joy yo‘q deb o‘ylashi mumkin, holbuki boshida ikkita bo‘sh katak bor. Buni hal qilish uchun elementlarni yana siljitish mumkin, lekin bu O(n) xarajatni qaytaradi.

Yaxshiroq yechim — array oxiridan keyin mantiqan boshiga qaytish. Bu circular queue yoki circular buffer g‘oyasi.

Circular queue

Circular queueda array halqa sifatida qaraladi. Index oxirgi katakdan o‘tganda 0ga qaytadi:

next_index = (current_index + 1) MOD capacity

MOD qoldiq operatori indexni 0..capacity-1 oralig‘ida saqlaydi.

         ┌────────────────────────────────────┐
         │                                    │
         ↓                                    │
Index:   0       1       2       3       4    │
       +-------+-------+-------+-------+-------+
       |  60   |  70   |  30   |  40   |  50   |
       +-------+-------+-------+-------+-------+
           ↑               ↑
          rear            front

Mantiqiy navbat arraydagi jismoniy index tartibida emas:

front → 30, 40, 50, 60, 70 ← rear

Array oxiridagi 50dan keyin navbat 0-indexdagi 60 bilan davom etadi. Elementlar ko‘chirilmaydi; faqat front va rear indexlari halqa bo‘ylab yuradi.

Bo‘sh va to‘la holatni ajratish

Front va rear bir xil qiymatga kelishi bo‘sh queue’ni ham, to‘la aylanib kelgan queueni ham anglatishi mumkin. Implementatsiya bu ikki holatni ajratishi kerak. Keng tarqalgan usullar:

• alohida size hisoblagichini saqlash;
• bitta katakni doim bo‘sh qoldirish;
• qo‘shimcha full/empty belgisi saqlash.

Ushbu maqoladagi pseudocodeda front keyingi olinadigan katakni, rear keyingi yoziladigan bo‘sh katakni va size elementlar sonini bildiradi:

Bo‘sh queue:
front = 0
rear = 0
size = 0

Circular queueda enqueue

FUNCTION ENQUEUE(queue, value)
    IF queue.size = queue.capacity
        RETURN OVERFLOW

    queue.items[queue.rear] = value
    queue.rear = (queue.rear + 1) MOD queue.capacity
    queue.size = queue.size + 1

Bir katakka yozish va indexlarni yangilash bajariladi. Fixed-size circular queueda vaqt O(1), qo‘shimcha xotira O(1).

Circular queueda dequeue

FUNCTION DEQUEUE(queue)
    IF queue.size = 0
        RETURN UNDERFLOW

    value = queue.items[queue.front]
    queue.items[queue.front] = EMPTY
    queue.front = (queue.front + 1) MOD queue.capacity
    queue.size = queue.size - 1
    RETURN value

Elementlar siljitilmaydi. Front keyingi katakka o‘tadi, shuning uchun vaqt O(1). EMPTY yozish ayrim xotira boshqaruv tizimlarida eski obyekt reference’ini ushlab turmaslik uchun foydali.

Circular buffer qayerda ishlatiladi?

Circular buffer maksimal sig‘im ma’lum bo‘lgan uzluksiz oqimlarda qulay:

• audio qurilmada kelayotgan tovush namunalarini vaqtincha saqlash;
• tarmoq paketlarini qabul qilish bufferi;
• oxirgi N ta log yozuvini saqlash;
• producer va consumer orasidagi qisqa tezlik farqini yumshatish.

Masalan, audio tizim tovush namunalarini ishlab chiqaradi, boshqa qism esa ularni doimiy tezlikda ijro etadi. Circular buffer eski bo‘shagan kataklarni qayta ishlatadi va doim element ko‘chirish talab qilmaydi. Producer juda sekin bo‘lsa underflow, juda tez bo‘lsa overflow yoki tanlangan siyosatga ko‘ra eski ma’lumot ustiga yozish yuz berishi mumkin.

Dynamic array asosidagi queue

Circular queue dynamic array bilan birlashtirilsa, capacity tugaganda kattaroq array ajratilishi mumkin. Mantiqiy navbat eski arrayda ikki bo‘lakka bo‘lingan bo‘lishi mumkin:

Jismoniy array: [60, 70, bo‘sh, 30, 40, 50]
Mantiqiy tartib: 30, 40, 50, 60, 70

Resize paytida elementlar yangi arrayga FIFO tartibida ko‘chiriladi:

Yangi array: [30, 40, 50, 60, 70, bo‘sh, bo‘sh, ...]
              ↑                   ↑
            front               rear

Oddiy ENQUEUE O(1), resize sodir bo‘lgan aniq amal O(n). Capacity geometrik oshirilsa, ko‘p enqueue amallarining amortized vaqti O(1) bo‘ladi. Amortized tahlil kamdan kam qimmat ko‘chirish xarajatini ko‘plab arzon amallar orasiga taqsimlaydi.

Linked list asosidagi queue

Singly linked listda front list boshini, rear esa oxirgi node’ni ko‘rsatadi:

front                                  rear
  ↓                                      ↓
[10 | next] → [20 | next] → [30 | NULL]

Rear reference bo‘lsa, yangi node oxiriga O(1) vaqtda ulanadi. Front reference esa birinchi node’ni O(1) vaqtda chiqaradi.

Enqueue

FUNCTION ENQUEUE_LINKED(queue, value)
    new_node = NEW NODE(value)

    IF queue.rear = NULL
        queue.front = new_node
        queue.rear = new_node
    ELSE
        queue.rear.next = new_node
        queue.rear = new_node

    queue.size = queue.size + 1

Bo‘sh queueda yangi node ham front, ham rear bo‘ladi. Bu edge case hisobga olinmasa, front NULL bo‘lib qolishi mumkin.

Dequeue

FUNCTION DEQUEUE_LINKED(queue)
    IF queue.front = NULL
        RETURN UNDERFLOW

    removed = queue.front
    queue.front = queue.front.next

    IF queue.front = NULL
        queue.rear = NULL

    queue.size = queue.size - 1
    RETURN removed.value

Oxirgi element olinganda front NULL bo‘ladi; rear ham NULLga o‘rnatilishi kerak. Aks holda rear navbatdan chiqarilgan eski node’ni ko‘rsatib qoladi.

Afzalligi va cheklovi

Linked list queue oldindan capacity talab qilmaydi va elementlarni resize paytida ko‘chirmaydi. ENQUEUE va DEQUEUE O(1). Buning evaziga har node next reference saqlaydi, alohida xotira ajratishni talab qiladi va tarqoq node’lar CPU cache bilan arraydan yomonroq ishlashi mumkin.

Queue turlari

Simple yoki linear queue

Simple queue odatiy FIFO model: element rear’dan kiradi, front’dan chiqadi. Linked list yoki to‘g‘ri circular array bilan amallar samarali bajariladi. “Linear” so‘zi ba’zan faqat oldinga yuruvchi, bo‘shagan bosh kataklarni qayta ishlatmaydigan fixed array implementatsiyasiga ham nisbatan ishlatiladi; kontekstni aniqlash muhim.

Printer navbati bunga real misol. Hujjatlar yuborilgan tartibda navbat oxiriga qo‘shiladi, printer esa frontdagi hujjatni olib chop etadi. Amaliy tizim katta yoki ustuvor hujjatlarga boshqa siyosat qo‘llashi mumkin, ammo oddiy FIFO printer queue kelish tartibini saqlaydi.

Circular queue

Circular queue fixed array kataklarini halqa bo‘ylab qayta ishlatadi. U doimiy buffer, streaming va oldindan ma’lum sig‘imli vazifalarda mos. Afzalligi — element ko‘chirmasdan O(1) amallar va yaxshi cache samaradorligi; cheklovi — fixed variant to‘lganda overflow siyosati kerak.

Deque

Deque (double-ended queue) — ikki tomonlama navbat. Unda elementni front va rear’ning ikkalasidan ham qo‘shish hamda olish mumkin:

PUSH_FRONT ← [ A, B, C ] → PUSH_BACK
POP_FRONT  ←             → POP_BACK

Deque oddiy queuedan kengroq interfeysga ega. Uni circular buffer yoki doubly linked list bilan qurish mumkin.

Real qo‘llanishlar:

• sliding window algoritmlarida oynadagi foydali nomzodlarni ikki tomondan boshqarish;
• work-stealing schedulerda worker o‘z vazifasini bir tomondan, boshqa worker esa boshqa tomondan olishi;
• palindrom tekshiruvda ikki chetdagi qiymatlarni taqqoslash;
• 0-1 BFS’da qirra og‘irligiga qarab node’ni old yoki orqaga qo‘shish.

Deque stack sifatida bir tomondan, queue sifatida esa bir tomondan qo‘shib boshqa tomondan olish orqali ishlashi mumkin. Ammo vazifa faqat FIFO bo‘lsa, oddiy queue interfeysi niyatni aniqroq ifodalaydi.

Priority queue

Priority queue elementlarni faqat kelish tartibida emas, ustuvorlik bo‘yicha chiqaradi. Masalan, tez yordam bo‘limida og‘ir holatdagi bemor keyin kelgan bo‘lsa ham oldin ko‘rilishi mumkin.

Elementlar kelishi:  A(past), B(yuqori), C(o‘rta)
Chiqish tartibi:     B, C, A

Priority queue oddiy FIFO queuening shunchaki boshqa nomi emas. U ko‘pincha heap asosida quriladi:

• eng ustuvor elementni ko‘rish O(1);
• qo‘shish O(log n);
• eng ustuvor elementni olish O(log n).

Teng ustuvorlikdagi elementlar FIFO tartibida chiqishi implementatsiya qo‘shimcha arrival order saqlashiga bog‘liq. Bu universal kafolat emas.

Priority queue vazifalar rejalashtirish, Dijkstra algoritmi va hodisalar simulyatsiyasida ishlatiladi. Oddiy queue esa BFS va adolatli kelish tartibi uchun mos.

Bounded va unbounded queue

Bounded queue maksimal capacity’ga ega. To‘lganda yangi element:

• rad etilishi;
• joy bo‘shaguncha kutishi;
• eski elementlardan birini chiqarishi;
• maxsus xato yoki signal qaytarishi

mumkin. Qaysi siyosat to‘g‘ri ekani tizim talabiga bog‘liq.

Unbounded queue tashqi ko‘rinishda qat’iy limit bermaydi, lekin haqiqiy xotira baribir cheklangan. Producer consumerdan uzoq vaqt tez ishlasa, navbat nazoratsiz o‘sib, butun dastur xotirasini tugatishi mumkin.

Bounded queue backpressure yaratishga yordam beradi: consumer ulgura olmaganda producer sekinlashadi yoki yangi ishni qabul qilmaydi. Bu real serverlar va streaming tizimlarida barqarorlik uchun muhim.

Asosiy amallar

Quyidagi pseudocode front, rear, size va capacity saqlaydigan circular array queueni asos qilib oladi.

Yaratish

FUNCTION CREATE_QUEUE(capacity)
    queue.items = capacity ta bo‘sh katak
    queue.front = 0
    queue.rear = 0
    queue.size = 0
    queue.capacity = capacity
    RETURN queue

Bucketlarning barchasini tayyorlash kerak bo‘lsa, vaqt va umumiy xotira O(capacity). Boshqaruv qiymatlari o‘zi O(1) joy oladi.

Enqueue

FUNCTION ENQUEUE(queue, value)
    IF queue.size = queue.capacity
        RETURN OVERFLOW

    queue.items[queue.rear] = value
    queue.rear = (queue.rear + 1) MOD queue.capacity
    queue.size = queue.size + 1

Fixed circular array yoki front/rear’li linked listda vaqt O(1). Dynamic array resize qilgan aniq enqueue O(n), amortized vaqt O(1).

Dequeue

FUNCTION DEQUEUE(queue)
    IF queue.size = 0
        RETURN UNDERFLOW

    value = queue.items[queue.front]
    queue.items[queue.front] = EMPTY
    queue.front = (queue.front + 1) MOD queue.capacity
    queue.size = queue.size - 1
    RETURN value

Element ko‘chirilmagani uchun vaqt O(1), yordamchi xotira O(1).

Peek

FUNCTION PEEK(queue)
    IF queue.size = 0
        RETURN UNDERFLOW

    RETURN queue.items[queue.front]

Front index yoki reference tayyor bo‘lgani uchun O(1). Navbat holati o‘zgarmaydi.

Is empty, is full va size

FUNCTION IS_EMPTY(queue)
    RETURN queue.size = 0

FUNCTION IS_FULL(queue)
    RETURN queue.size = queue.capacity

FUNCTION SIZE(queue)
    RETURN queue.size

Hisoblagich saqlangani sababli barcha amallar O(1). Linked list queueda capacity bo‘lmasligi mumkin, shunda IS_FULL xotira yoki tashqi limit siyosatiga bog‘liq.

Qidirish va traversal

Queue aniq qiymatni qidirish uchun optimallashtirilmagan. Eng yomon holatda barcha n ta element tekshiriladi — O(n). Circular arrayda traversal front’dan boshlanib mantiqiy tartibda yuradi:

FUNCTION TRAVERSE(queue)
    FOR offset = 0 DAN queue.size - 1 GACHA
        index = (queue.front + offset) MOD queue.capacity
        VISIT queue.items[index]

Traversal O(n) vaqt va iterativ ko‘rinishda O(1) yordamchi xotira ishlatadi.

O‘rtadagi elementni o‘chirish yoki yangilash

Klassik queue faqat frontdan o‘chiradi. O‘rtadagi elementni topish O(n), arrayda bo‘shliqni yopish uchun elementlarni siljitish ham O(n) bo‘lishi mumkin. Bunday amal tez-tez kerak bo‘lsa, queue to‘g‘ri abstraksiya emas.

Bosqichma-bosqich dry run

Capacity 4 bo‘lgan circular queue bilan ishlaymiz. front va rear keyingi o‘qish hamda yozish indexlarini bildiradi.

Boshlanish:
items = [_, _, _, _]
front = 0, rear = 0, size = 0

Uch element qo‘shamiz:

ENQUEUE(10): [10, _,  _,  _]   front=0, rear=1, size=1
ENQUEUE(20): [10, 20, _,  _]   front=0, rear=2, size=2
ENQUEUE(30): [10, 20, 30, _]   front=0, rear=3, size=3

Ikki element olamiz:

DEQUEUE() → 10
[_, 20, 30, _]                front=1, rear=3, size=2

DEQUEUE() → 20
[_, _, 30, _]                 front=2, rear=3, size=1

Yana ikki element qo‘shamiz:

ENQUEUE(40): [_,  _, 30, 40]  front=2, rear=0, size=2
ENQUEUE(50): [50, _, 30, 40]  front=2, rear=1, size=3

Rear 3dan keyin 0ga qaytdi. Jismoniy array [50, _, 30, 40], lekin FIFO tartib:

front → 30, 40, 50 ← rear tomoni

Bu dry run circular queueda index tartibi bilan mantiqiy navbat tartibini aralashtirmaslik kerakligini ko‘rsatadi.

Vaqt va xotira murakkabligi

Linked listda size hisoblagichi saqlanmasa SIZE O(n) bo‘lishi mumkin. Oddiy arraydan front elementni olib, barcha elementni siljitadigan noto‘g‘ri implementatsiyada DEQUEUE O(n) bo‘ladi.

n elementli queue umumiy O(n) xotira talab qiladi. Fixed circular arrayda aniq xotira O(capacity); bo‘sh kataklar ham ajratilgan joyni egallaydi. Linked listda har node uchun qo‘shimcha reference va allocation metadata bo‘lishi mumkin. Asosiy amallarning yordamchi xotirasi odatda O(1).

Queue va stack farqi

Ikkalasi ham elementlar kirib-chiqish tartibini cheklaydigan ADT, ammo qoidasi boshqa:

Kirish: A, B, C

Queue chiqishi: A, B, C
Stack chiqishi: C, B, A

Masala “navbat” so‘zini ishlatgani uchun avtomatik queue tanlanmaydi. Qaysi element keyingi qayta ishlanishi kerakligini aniqlash muhim.

Real qo‘llanishlar

Printer navbati

Bir nechta foydalanuvchi hujjat yuboradi. Hujjatlar queue rear’iga qo‘shiladi, printer frontdagi hujjatni oladi. Queue printer band paytda kelgan ishlarni yo‘qotmay, vaqtincha saqlaydi.

Amalda ustuvor hujjat, bekor qilish, qayta urinish va bir nechta printer bo‘lishi mumkin. Shunda oddiy FIFO queue qo‘shimcha metadata yoki priority queue bilan kengaytiriladi.

Server so‘rovlari va task queue

Web server yoki worker pool bir vaqtda cheklangan ishni bajara oladi. Kelgan vazifalar queuega qo‘yiladi, bo‘sh worker frontdan vazifa oladi. Queue qisqa trafik sakrashini yumshatadi.

Queue cheksiz o‘ssa, kechikish va xotira sarfi nazoratsiz ortadi. Shu sababli maksimal uzunlik, timeout, rad etish yoki backpressure siyosati real tizimning bir qismi bo‘ladi.

Breadth-first search

BFS graph yoki tree’ni boshlang‘ich node’dan masofa qatlamlari bo‘yicha ko‘radi. Topilgan qo‘shnilar rear’ga qo‘shiladi, keyingi node frontdan olinadi:

FUNCTION BFS(graph, start)
    queue = bo‘sh queue
    visited = bo‘sh set

    visited ga start ni qo‘sh
    queue.ENQUEUE(start)

    WHILE queue bo‘sh emas
        node = queue.DEQUEUE()
        VISIT node

        FOR har bir neighbor node qo‘shnilari ichida
            IF neighbor visited ichida bo‘lmasa
                visited ga neighbor ni qo‘sh
                queue.ENQUEUE(neighbor)

FIFO sababli oldingi qatlamdagi barcha node keyingi qatlamdan oldin qayta ishlanadi. Og‘irliksiz graphda shu xususiyat eng kam qirralar sonidan iborat yo‘lni topishga yordam beradi. Vaqt adjacency list bilan O(V + E), queue va visited uchun qo‘shimcha xotira O(V) bo‘lishi mumkin.

Xabar almashish

Producer xabar yaratadi, consumer keyinroq qayta ishlaydi. Queue ularning tezligi va ishlash vaqtini ajratadi. Ammo amaliy message broker faqat xotiradagi oddiy queuedan kattaroq tushuncha: persistence, acknowledgement, retry, ordering va delivery guarantee kabi qoidalar mavjud.

Streaming va qurilma bufferlari

Klaviatura bosishlari, tarmoq paketlari yoki audio namunalar consumer tayyor bo‘lguncha circular bufferda turishi mumkin. Fixed capacity xotira sarfini oldindan nazorat qiladi. To‘lish siyosati ma’lumot tabiatiga mos tanlanadi: audio real-time oqimda eski sample tashlanishi mumkin, moliyaviy tranzaksiyada esa yo‘qotish qabul qilinmaydi.

Hodisalar simulyatsiyasi

Oddiy vaqt tartibli hodisalarda queue ishlashi mumkin. Agar eng yaqin timestamp’li hodisa kelish tartibidan qat’i nazar birinchi bajarilishi kerak bo‘lsa, priority queue mosroq. Bu queue tanlashda FIFO bilan “eng muhim/eng erta” tartibini farqlash zarurligini ko‘rsatadi.

Keng tarqalgan algoritmik yondashuvlar

Level-order traversal

Tree node’lari darajama-daraja ko‘riladi. Har daraja boshida queuening joriy size qiymati olinadi; aynan shuncha node shu darajaga tegishli:

WHILE queue bo‘sh emas
    level_size = queue.SIZE()

    REPEAT level_size marta
        node = queue.DEQUEUE()
        node childlarini queuega qo‘sh

Loop davomida yangi childlar qo‘shilsa ham, ular keyingi darajada qayta ishlanadi, chunki level_size oldindan saqlangan.

Multi-source BFS

Bir nechta boshlang‘ich nuqtaning barchasi avval queuega qo‘shiladi. BFS ularning ta’sirini bir vaqtda qatlamlar bo‘yicha yoyadi. Masalan, gridda bir nechta yong‘in manbasidan har katakka eng yaqin masofani topish mumkin.

Sliding window va deque

Har uzunligi k bo‘lgan oynaning maksimumini topishda deque’da qiymatlar emas, foydali indexlar kamayuvchi tartibda saqlanadi. Yangi qiymatdan kichik nomzodlar rear’dan chiqariladi, oynadan chiqib ketgan index frontdan olinadi. Har index ko‘pi bilan bir marta kirib, bir marta chiqadi, shuning uchun umumiy vaqt O(n).

Ikki stackdan queue qurish

input va output stacklari ishlatiladi:

ENQUEUE(value):
    input.PUSH(value)

DEQUEUE():
    IF output bo‘sh bo‘lsa
        WHILE input bo‘sh emas
            output.PUSH(input.POP())

    RETURN output.POP()

Inputdan outputga ko‘chirish tartibni bir marta teskari qiladi. Har element inputga bir marta qo‘shilib, outputga bir marta ko‘chib, bir marta chiqadi. Ayrim dequeue O(n), ammo ketma-ket amallar uchun amortized vaqt O(1).

Queue bilan producer-consumer

Producer ishlarni enqueue, consumer dequeue qiladi. Bir nechta thread yoki process bo‘lsa, oddiy queue amallari o‘z-o‘zidan xavfsiz emas. Race conditionni oldini olish uchun lock, atomic operatsiya yoki maxsus concurrent queue kerak. “Queue ishlatildi” degani thread safety avtomatik ta’minlandi degani emas.

Afzalliklari

• FIFO tartibini aniq va tabiiy ifodalaydi.
• To‘g‘ri implementatsiyada enqueue, dequeue va peek O(1).
• Producer va consumer tezligi orasidagi qisqa farqni bufferlaydi.
• BFS, level-order traversal va kelish tartibli ishlarni sodda qiladi.
• Circular buffer fixed xotirani qayta-qayta samarali ishlatadi.
• Linked list oldindan capacity talab qilmasdan o‘sishi mumkin.

Bu afzallik o‘rtadagi elementlarga bevosita kirishdan voz kechish va navbat o‘sishini boshqarish zarurati evaziga keladi.

Cheklovlari

• Faqat frontdagi element to‘g‘ridan-to‘g‘ri olinadi.
• Qidirish va o‘rtadagi elementni o‘chirish O(n).
• Fixed queue to‘lganda overflow siyosati kerak.
• Unbounded queue nazoratsiz o‘sib, xotirani tugatishi mumkin.
• Dynamic array resize’i ayrim enqueue amallarini O(n) qiladi.
• Linked list har node uchun reference va allocation xarajatiga ega.
• FIFO ustuvor vazifalarni avtomatik oldinga chiqarmaydi.
• Parallel producer-consumer uchun sinxronizatsiya alohida hal qilinadi.

Keng tarqalgan xatolar va edge case’lar

Bo‘sh queuedan dequeue qilish

Bo‘sh queueda front element mavjud emas. DEQUEUE va PEEKdan oldin bo‘shlik tekshiriladi yoki API xato holatini aniq qaytaradi. Maxsus -1 qiymati noaniq bo‘lishi mumkin, chunki -1 haqiqiy element sifatida ham saqlanishi mumkin.

Array elementlarini har safar siljitish

Frontni doim 0da ushlab, DEQUEUEdan keyin barcha elementni siljitish amalni O(n) qiladi. Front index yoki circular buffer ishlatish element ko‘chirishni yo‘qotadi.

Circular indexda modulo unutish

Rear yoki front array oxiridan o‘tganda 0ga qaytmasa, index chegaradan chiqadi. Har yangilanish capacity bilan modulo qilinadi yoki unga teng ekvivalent wrap-around tekshiruvi ishlatiladi.

Bo‘sh va to‘la holatni aralashtirish

Faqat front = rear sharti ikkala holatni ifodalashi mumkin. Size, bo‘sh katak yoki alohida flag kabi aniq invariant tanlanmasa, queue to‘la paytda bo‘sh deb yoki aksincha ko‘rinadi.

Front va rear konvensiyalarini aralashtirish

Rear oxirgi mavjud elementnimi yoki keyingi bo‘sh kataknimi ko‘rsatadi — boshida tanlanadi. Pseudocode qismlarida turli konvensiyalarni aralashtirish off-by-one xato tug‘diradi.

Bitta elementli linked queue

Yagona node dequeue qilinganda front ham, rear ham NULL bo‘lishi kerak. Faqat frontni yangilash rear’da dangling yoki eskirgan reference qoldiradi.

Rear reference saqlamaslik

Singly linked list oxirini har enqueue’da boshidan qidirish O(n). Rear reference’ni saqlash enqueue’ni O(1) qiladi, ammo har o‘zgarishda uni to‘g‘ri yangilash shart.

Queue va priority queueni aralashtirish

Oddiy queue “eng oldin kelgan” elementni, priority queue esa “eng ustuvor” elementni chiqaradi. Vazifa favqulodda ishlarni oldinga chiqarishni talab qilsa, FIFO yetarli emas.

Queue uzunligini cheksiz deb qabul qilish

Unbounded API amalda cheksiz xotira degani emas. Producer uzoq vaqt tezroq bo‘lsa, latency va xotira o‘sadi. Capacity, timeout, rejection va backpressure siyosati oldindan belgilanadi.

Thread safety’ni taxmin qilish

Bir nechta worker bir paytda front/rear/size’ni o‘zgartirsa, yangilanishlar yo‘qolishi yoki bir element ikki marta olinishi mumkin. Concurrent muhit uchun sinxronlashtirilgan yoki lock-free queue talab qilinadi; oddiy DSA pseudocode buni kafolatlamaydi.

BFS’da visitedni juda kech belgilash

Node dequeue qilingandagina visited qilinsa, bir nechta qo‘shni ayni nodeni queuega takroran qo‘shishi mumkin. Ko‘p BFS implementatsiyalarida node enqueue qilingan zahoti visited belgilanadi. Bu takroriy navbatga tushishni oldini oladi.

Qachon queue ishlatish kerak?

Queue quyidagi talablar mavjud bo‘lganda mos:

• eng oldin kelgan element birinchi qayta ishlanishi kerak;
• producer va consumer orasida vaqtinchalik buffer zarur;
• BFS yoki level-order traversal bajariladi;
• printer, task yoki requestlar kelish tartibida boshqariladi;
• fixed-size oqim bufferi circular tartibda qayta ishlatiladi;
• ishlarni navbatga qo‘yib, keyin workerlarga tarqatish kerak;
• ikki chetdan boshqarish zarur bo‘lsa, deque varianti mos keladi.

Tanlovda faqat FIFO yetarli emas: maksimal uzunlik, to‘lish siyosati, parallel kirish va tartib kafolati ham aniqlanadi.

Qachon queue ishlatmaslik kerak?

Quyidagi holatlarda boshqa tuzilma yaxshiroq:

• Eng oxirgi element birinchi olinishi kerak bo‘lsa, stack LIFO tartibini beradi.
• Eng ustuvor element birinchi olinishi kerak bo‘lsa, priority queue yoki heap mos.
• Index bo‘yicha tasodifiy kirish kerak bo‘lsa, array yoki dynamic array tanlanadi.
• Kalit bo‘yicha tez lookup kerak bo‘lsa, hash table mosroq.
• O‘rtadagi elementlar tez-tez o‘chirilsa, queue interfeysi noqulay.
• Saralangan traversal yoki diapazon so‘rovi kerak bo‘lsa, balanced tree yoki saralangan tuzilma kerak.
• Ikki tomondan qo‘shish va olish kerak bo‘lsa, oddiy queue o‘rniga deque ishlatiladi.
• Producer oqimini cheklab bo‘lmasa va xotira chegaralangan bo‘lsa, oddiy unbounded queue muammoni yashirib, keyin xotira tanqisligiga olib keladi; bounded queue va backpressure siyosati zarur.

Queue ishlarni tezlashtirmaydi; u qaysi ish keyingi ekanini va ishlar kutayotgan paytda qayerda turishini boshqaradi.

Eng muhim xulosa

Queue elementlarni FIFO — “birinchi kirgan, birinchi chiqadi” tartibida boshqaradigan abstrakt ma’lumotlar turi. ENQUEUE rear tomonga qo‘shadi, DEQUEUE front tomondan oladi, PEEK esa frontni o‘zgartirmasdan ko‘rsatadi.

Oddiy arrayda har dequeue’dan keyin elementlarni siljitish O(n) va keraksiz. Circular queue front va rear indexlarini halqa bo‘ylab yurgizib, bo‘shagan kataklarni qayta ishlatadi va asosiy amallarni O(1) qiladi. Dynamic variant enqueue’ni amortized O(1)da bajaradi; resize bo‘lgan aniq amal O(n). Linked list queue front va rear reference’lari bilan ikkala asosiy amalni O(1)da bajaradi, lekin har node qo‘shimcha xotira talab qiladi.

Deque ikki tomondan ishlashga ruxsat beradi. Priority queue esa nomida “queue” bo‘lsa ham, elementni FIFO emas, ustuvorlik bo‘yicha chiqaradi. Bounded queue sig‘im va backpressure’ni boshqaradi; unbounded queue haqiqatan cheksiz emas.

Queue tanlashdan oldin to‘rtta savol bering:

1. Haqiqiy talab FIFO tartibimi?
2. Queue maksimal qancha o‘sishi mumkin?
3. To‘lganda producer va ma’lumot bilan nima sodir bo‘lishi kerak?
4. Bir nechta producer yoki consumer parallel ishlaydimi?

Queuedan keyingi tabiiy mavzu — tree va graph traversal. BFS queue yordamida node’larni qatlamma-qatlam ko‘radi, DFS esa stack yoki rekursiya bilan bir yo‘l bo‘ylab chuqurlashadi. Shu ikki traversalni taqqoslash queue va stackdagi FIFO/LIFO farqining algoritm natijasiga qanday ta’sir qilishini aniq ko‘rsatadi.