Stack tuzish

Queue tuzish masalasining aksi ham mavjud: faqat queue operatsiyalaridan foydalanib stack xatti-harakatini simulyatsiya qilish. Bu masala ham tuzilmalar o'rtasidagi fundamental tafovutni — LIFO va FIFO tartibining farqini — amaldagi ko'rinishda o'rgatadi.

Vazifa: faqat queue operatsiyalaridan foydalanib, quyidagi amallarni bajaradigan tuzilma yarating:

PUSH(value) — elementni stackka qo'shish;
POP() — eng tepa elementni olib tashlash;
TOP() — tepa elementni o'chirmasdan ko'rish;
IS_EMPTY() — stack bo'shligini tekshirish.

Muammo: queue LIFO tartibini bilmaydi

Queue elementni faqat rear'dan qabul qiladi va faqat front'dan chiqaradi. Siz PUSH qilgan eng so'nggi element queue oxirida turadi va boshqa barcha elementlar chiqib ketmaguncha u front'ga yetmaydi.

Stack esa tepadan ishlaydi: eng so'nggi element darhol POP qilinadi.

Bitta queue bilan bu farqni to'g'ridan-to'g'ri bartaraf etib bo'lmaydi. Lekin aylantirib (rotate) qilib — ya'ni, queue boshiga yangi elementni o'rnatib bo'ladi.

Asosiy g'oya: aylantirib boshga qo'yish

Yangi element PUSH qilinganda uni queue rear'iga qo'shamiz. Lekin so'ngra queuda nechta element bo'lsa, shuncha marta DEQUEUE→ENQUEUE qilib aylantirамiz. Bu orqali yangi element front'ga kelib qoladi — va u navbatdagi POP uchun birinchi bo'lib turadi.

PUSH arxitekturasi:

Queue: [A, B, C]   (front: A, rear: C)

PUSH(D):
    ENQUEUE(D)   → [A, B, C, D]

    Aylantiramiz (n-1 = 3 marta):
        DEQUEUE → A, ENQUEUE(A)   → [B, C, D, A]
        DEQUEUE → B, ENQUEUE(B)   → [C, D, A, B]
        DEQUEUE → C, ENQUEUE(C)   → [D, A, B, C]

Queue: [D, A, B, C]   (front: D)

Endi D front'da — POP qilinganda aynan u chiqadi. Bu LIFO tartibini beradi.

Algoritm

FUNCTION PUSH(queue, value)
    queue.ENQUEUE(value)

    n = queue.SIZE()

    REPEAT n-1 marta
        queue.ENQUEUE(queue.DEQUEUE())

FUNCTION POP(queue)
    IF queue.IS_EMPTY()
        RETURN UNDERFLOW
    RETURN queue.DEQUEUE()

FUNCTION TOP(queue)
    IF queue.IS_EMPTY()
        RETURN UNDERFLOW
    RETURN queue.PEEK()

FUNCTION IS_EMPTY(queue)
    RETURN queue.IS_EMPTY()

POP va TOP oddiy: queue front'da aynan tepa element turadigan tartib o'rnatilgan, shuning uchun ular to'g'ridan-to'g'ri queue amallarini chaqiradi.

Bosqichma-bosqich dry run

PUSH(1):
    ENQUEUE(1)   Queue: [1]
    n=1, n-1=0 ta aylanish (hech narsa qilinmaydi)

PUSH(2):
    ENQUEUE(2)   Queue: [1, 2]
    n=2, n-1=1 ta aylanish:
        DEQUEUE → 1, ENQUEUE(1)   Queue: [2, 1]

PUSH(3):
    ENQUEUE(3)   Queue: [2, 1, 3]
    n=3, n-1=2 ta aylanish:
        DEQUEUE → 2, ENQUEUE(2)   Queue: [1, 3, 2]
        DEQUEUE → 1, ENQUEUE(1)   Queue: [3, 2, 1]

POP():
    DEQUEUE → 3   Queue: [2, 1]

TOP():
    PEEK → 2   Queue: [2, 1]

POP():
    DEQUEUE → 2   Queue: [1]

POP():
    DEQUEUE → 1   Queue: []

LIFO tartib saqlandi: 3, 2, 1 ketma-ketlikda chiqdi.

Vaqt va xotira murakkabligi

PUSH qilinganda n-1 ta ENQUEUE/DEQUEUE juftligi bajariladi. n — push paytidagi stack elementi soni. Bu O(n) vaqt.

POP va TOP esa faqat queue front'iga kiradi — O(1).

Amal	Vaqt	Sabab
`PUSH`	`O(n)`	Queue n-1 marta aylantiriladi
`POP`	`O(1)`	Front elementni chiqarish
`TOP`	`O(1)`	Front elementni ko'rish
`IS_EMPTY`	`O(1)`	Queue holati tekshiriladi

Xotira: n ta elementni saqlash uchun O(n).

Ikki queue bilan alternativ yondashuv

Pop qimmat, push arzon bo'lgan boshqa yondashuv ham mavjud. Unda ikki queue ishlatiladi:

PUSH(value):
    main.ENQUEUE(value)

POP():
    WHILE main.SIZE() > 1
        temp.ENQUEUE(main.DEQUEUE())

    result = main.DEQUEUE()

    // main va temp ni almashtiramiz
    swap(main, temp)

    RETURN result

Bu yerda PUSH O(1), POP esa O(n). Hanuz ikkinchi queue xotirani egallaydi: asosiyda 0, temp'da n-1 element yoki aksincha.

PUSH(1): main: [1]            temp: []
PUSH(2): main: [1, 2]         temp: []
PUSH(3): main: [1, 2, 3]      temp: []

POP():
    main size = 3 > 1:
        DEQUEUE(1) → temp.ENQUEUE(1)   main: [2, 3]   temp: [1]
        DEQUEUE(2) → temp.ENQUEUE(2)   main: [3]       temp: [1, 2]
    main.DEQUEUE() → 3
    swap: main ↔ temp
    main: [1, 2]   temp: []
    result: 3

Ikkita yondashuvni taqqoslash

Xususiyat	Push qimmat (1 queue)	Pop qimmat (2 queue)
`PUSH`	`O(n)`	`O(1)`
`POP`	`O(1)`	`O(n)`
`TOP`	`O(1)`	`O(n)`
Qo'shimcha xotira	`O(1)` (1 queue)	`O(n)` (2 queue)

Tez-tez push, kamdan kam pop bo'lsa — "pop qimmat" (2 queue) usuli yaxshiroq. Tez-tez pop, kamdan kam push bo'lsa — "push qimmat" (1 queue) usuli yaxshiroq.

Edge case'lar

Bo'sh stackdan POP. Queue bo'sh bo'lsa underflow qaytariladi. Har ikkala usulda ham avval IS_EMPTY tekshiriladi.

Bitta element. PUSH(5) — queue: [5], n=1, n-1=0 ta aylanish. POP → 5. To'g'ri.

PUSH keyin darhol POP. Stack mantig'i bo'yicha eng so'nggi push birinchi pop bo'lishi kerak. Yuqoridagi dry runda PUSH(1), PUSH(2), PUSH(3), POP() → 3. To'g'ri.

Note

1 queue usulida PUSH paytida queue.SIZE() qiymati n bo'lsa, n-1 marta aylantiriladi — ya'ni, push qilinayotgan element n-1 ta oldindagi elementni ortida qoldiradi. Bu formulani n ta emas n-1 ta qilib yozish muhim: n ta aylantirilsa yangi element yana rear'ga kelib qoladi.

Nega bu masala foydali?

Queue bilan stack tuzish bir-birining qiyosi. Ikkala masala ham quyidagi tushunchalarni mustahkamlaydi:

Stack va queue tashqi interfeysdan emas, kirish-chiqish tartibidan farq qiladi.
Bir ADT boshqasidan qurilishi mumkin, lekin narxi bo'ladi: aylantirishlar yoki ikkinchi tuzilma.
Amortized tahlil qimmat amalni bir operatsiya sifatida emas, jami amallar uchun o'rtacha sifatida ko'radi.

Xulosa

Queue bilan stack qurish "queue aylantirish = tartibni o'zgartirish" g'oyasiga asoslanadi. Push qimmat usulida yangi element darhol front'ga o'rnatiladi, shuning uchun pop va top O(1). Pop qimmat usulida esa push tez bo'ladi, pop esa barcha elementlarni ko'chirib yuborib oxirgi elementni topadi.

Ikki yondashuv o'rtasidagi tanlov qaysi amal ko'proq bajarilishiga bog'liq.