Stack

Tasavvur qiling, stol ustiga likopchalarni birma-bir taxlayapsiz. Yangi likopcha doim eng tepaga qo‘yiladi. Likopcha kerak bo‘lganda ham avval eng tepadagisini olasiz. Pastdagi likopchani olish uchun uning ustidagilarni avval olib tashlashga to‘g‘ri keladi.

Stack — elementlarni aynan shu tartibda boshqaradigan ma’lumotlar tuzilmasi. Unga eng oxirida qo‘shilgan element birinchi bo‘lib olinadi. Bu qoida LIFO (Last In, First Out) — “oxirgi kirgan, birinchi chiqadi” deb ataladi.

           ┌──────────┐
top    →   │    40    │  ← eng oxirgi qo‘shilgan
           ├──────────┤
           │    30    │
           ├──────────┤
           │    20    │
           ├──────────┤
bottom →   │    10    │  ← eng oldin qo‘shilgan
           └──────────┘

Stackning muhim cheklovi shuki, elementlar bilan faqat bitta tomondan — top, ya’ni tepa qismidan ishlanadi. Yangi element topga qo‘shiladi, element ham topdan olinadi. Shu cheklov ayrim vazifalarni juda sodda va samarali qiladi: orqaga qaytish, ichma-ich tuzilmalarni tekshirish, bajarilayotgan funksiyalar holatini saqlash va eng yaqin oldingi elementni topish shular jumlasidan.

Stack elementlarni xotirada qanday joylashtirishni o‘zi belgilamaydi. U avvalo abstrakt ma’lumotlar turi (abstract data type, ADT) — ruxsat etilgan amallar va ularning xatti-harakatini belgilaydigan mantiqiy modeldir. Uni array, dynamic array yoki linked list ustiga qurish mumkin. Foydalanuvchi uchun LIFO qoidasi o‘zgarmaydi, ammo xotira xarajati va ayrim nozik murakkabliklar implementatsiyaga qarab farq qiladi.

Likopchalar analogiyasidan texnik modelga

Likopchalar taxlamida faqat eng yuqori likopchaga bevosita yetish mumkin. Stackda ham quyidagi asosiy amallar top atrofida bajariladi:

• yangi elementni tepaga qo‘yish — PUSH;
• tepadagi elementni olib tashlash — POP;
• tepadagi elementni olib tashlamasdan ko‘rish — PEEK yoki TOP;
• stack bo‘shligini tekshirish — IS_EMPTY;
• elementlar sonini bilish — SIZE.

PUSH(40)                         POP()

    40                               40 ← olinadi
    ↓                                ↑
┌──────┐                         ┌──────┐
│  30  │                         │  30  │ ← yangi top
├──────┤                         ├──────┤
│  20  │                         │  20  │
└──────┘                         └──────┘

Analogiyada likopchalar jismonan vertikal turadi. Kompyuter xotirasidagi stack esa albatta yuqoriga qarab chizilgan bo‘lishi shart emas. Array implementatsiyasida elementlar yonma-yon, linked list implementatsiyasida esa xotiraning turli joylarida turishi mumkin. “Top” jismoniy yo‘nalish emas, keyingi POP qaysi elementni olishini bildiradigan mantiqiy tushuncha.

Asosiy terminlar

Top va bottom

Top — stackdagi keyingi POP yoki PEEK amali ishlaydigan tomon. Bottom — eng oldin qo‘shilgan element joylashgan qarama-qarshi chet.

Topdagi elementga tez kirish stackning asosiy xususiyati. Bottom yoki o‘rtadagi elementga bevosita kirish klassik stack interfeysining vazifasi emas.

Push

PUSH(value) yangi qiymatni stack topiga qo‘shadi. Oldingi top yangi elementning ostida qoladi.

Pop

POP() topdagi elementni stackdan chiqaradi va odatda uning qiymatini qaytaradi. Bu amal stack holatini o‘zgartiradi.

Peek yoki top

PEEK() topdagi qiymatni ko‘rsatadi, lekin uni o‘chirmaydi. POPdan farqli ravishda stack hajmi o‘zgarmaydi.

LIFO

LIFO elementlarning kelish va ketish tartibi o‘rtasidagi qoidani bildiradi:

PUSH(A), PUSH(B), PUSH(C)

POP tartibi: C, B, A

Underflow va overflow

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

Dynamic stackda sig‘im avtomatik kengayishi mumkin, ammo xotira cheksiz emas. “Dynamic stackda overflow umuman bo‘lmaydi” deyish noto‘g‘ri; amalda xotira ajratish muvaffaqiyatsiz bo‘lishi mumkin.

Stack nima sababdan bitta tomondan ishlaydi?

Stackning cheklovi uning foydasini yaratadi. Agar o‘rtadagi yoki pastdagi elementni istalgan payt olish mumkin bo‘lsa, LIFO tartibiga tayanadigan algoritmning holatini tushunish qiyinlashadi. Bitta tomondan ishlash quyidagilarni kafolatlaydi:

• eng yangi holat birinchi qayta ishlanadi;
• oldingi holatlar tabiiy ravishda teskari tartibda saqlanadi;
• topni boshqarish uchun odatda bitta index yoki reference yetadi;
• asosiy amallar ko‘pincha O(1) vaqtda bajariladi.

Masalan, matn muharririda foydalanuvchi oxirgi bajargan amal birinchi bekor qilinishi kerak. Har yangi amal undo stack topiga qo‘shiladi. Undo bosilganda aynan eng so‘nggi amal olinadi. Bu holatda LIFO cheklovi muammoning o‘zidagi tartib bilan mos keladi.

Stack xotirada qanday ifodalanadi?

Stackning ikki klassik implementatsiyasi bor:

1. array yoki dynamic array asosidagi stack;
2. linked list asosidagi stack.

Ikkalasi bir xil tashqi amallarni beradi, ammo ichkarida boshqa mexanizm ishlatadi.

Fixed-size array asosidagi stack

Oldindan belgilangan capacity’li array va top o‘rnini ko‘rsatuvchi index saqlanadi. Ushbu maqolada top oxirgi mavjud element indexini bildiradi deb olamiz. Bo‘sh stackda top = -1:

Capacity: 5

Index:      0       1       2       3       4
          +-------+-------+-------+-------+-------+
Element:  |  10   |  20   |  30   | bo‘sh | bo‘sh |
          +-------+-------+-------+-------+-------+
                            ↑
                          top = 2

Ba’zi implementatsiyalar topni keyingi bo‘sh index yoki size sifatida saqlaydi. Masalan, yuqoridagi holatda size = 3. Qaysi konvensiya ishlatilishidan qat’i nazar, chegaralar izchil boshqarilishi kerak.

Push ichkarida qanday ishlaydi?

1. stack to‘la emasligi tekshiriladi;
2. top bittaga oshiriladi;
3. yangi qiymat array[top]ga yoziladi.

FUNCTION PUSH(stack, value)
    IF stack.top = stack.capacity - 1
        RETURN OVERFLOW

    stack.top = stack.top + 1
    stack.items[stack.top] = value

Array indexi orqali yozish va topni yangilash doimiy miqdordagi ish, shuning uchun vaqt O(1). Yangi array yaratilmaydi; amalning qo‘shimcha xotirasi O(1).

Pop ichkarida qanday ishlaydi?

1. stack bo‘sh emasligi tekshiriladi;
2. array[top] qiymati vaqtincha olinadi;
3. top bittaga kamaytiriladi;
4. olingan qiymat qaytariladi.

FUNCTION POP(stack)
    IF stack.top = -1
        RETURN UNDERFLOW

    value = stack.items[stack.top]
    stack.top = stack.top - 1
    RETURN value

Bu ham O(1) vaqt va O(1) qo‘shimcha xotira talab qiladi. Eski katakdagi bitlar darhol tozalanmasligi mumkin, lekin mantiqiy stack uchun topdan keyingi hudud bo‘sh hisoblanadi. Agar katak obyekt reference’ini saqlasa, keraksiz obyektning xotirada ushlanib qolmasligi uchun implementatsiya uni bo‘sh qiymatga almashtirishi mumkin.

Fixed-size arrayning afzalligi va cheklovi

Elementlar yonma-yon joylashgani sababli xotira ixcham va CPU cache uchun qulay. Har elementga alohida node yoki reference kerak emas. Lekin capacity oldindan tanlanadi: juda kichik bo‘lsa overflow, juda katta bo‘lsa bo‘sh kataklar xotirani band qiladi.

Fixed-size stack maksimal chuqurlik aniq bo‘lgan joyda foydali. Masalan, embedded qurilmada ruxsat etilgan operatsiyalar soni qat’iy cheklangan bo‘lsa, oldindan xotira ajratish ish vaqtida yangi allocationlardan qochadi.

Dynamic array asosidagi stack

Dynamic array tashqi ko‘rinishda o‘sib boradi, lekin ichida ma’lum capacity’li array saqlaydi. Joy tugaganda kattaroq array yaratilib, eski elementlar unga ko‘chiriladi:

Eski capacity = 4
[10][20][30][40]

PUSH(50) uchun joy yo‘q
          ↓
Yangi capacity = 8
[10][20][30][40][50][ ][ ][ ]

Oddiy PUSH bo‘sh capacity mavjud bo‘lsa O(1). Kengayish sodir bo‘lgan aniq PUSH barcha n ta elementni ko‘chirishi sabab O(n). Capacity geometrik o‘ssa, masalan, taxminan ikki barobar qilinsa, ko‘p PUSH amallarining amortized vaqti O(1) bo‘ladi.

Amortized O(1) — har bir PUSH albatta doimiy vaqt oladi degani emas. Kamdan kam qimmat kengayish xarajati uning oldidagi va keyingi ko‘plab arzon amallar orasiga taqsimlanadi.

Dynamic array stack amaliy dasturlarda keng tanlanadi: elementlar xotirada zich joylashadi, top index orqali tez boshqariladi va ko‘p mayda node allocation talab qilmaydi. Kengayish paytida vaqtinchalik katta xotira va elementlarni ko‘chirish xarajati uning cheklovidir.

Linked list asosidagi stack

Singly linked listning boshini stack topi sifatida ishlatish mumkin:

top
 ↓
[30 | next] → [20 | next] → [10 | NULL]

PUSH yangi node’ni list boshiga ulaydi:

FUNCTION PUSH_LINKED(stack, value)
    new_node = NEW NODE(value)
    new_node.next = stack.top
    stack.top = new_node
    stack.size = stack.size + 1

POP birinchi node’ni chiqaradi:

FUNCTION POP_LINKED(stack)
    IF stack.top = NULL
        RETURN UNDERFLOW

    removed = stack.top
    stack.top = stack.top.next
    stack.size = stack.size - 1
    RETURN removed.value

Ikkala amal ham O(1), chunki list bo‘ylab yurish shart emas. Yangi node uchun O(1) qo‘shimcha xotira ajratiladi.

Linked list stack oldindan capacity talab qilmaydi va elementlarni resize paytida ko‘chirmaydi. Buning evaziga har node next reference’ini saqlaydi, alohida allocation talab qiladi va node’lar tarqoq joylashgani sabab CPU cache bilan dynamic arraydan yomonroq ishlashi mumkin.

Array va linked list implementatsiyalarini taqqoslash

Big O jadvalida ikkala implementatsiya o‘xshash ko‘rinsa ham, amaliy tezlik va xotira xarajati farq qiladi. Odatda dynamic array stack yaxshi boshlang‘ich tanlov. Barqaror node reference’lari, oldindan noma’lum o‘sish yoki maxsus node boshqaruvi kerak bo‘lsa linked list ko‘rib chiqiladi.

Stackning asosiy amallari

Stack yaratish

Dynamic stack bo‘sh kolleksiya va size = 0 bilan boshlanadi:

FUNCTION CREATE_STACK()
    stack.items = bo‘sh dynamic array
    stack.size = 0
    RETURN stack

Tashqi boshqaruv ma’lumotlarini yaratish O(1). Agar boshlang‘ich capacity’li arrayning barcha kataklarini tayyorlash kerak bo‘lsa, yaratish va xotira O(capacity) deb qaralishi mumkin.

Push

FUNCTION PUSH(stack, value)
    IF ichki array to‘la bo‘lsa
        uni kattalashtir

    stack.items[stack.size] = value
    stack.size = stack.size + 1

Kutiladigan yoki amortized vaqt O(1), resize bo‘lgan bitta amal O(n). Fixed-size array yoki linked listda resize bo‘lmasa, muvaffaqiyatli PUSH O(1).

Pop

FUNCTION POP(stack)
    IF stack.size = 0
        RETURN UNDERFLOW

    stack.size = stack.size - 1
    value = stack.items[stack.size]
    stack.items[stack.size] = EMPTY
    RETURN value

Top joyi ma’lum bo‘lgani uchun vaqt O(1), qo‘shimcha xotira O(1). EMPTY yozish mantiqiy natijani o‘zgartirmaydi, ammo reference saqlanadigan muhitda obyektni keraksiz ushlab turishni oldini olishi mumkin.

Peek

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

    RETURN stack.items[stack.size - 1]

PEEK qiymatni o‘chirmaydi. Index hisoblash va bitta o‘qish sababli vaqt O(1), xotira O(1).

Is empty va size

FUNCTION IS_EMPTY(stack)
    RETURN stack.size = 0

FUNCTION SIZE(stack)
    RETURN stack.size

size alohida saqlansa, ikkala amal O(1). Linked listda size saqlanmasa, elementlar sonini bilish uchun barcha node’larni yurib chiqish O(n) bo‘ladi. Qulay O(1) size har PUSH va POPda hisoblagichni to‘g‘ri yangilash mas’uliyati evaziga keladi.

Traversal va qidirish

Klassik stack interfeysi faqat top bilan ishlashga mo‘ljallangan. Barcha elementni ko‘rish yoki qiymat qidirish talab qilinsa, n ta elementni tekshirish kerak — O(n).

Elementlarni POP qilib ko‘rish stackni buzadi. Uni saqlash kerak bo‘lsa, qayta tiklash uchun yordamchi stack ishlatilishi mumkin, bu O(n) qo‘shimcha xotira oladi. Ayrim implementatsiya ichki array bo‘ylab o‘qishga ruxsat beradi, ammo bu stack ADT’ning universal amali emas.

Yangilash

Top qiymatni POP va PUSH bilan yoki maxsus REPLACE_TOP amali bilan O(1) yangilash mumkin. O‘rtadagi elementni index bo‘yicha yangilash klassik stack semantikasini chetlab o‘tadi. Bunday talab tez-tez bo‘lsa, dynamic array yoki boshqa kolleksiyani bevosita ishlatish to‘g‘riroq.

Bosqichma-bosqich dry run

Bo‘sh stack ustida quyidagi amallarni bajaramiz:

PUSH(10)
PUSH(20)
PUSH(30)
PEEK()
POP()
PUSH(40)

Bosqichlar:

Boshlanish:  []

PUSH(10):    [10]
               ↑ top

PUSH(20):    [10, 20]
                   ↑ top

PUSH(30):    [10, 20, 30]
                       ↑ top

PEEK():      30 qaytadi, stack o‘zgarmaydi
             [10, 20, 30]

POP():       30 qaytadi
             [10, 20]
                   ↑ top

PUSH(40):    [10, 20, 40]
                       ↑ top

Oxirgi natijada 30 yo‘q, 40 topda. 10 birinchi qo‘shilgan bo‘lsa ham, uning ustidagi elementlar olinmaguncha u POP orqali chiqmaydi.

Vaqt va xotira murakkabligi

Big O real bajarilish sekundini emas, elementlar soni oshganda ish miqdori qanday o‘sishini bildiradi. O(1) amal “nol vaqt” degani emas; stackda 10 yoki million element bo‘lishidan qat’i nazar bir xil miqdordagi top boshqaruvi bajarilishini anglatadi.

SIZE linked list implementatsiyasida hisoblagich saqlanmasa O(n) bo‘lishi mumkin.

n ta element saqlaydigan stackning umumiy xotirasi O(n). Dynamic array capacity sabab ndan ko‘proq katak ajratishi, linked list esa har element uchun reference saqlashi mumkin. Asosiy amallarning yordamchi xotirasi odatda O(1).

Stack ADT va call stack bir xil emas

Stack ADT — dasturchi ma’lumotlarni LIFO tartibida saqlash uchun ishlatadigan umumiy model. Call stack — dastur runtime’i funksiya chaqiruvlarini boshqarish uchun ishlatadigan maxsus stack.

Funksiya chaqirilganda call stackka odatda yangi stack frame qo‘shiladi. Freym parametrlar, lokal o‘zgaruvchilar, qaytish manzili va boshqa xizmat ma’lumotlarini saqlashi mumkin. Funksiya tugaganda uning freymi chiqariladi:

MAIN chaqirildi
    A chaqirildi
        B chaqirildi

Call stack top:
┌──────────────┐
│ B freymi     │ ← birinchi tugaydi
├──────────────┤
│ A freymi     │
├──────────────┤
│ MAIN freymi  │
└──────────────┘

Rekursiyada funksiya o‘zini qayta chaqirgani sababli bir xil funksiya uchun ko‘p alohida freym stackka qo‘shiladi. Chuqurlik juda katta bo‘lsa call stack xotirasi tugab, stack overflow yuz berishi mumkin.

Real qo‘llanishlar

Matn muharriridagi undo va redo

Har bajarilgan amal undo stackka qo‘shiladi. Foydalanuvchi Undo bosganda oxirgi amal olinib, uning teskarisi bajariladi va amal redo stackka o‘tkaziladi:

Yangi amal:
    undo.PUSH(amal)
    redo ni tozalash

Undo:
    amal = undo.POP()
    amalni bekor qilish
    redo.PUSH(amal)

Redo:
    amal = redo.POP()
    amalni qayta bajarish
    undo.PUSH(amal)

Undo’dan keyin yangi amal bajarilsa, eski redo yo‘li odatda endi haqiqiy tarix bo‘lmagani uchun tozalanadi. Murakkab, tarmoqlanuvchi tarix uchun oddiy ikkita stack yetmasligi mumkin.

Brauzer navigatsiyasi

Soddalashtirilgan modelda orqaga va oldinga tarix uchun ikkita stack ishlatiladi. Yangi sahifaga o‘tilganda joriy sahifa back stackka qo‘shilib, forward stack tozalanadi. Back amali joriy sahifani forward stackka, back stackdagi top sahifani esa joriy holatga o‘tkazadi.

Amaliy brauzerlar tablar, redirectlar, sahifa holati va xavfsizlik sabab bundan murakkab tarix modeliga ega bo‘lishi mumkin, lekin LIFO mantig‘i navigatsiyaning asosiy qismini yaxshi tushuntiradi.

Qavslarni tekshirish

Matndagi (), [], {} qavslar to‘g‘ri yopilganini stack bilan tekshirish mumkin. Ochuvchi qavs stackka qo‘shiladi. Yopuvchi qavs uchraganda topdagi ochuvchi qavs unga mos bo‘lishi kerak:

FUNCTION VALID_BRACKETS(text)
    stack = bo‘sh stack

    FOR har bir symbol text ichida
        IF symbol ochuvchi qavs bo‘lsa
            stack.PUSH(symbol)

        ELSE IF symbol yopuvchi qavs bo‘lsa
            IF stack bo‘sh bo‘lsa
                RETURN FALSE

            opening = stack.POP()

            IF opening va symbol mos kelmasa
                RETURN FALSE

    RETURN stack bo‘sh

Nima uchun oxirida stack bo‘shligi tekshiriladi? "((" matnida noto‘g‘ri yopuvchi qavs yo‘q, ammo ikkita ochuvchi qavs yopilmay qolgan. Vaqt O(n), eng yomon yordamchi xotira O(n).

Ifodalarni hisoblash

Operatorlar ustuvorligini boshqarish, infix ifodani postfixga aylantirish yoki postfix ifodani hisoblashda stack ishlatiladi. Postfix misolida sonlar stackka qo‘shiladi; operator uchraganda kerakli operandlar topdan olinadi, natija yana stackka qo‘yiladi.

Postfix: 2 3 + 4 *

2 → [2]
3 → [2, 3]
+ → [5]
4 → [5, 4]
* → [20]

Ayirish va bo‘lish kabi amallarda operand tartibi muhim. Stackdan birinchi chiqqan qiymat odatda o‘ng operand, ikkinchisi chap operand bo‘ladi.

DFS va backtracking

Depth-first search bir yo‘l bo‘ylab imkon qadar chuqur borib, keyin oldingi tanlovga qaytadi. Rekursiv DFS call stackdan yashirin foydalanadi; iterativ DFS esa node’larni explicit stackda saqlaydi. Labirint, graph traversal va backtracking masalalarida qaytish nuqtalari LIFO tartibiga mos.

Dastur interpreterlari va virtual mashinalar

Ba’zi virtual mashinalar operand stackdan foydalanadi. Instruksiya qiymatlarni stackka qo‘yadi, operator esa topdagi operandlarni olib natijani qaytaradi. Bu model instruktsiyalarni sodda formatda ifodalashga yordam beradi.

Keng tarqalgan algoritmik yondashuvlar

Monotonic stack

Monotonic stack elementlari o‘suvchi yoki kamayuvchi tartib saqlaydigan stack. Yangi element kelganda tartibni buzadigan top elementlar chiqariladi. U “chap/o‘ng tomondagi eng yaqin kattaroq yoki kichikroq element” kabi masalalarni samarali yechadi.

Masalan, haroratlar ro‘yxatida keyingi issiqroq kunni topish uchun stackda hali javobi topilmagan indexlar saqlanadi:

FUNCTION NEXT_GREATER(values)
    result = uzunligi values bilan teng, boshlang‘ich 0 lar
    stack = bo‘sh stack       // indexlarni saqlaydi

    FOR i = 0 DAN values.length - 1 GACHA
        WHILE stack bo‘sh emas AND values[i] > values[stack.PEEK()]
            previous_index = stack.POP()
            result[previous_index] = i

        stack.PUSH(i)

    RETURN result

Ichma-ich WHILE borligi algoritmni avtomatik O(n²) qilmaydi. Har index stackka bir marta kiradi va ko‘pi bilan bir marta chiqadi. Jami PUSH va POPlar O(n), shuning uchun vaqt O(n), xotira O(n).

Ikki stack orqali queue

Queue FIFO tartibida ishlaydi, stack esa LIFO. Ikki stack yordamida ikki marta teskari aylantirish FIFO tartibini hosil qiladi:

• yangi elementlar input stackka qo‘shiladi;
• olish kerak bo‘lganda output bo‘sh bo‘lsa, inputdagi hamma element outputga o‘tkaziladi;
• element output topidan olinadi.

Har element inputga bir marta kirib, outputga bir marta ko‘chadi va bir marta chiqadi. Ayrim DEQUEUE ko‘chirish sabab O(n) bo‘lishi mumkin, lekin ketma-ket amallar uchun amortized vaqt O(1).

Stack yordamida rekursiyani iteratsiyaga aylantirish

Rekursiv algoritm qayerga qaytish kerakligini call stackda saqlaydi. Uni iterativ qilishda zarur holat — masalan, node, bajarilish bosqichi yoki qolgan oraliq — explicit stackka yoziladi. Bu call stack overflow xavfini boshqarish imkonini beradi, lekin umumiy xotira ehtiyojini har doim yo‘q qilmaydi.

Min stack

Oddiy stackdagi minimumni topish O(n) traversal talab qiladi. Har darajadagi joriy minimumni qo‘shimcha stackda yoki har yozuv bilan saqlash orqali GET_MIN()ni O(1) qilish mumkin:

value_stack: [5, 2, 4, 1]
min_stack:   [5, 2, 2, 1]

Bu tezlik qo‘shimcha O(n) xotira va har PUSH/POPda ikkinchi holatni yangilash evaziga keladi.

Afzalliklari

• PUSH, POP va PEEK odatda O(1).
• LIFO talab qilinadigan jarayonni sodda va aniq ifodalaydi.
• Orqaga qaytish nuqtalarini tabiiy tartibda saqlaydi.
• Array yoki linked list ustiga qurilishi mumkin.
• Rekursiyani iterativ boshqarishga va ichma-ich tuzilmalarni tekshirishga yordam beradi.
• Interfeys cheklangani sababli ichki holatni boshqarish osonroq.

Bu afzallik o‘rtadagi va pastdagi elementlarga bevosita kira olmaslik evaziga keladi.

Cheklovlari

• Faqat top elementga to‘g‘ridan-to‘g‘ri kirish mumkin.
• Qiymat qidirish va to‘liq traversal O(n).
• Bo‘sh stackdan POP yoki PEEK underflow keltirib chiqaradi.
• Fixed-size implementatsiyada capacity tugashi mumkin.
• Dynamic array resize’i ayrim PUSHni O(n) qiladi.
• Linked list implementatsiyasi har element uchun reference va allocation xarajatiga ega.
• Juda katta call stack yoki rekursiv chuqurlik stack overflowga olib keladi.
• FIFO yoki ustuvorlik bo‘yicha ishlov berish talabiga mos emas.

Keng tarqalgan xatolar va edge case’lar

Bo‘sh stackdan pop qilish

Bo‘sh stackda top element yo‘q. POP yoki PEEKdan oldin IS_EMPTY tekshiriladi yoki API qaytaradigan xato holati aniq boshqariladi. Maxsus -1 qiymatini qaytarish har doim xavfsiz emas, chunki -1 stackdagi haqiqiy qiymat bo‘lishi mumkin.

Top indexni noto‘g‘ri boshqarish

top oxirgi element indeximi yoki keyingi bo‘sh indexmi — implementatsiya boshida aniqlanishi kerak. Bu ikki modelni aralashtirish off-by-one xatosi va array chegarasidan chiqishga olib keladi.

Model A: bo‘sh top = -1, oxirgi element items[top]
Model B: bo‘sh size = 0, oxirgi element items[size - 1]

Pop va peekni aralashtirish

PEEK faqat ko‘radi, POP esa olib tashlaydi. Parser yoki qavs tekshiruvda tasodifan PEEK ishlatib, elementni stackda qoldirish keyingi hisobni buzishi mumkin. Aksincha, faqat tekshirish kerak joyda POP qilish holatni yo‘qotadi.

Operandlar tartibini teskari olish

Postfix hisoblashda right = POP(), keyin left = POP() olinadi. left - right o‘rniga right - left qilish qo‘shishda sezilmasligi, lekin ayirish va bo‘lishda noto‘g‘ri natija berishi mumkin.

Qavslar uchun faqat sonni sanash

Ochuvchi va yopuvchi qavslar soni tengligi yetarli emas. ")(" da sonlar teng, ammo tartib noto‘g‘ri. "([)]" da ham turlar soni teng, lekin yopilish ichma-ichlikka mos emas. Stack eng oxirgi ochilgan qavs birinchi yopilishini tekshiradi.

Dynamic array pushini har doim qat’iy O(1) deyish

Resize bo‘lmagan PUSH O(1), resize bo‘lgan aniq amal O(n). Geometrik o‘sishdagi ketma-ket amallar uchun to‘g‘ri atama amortized O(1).

Linked listning noto‘g‘ri chetini top qilish

Singly linked list oxiridan o‘chirish oldingi node’ni topishni talab qilishi mumkin. List boshini top qilish PUSH va POPni O(1) saqlaydi.

Reference’ni tozalamaslik

Array stackdan obyekt chiqarilganda size kamayishi mantiqan yetarli bo‘lsa-da, eski katak reference saqlab qolsa, garbage collector obyektni hali reachable deb hisoblashi mumkin. Implementatsiya foydalanilmaydigan katakni tozalashi foydali.

Stack ichini tashqi kodga ochib qo‘yish

Ichki arrayga tashqi kod istalgan indexdan yozsa, LIFO invarianti va size holati buziladi. Stack interfeysi ichki saqlash usulini yashirishi kerak.

Bir elementli holat

Bitta element POP qilingach stack bo‘sh bo‘ladi. Linked listda top NULL, arrayda size 0 yoki top -1ga qaytishi kerak. Keyingi PEEK underflow bo‘lishi shart.

Qachon stack ishlatish kerak?

Stack quyidagi talablar mavjud bo‘lganda mos:

• eng yangi qo‘shilgan element birinchi qayta ishlanishi kerak;
• amal yoki holatlarni teskari tartibda qaytarish kerak;
• ichma-ich qavs, teg yoki scope’larni tekshirish kerak;
• DFS, backtracking yoki iterativ tree traversal bajariladi;
• ifoda operatorlari va operandlarini vaqtincha saqlash kerak;
• keyingi/oldingi kattaroq element kabi monotonic stack masalasi bor;
• rekursiv bajarilish holatini explicit boshqarish kerak.

Stack tanlashdan oldin LIFO tartibi muammoning haqiqiy talabimi, shuni tekshirish muhim. Faqat “elementlarni saqlash kerak” degan talab stack uchun yetarli sabab emas.

Qachon stack ishlatmaslik kerak?

Quyidagi vaziyatlarda boshqa ma’lumotlar tuzilmasi yaxshiroq:

• Birinchi kirgan element birinchi chiqishi kerak bo‘lsa, queue FIFO tartibini beradi.
• Index bo‘yicha ixtiyoriy elementga kirish kerak bo‘lsa, array yoki dynamic array mosroq.
• Kalit bo‘yicha tez qidirish kerak bo‘lsa, hash table ko‘pincha yaxshiroq.
• Eng kichik yoki eng katta ustuvor element olinishi kerak bo‘lsa, priority queue yoki heap kerak.
• Ikki tomondan qo‘shish va olish zarur bo‘lsa, deque mos keladi.
• O‘rtadagi elementlar tez-tez o‘chirilsa, node reference’lari bilan linked list yoki boshqa maxsus tuzilma ko‘rib chiqiladi.
• Juda chuqur rekursiya bo‘lsa, call stackka tayanish o‘rniga explicit stack va iterativ algoritm xavfsizroq bo‘lishi mumkin.

Stackning cheklangan interfeysi LIFO muammosida afzallik, tasodifiy kirish talabida esa to‘siqdir.

Eng muhim xulosa

Stack — elementlarni LIFO, ya’ni “oxirgi kirgan, birinchi chiqadi” tartibida boshqaradigan abstrakt ma’lumotlar turi. Uning markazida top turadi: PUSH topga qo‘shadi, POP topdan olib tashlaydi, PEEK esa topni o‘zgartirmasdan ko‘rsatadi.

Stack fixed array, dynamic array yoki linked list ustiga qurilishi mumkin. Dynamic array stack cache uchun qulay va PUSHni amortized O(1)da bajaradi; resize bo‘lgan aniq amal O(n). Linked list stackda top list boshida saqlansa, PUSH va POP O(1), ammo har node qo‘shimcha reference va allocation talab qiladi.

Stackning asosiy amallari odatda O(1), qidirish va traversal esa O(n). Bo‘sh stackdan olish underflow, sig‘imi cheklangan stackka ortiqcha qo‘shish overflowdir. Stack ADT bilan runtime call stack bir xil emas, lekin ikkalasi ham LIFO qoidasidan foydalanadi.

Stackni tanlashdan oldin uchta savol bering:

1. Eng oxirgi kelgan element birinchi ishlanishi kerakmi?
2. Faqat top bilan ishlash yetarlimi?
3. Capacity, resize yoki node xarajatlaridan qaysi biri vazifaga mos?

Stackdan keyingi tabiiy mavzu — queue. Stack eng yangi elementni birinchi chiqarsa, queue eng oldin kelgan elementni birinchi chiqaradi. Shu bitta tartib farqi undo, DFS va ifoda hisoblashga mos stackni printer navbati, so‘rovlar oqimi va BFSga mos queuedan ajratadi.