Tarkibga o'tish

Queue tuzish

Stack va queue ziddiyatli ko'rinadi: stack eng oxirgi qo'shilgan elementni birinchi chiqarsa, queue eng oldin qo'shilgan elementni birinchi chiqaradi. Lekin ikki stackni birga ishlatib, queue xatti-harakatini simulyatsiya qilish mumkin. Bu masala stackning ichki mantiqini chuqurroq tushunishga yordam beradi va amortized tahlilning amaliy namunasidir.

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

  • ENQUEUE(value) — elementni navbatga qo'shish;
  • DEQUEUE() — navbatdagi birinchi elementni olib tashlash;
  • PEEK() — birinchi elementni o'chirmasdan ko'rish;
  • IS_EMPTY() — navbat bo'shligini tekshirish.

Nima uchun ikki stack?

Bir stack bilan FIFO tartibini saqlab bo'lmaydi: push va pop bir uchdan ishlaydi. Ikkala stack yordamida esa tartibni ikki marta teskari qilish mumkin:

  • bir marta teskari qilish LIFO hosil qiladi;
  • ikki marta teskari qilish asl tartibni qaytaradi — ya'ni FIFO.
Boshlang'ich tartib: A, B, C
Stack 1ga push qilamiz: [A, B, C]  (top = C)

Stack 1dan pop qilib Stack 2ga push:
    Stack 2: [C, B, A]  (top = A)

Stack 2dan pop tartibi: A, B, C   ← asl tartib

Ikki stack g'oyasi

input stacki yangi elementlarni qabul qiladi. output stacki esa chiqarish uchun ishlatiladi.

  • Enqueue: yangi elementni input stackka PUSH qilamiz.
  • Dequeue: output bo'sh bo'lsa, inputdagi barcha elementlarni outputga o'tkazamiz, so'ng outputdan POP qilamiz.
ENQUEUE:
    input.PUSH(value)

DEQUEUE:
    IF output.IS_EMPTY()
        WHILE input.IS_EMPTY() emas
            output.PUSH(input.POP())

    IF output.IS_EMPTY()
        RETURN UNDERFLOW

    RETURN output.POP()

PEEK:
    IF output.IS_EMPTY()
        WHILE input.IS_EMPTY() emas
            output.PUSH(input.POP())

    IF output.IS_EMPTY()
        RETURN UNDERFLOW

    RETURN output.PEEK()

IS_EMPTY:
    RETURN input.IS_EMPTY() VA output.IS_EMPTY()

Bosqichma-bosqich dry run

Quyidagi amallar ketma-ketligini bajaramiz:

ENQUEUE(1)
ENQUEUE(2)
ENQUEUE(3)
DEQUEUE()
ENQUEUE(4)
DEQUEUE()
DEQUEUE()

ENQUEUE(1):
    input.PUSH(1)
    input: [1]     output: []

ENQUEUE(2):
    input.PUSH(2)
    input: [1, 2]  output: []

ENQUEUE(3):
    input.PUSH(3)
    input: [1, 2, 3]  output: []
    (top = 3)

DEQUEUE():
    output bo'sh → input'dan output'ga ko'chirish:
        POP(3) → output.PUSH(3)   output: [3]
        POP(2) → output.PUSH(2)   output: [3, 2]
        POP(1) → output.PUSH(1)   output: [3, 2, 1]
        input: []
    output.POP() → 1
    input: []  output: [3, 2]

ENQUEUE(4):
    input.PUSH(4)
    input: [4]  output: [3, 2]

DEQUEUE():
    output bo'sh emas → to'g'ridan output.POP() → 2
    input: [4]  output: [3]

DEQUEUE():
    output bo'sh emas → output.POP() → 3
    input: [4]  output: []

FIFO tartib saqlanganini ko'rish mumkin: 1, 2, 3 ketma-ketlikda chiqdi, 4 esa hali inputda turadi.

Amortized tahlil

DEQUEUE amali ba'zan O(n) ko'rinadi, chunki barcha elementlarni outputga ko'chirishi kerak. Lekin bu qanday tez-tez sodir bo'ladi?

Ko'chirish faqat output bo'shaganda bajariladi. Har element hayoti davomida:

  1. inputga bir marta PUSH qilinadi (ENQUEUE paytida);
  2. inputdan bir marta POP qilinadi (ko'chirish paytida);
  3. outputga bir marta PUSH qilinadi (ko'chirish paytida);
  4. outputdan bir marta POP qilinadi (DEQUEUE paytida).

Jami 4 ta operatsiya — O(1) amortized.

Amortized tahlildan amaliy xulosasi shuki, bitta DEQUEUE O(n) bo'lishi mumkin, lekin ketma-ket n ta DEQUEUE jami O(n) vaqt oladi. Har DEQUEUE uchun o'rtacha O(1).

Amal Eng yomon holat Amortized
ENQUEUE O(1) O(1)
DEQUEUE O(n) O(1)
PEEK O(n) O(1)
IS_EMPTY O(1) O(1)

Eng yomon holat DEQUEUE — bu ko'p ENQUEUEdan keyin birinchi DEQUEUE. Undan keyingi DEQUEUElar esa output bo'shagunga qadar barchasi O(1).

Yordamchi xotira

input va output stacklari birgalikda n ta elementni saqlaydi — bittasi inputda bo'lsa, boshqasida bo'lmaydi. Umumiy xotira O(n).

Har bir stack alohida ma'lumot sifatida yaratilsa, ikki tuzilma uchun qo'shimcha overhead bo'lishi mumkin, lekin bu elementlar soni bilan o'smaydi.

Edge case'lar

Bo'sh navbatdan DEQUEUE. Agar input ham, output ham bo'sh bo'lsa, underflow qaytariladi. Faqat bitta bo'shligini tekshirish yetarli emas: input bo'sh bo'lsa ham outputda element bo'lishi mumkin.

ENQUEUE va DEQUEUE aralashganda output'da elementlar bo'lishi. output bo'sh bo'lmagan paytda ENQUEUE qilinsa, yangi elementlar inputga boradi. Keyingi DEQUEUE uchun outputdagi eski elementlar avval chiqariladi — FIFO tartib to'g'ri.

Bitta element. ENQUEUE(5), DEQUEUE() — input: [5], ko'chirish: output: [5], POP → 5. To'g'ri.

Note

IS_EMPTY faqat input.IS_EMPTY() emas, balki ikkalasini tekshirishi kerak. Aks holda outputda elementlar bo'lsa ham bo'sh deb qaytarishi mumkin.

Push-heavy alternativ

Boshqa yondashuv: enqueue qimmat, dequeue arzon.

ENQUEUE qilinganda yangi element boshqa stackga o'tkaziladi va tartibni saqlab ketma-ketlik boshiga qo'yiladi:

ENQUEUE(value):
    temp = bo'sh stack

    WHILE stack bo'sh emas
        temp.PUSH(stack.POP())

    stack.PUSH(value)

    WHILE temp bo'sh emas
        stack.PUSH(temp.POP())

DEQUEUE():
    IF stack.IS_EMPTY()
        RETURN UNDERFLOW
    RETURN stack.POP()

Bu holatda DEQUEUE O(1), lekin ENQUEUE har safar O(n). Tez-tez enqueue, kamdan kam dequeue bo'lsa bu noqulay.

Ikki stack yondashuvi (pop-heavy bo'lgan birinchi usul) tez-tez enqueue bo'lganda yaxshiroq, chunki enqueue har doim O(1).

Nega bu masala foydali?

Queue tuzish masalasi sof amaliy muammo emas. Bu masala quyidagilarni tushunishga yordam beradi:

  • ADT (abstrakt ma'lumotlar turi) va implementatsiya o'rtasidagi farq. Stack va queue har xil tartibda ishlaydi, lekin ikkisi ham arraydan yoki linked listdan qurilishi mumkin.
  • Amortized tahlil. Bitta operatsiya qimmat ko'rinsa ham, ketma-ket operatsiyalar uchun o'rtacha arzon bo'lishi mumkin.
  • Tuzilmalarni boshqasidan qurish. Ko'p real tuzilmalar oddiyroq qismlardan quriladi.

Xulosa

Ikki stackdan queue qurish "ikki teskari = to'g'ri tartib" g'oyasiga asoslanadi. input stack yangi elementlarni qabul qiladi, output stack esa ularni FIFO tartibida chiqaradi. Ko'chirish faqat output bo'shaganda bajarilgani uchun har element umri davomida doimiy miqdorda amallar bajaradi. Bu ENQUEUEni O(1), DEQUEUEni amortized O(1) qiladi.