Stack

Stack — ma’lumotlarni oxirgi kirgan element birinchi chiqadi tamoyili asosida saqlaydigan tuzilma. Bu tamoyil inglizcha LIFO — Last In, First Out deb ataladi.

Stack kundalik hayotdagi ustma-ust taxlangan kitoblarga o‘xshaydi: eng oxirida qo‘yilgan kitobni olish eng oson. Dasturlashda ham elementlar faqat stackning yuqori qismi orqali qo‘shiladi va olinadi.

Stack ikki ma’noda uchraydi:

• ma’lumotlar tuzilmasi sifatida;
• process xotirasidagi call stack sifatida.

Bu ikki tushuncha bir tamoyilga tayanadi, ammo vazifasi boshqa.

Asosiy amallar

Stack odatda quyidagi amallarni qo‘llaydi:

• push — yangi elementni yuqoriga qo‘shish;
• pop — yuqoridagi elementni olib tashlash va qaytarish;
• peek yoki top — yuqoridagi elementni o‘chirmasdan ko‘rish;
• isEmpty — stack bo‘sh yoki bo‘sh emasligini tekshirish;
• size — elementlar sonini olish.

Misol:

push(10)
push(20)
push(30)

Stack: [10, 20, 30]

pop() → 30
Stack: [10, 20]

30 oxirgi qo‘shilgan element bo‘lgani uchun birinchi olinadi.

Stack implementatsiyasi

Stack ikki keng tarqalgan usulda yaratiladi:

Array asosida

Elementlar massiv ichida ketma-ket saqlanadi.

Afzalliklari:

• xotirada ixcham joylashadi;
• cache uchun qulay;
• push va pop tez;
• implementatsiyasi sodda.

Kamchiligi:

• fixed-size massivda sig‘im oldindan belgilanadi;
• dynamic array kattalashganda qayta allocation bo‘lishi mumkin.

Linked list asosida

Har element keyingi elementga pointer saqlaydi.

Afzalliklari:

• hajm dinamik;
• massivni qayta ko‘chirish talab qilinmaydi.

Kamchiligi:

• har node uchun qo‘shimcha pointer;
• xotira tarqoq joylashadi;
• cache samaradorligi pastroq.

Vaqt murakkabligi

To‘g‘ri implementatsiyada:

Amal	Murakkablik
Push	O(1)
Pop	O(1)
Peek	O(1)
Qidirish	O(n)

Stackning asosiy kuchi uning yuqori qismi bilan ishlash tezligidadir. Ixtiyoriy o‘rtadagi elementni topish uchun ketma-ket ko‘rish talab qilinadi.

Call stack

Process ichidagi har thread o‘z call stackiga ega.

Funksiya chaqirilganda stackda stack frame yaratiladi. Stack frame quyidagilarni saqlashi mumkin:

• qaytish manzili;
• funksiya argumentlari;
• lokal o‘zgaruvchilar;
• saqlangan registerlar;
• oldingi stack frame bilan bog‘lanish;
• exception yoki debugging ma’lumoti.

Misol:

main()
└── calculate()
    └── sum()

sum() tugaganda uning frame’i stackdan olinadi va bajarilish calculate() funksiyasiga qaytadi.

Stack pointer

Protsessor yoki runtime call stackning yuqori qismini maxsus register orqali kuzatadi. Bu register odatda stack pointer deb ataladi.

Funksiya kirishida stack pointer yangi frame uchun o‘zgartiriladi. Funksiya tugaganda oldingi holat tiklanadi.

Arxitektura bo‘yicha stack:

• yuqori manzildan pastga;
• yoki past manzildan yuqoriga

o‘sishi mumkin. x86 oilasida odatda past manzillar tomon o‘sadi.

Stack frame va recursion

Recursive funksiya o‘zini qayta chaqirganda har chaqiriq uchun yangi frame yaratiladi.

Misol:

factorial(4)
factorial(3)
factorial(2)
factorial(1)

Har bosqich argument va qaytish manzilini saqlaydi.

Recursion chuqurligi juda katta bo‘lsa, stack limiti tugaydi va stack overflow yuz beradi.

Stack overflow

Stack overflow quyidagi sabablar bilan kelib chiqadi:

• cheksiz recursion;
• juda chuqur recursion;
• stackda katta array yaratish;
• thread stack hajmi juda kichik;
• noto‘g‘ri function call zanjiri.

Natija:

• segmentation fault;
• runtime exception;
• process tugashi;
• guard page fault.

Katta ma’lumot stack o‘rniga heapda saqlanishi mumkin.

Stack underflow

Bo‘sh stackdan pop qilishga urinish stack underflow deb ataladi.

Implementatsiya:

• exception qaytarishi;
• maxsus qiymat berishi;
• xato kodi qaytarishi

mumkin.

Underflowni oldini olish uchun isEmpty yoki size tekshiriladi.

Expression evaluation

Stack arifmetik ifodalarni qayta ishlashda ishlatiladi.

Masalan, postfix yozuv:

2 3 + 4 *

Jarayon:

1. 2 stackga qo‘shiladi.
2. 3 stackga qo‘shiladi.
3. + ikki qiymatni oladi va 5ni qo‘shadi.
4. 4 stackga qo‘shiladi.
5. * 5 va 4ni olib, 20ni qo‘shadi.

Natija — 20.

Compiler va calculatorlar expression parsingda stackdan foydalanadi.

Parenthesis tekshirish

Qavslarning to‘g‘ri ochilib-yopilishini stack bilan tekshirish mumkin.

({[]})

Ochiluvchi qavs stackga qo‘shiladi. Yopiluvchi qavs kelganda yuqoridagi qavs bilan mosligi tekshiriladi.

Stack bo‘sh qolsa va barcha juftliklar mos bo‘lsa, ifoda to‘g‘ri.

Undo va redo

Matn muharriri bajarilgan amallarni stackda saqlashi mumkin.

• Undo stack — oxirgi amalni orqaga qaytaradi.
• Redo stack — qaytarilgan amalni qayta bajaradi.

Yangi amal bajarilganda redo stack odatda tozalanadi.

Browser history

Brauzerning back va forward navigatsiyasi ikki stack modeli bilan tushuntiriladi.

• Back stack — oldingi sahifalar.
• Forward stack — orqaga qaytgandan keyingi sahifalar.

Bu model amaliy implementatsiyada boshqa strukturalar bilan birga ishlashi mumkin.

Depth-first search

Graf yoki daraxtni Depth-First Search usulida yurishda stack ishlatiladi.

Recursive DFS call stackka tayanadi. Iterative DFS esa explicit stack ishlatadi.

Explicit stack recursion limitini nazorat qilish va katta graflarda xavfsiz ishlash imkonini beradi.

Stack va queue farqi

Jihat	Stack	Queue
Tamoyil	LIFO	FIFO
Qo‘shish	Yuqoriga	Oxiriga
Olish	Yuqoridan	Boshidan
Misol	Undo, call stack	Job queue, printer queue

Stack oxirgi elementni, queue esa birinchi elementni ustun qo‘yadi.

Xavfsizlik

Call stackdagi xotira xatolari xavfsizlik zaifligiga aylanishi mumkin.

Masalan, stack buffer overflow qaytish manzilini buzishi mumkin.

Himoya usullari:

• stack canary;
• ASLR;
• NX bit;
• bounds checking;
• memory-safe tillar;
• control-flow protection;
• compiler hardening.

Diagnostika

Stack muammosida quyidagilar tekshiriladi:

• recursion chuqurligi;
• thread stack hajmi;
• stack trace;
• katta lokal o‘zgaruvchilar;
• buffer chegarasi;
• function call zanjiri;
• exception;
• core dump;
• sanitizer.

Stack trace dastur qaysi funksiyalar orqali xatoga kelganini ko‘rsatadi.

Bog‘liq tushunchalar

LIFO, Push, Pop, Call stack, Stack frame, Stack pointer, Recursion, Stack overflow, Queue, Heap