Stack

Stek (Stack) — bu LIFO (Last In First Out — oxirgi kirgan birinchi chiqadi) tamoyiliga qat'iy amal qiluvchi chiziqli ma'lumotlar tuzilmasidir. Bu shuni anglatadiki, stekka eng oxirgi kiritilgan element undan eng birinchi bo'lib chiqariladi.

Stekni ustma-ust terilgan likopchalar taxlami (pile of plates) kabi tasavvur qilish mumkin:

Bu yerda siz:

• Eng tepaga yangi likopcha qo'yishingiz mumkin.
• Eng tepada turgan likopchani olishingiz mumkin.
• Agar sizga eng tagidagi likopcha kerak bo'lsa, avval uning ustidagi barcha likopchalarni birma-bir olib tashlashingiz shart. Stek ma'lumotlar tuzilmasi aynan shu tarzda ishlaydi.

Stekning LIFO prinsipi

Dasturlash terminologiyasida:

• Stekning eng yuqorisiga yangi element qo'shish amali Push deb ataladi.
• Stekning eng yuqorisidan elementni olib tashlash amali Pop deb ataladi.

Yuqoridagi rasmda 3-element eng oxirida qo'yilgan bo'lsa-da, u eng birinchi bo'lib olib tashlandi. Bu LIFO prinsipining yaqqol amaliy ko'rinishidir.

Biz stekni Go, Python, Java, C, C++ kabi istalgan dasturlash tilida yaratishimiz mumkin, ammo ularning ishlash mantig'i va spetsifikatsiyasi mutlaqo bir xil bo'lib qoladi.

Stekning asosiy operatsiyalari

Stek ustida amallar bajarish uchun quyidagi asosiy funksiyalardan foydalaniladi:

• Push: Stekning eng yuqori qismiga yangi element qo'shish.
• Pop: Stekning eng yuqori qismidagi elementni o'chirish va uning qiymatini qaytarish.
• IsEmpty: Stek bo'sh yoki bo'sh emasligini tekshirish.
• IsFull: Stek to'lganligini tekshirish (statik massiv asosida cheklangan hajm berilganda).
• Peek (Top): Eng yuqoridagi elementni o'chirmasdan, faqat uning qiymatini o'qish.

Stek ma'lumotlar tuzilmasining ishlash mexanizmi

Operatsiyalar quyidagi tartibda bajariladi:

1. Stekdagi eng yuqori element manzilini saqlash uchun TOP nomli ko'rsatkich (indeks) ishlatiladi.
2. Stek yaratilganda, uning bo'sh ekanligini bildirish uchun TOP = -1 qilib boshlanadi.
3. Yangi element qo'shishda (Push): avval TOP indeksi 1 ga oshiriladi (TOP = TOP + 1), so'ngra yangi element TOP ko'rsatayotgan joyga yoziladi.
4. Elementni olishda (Pop): TOP ko'rsatkichidagi element qiymati qaytariladi va TOP indeksi 1 ga kamaytiriladi (TOP = TOP - 1).
5. Yangi element qo'shishdan oldin stek to'lib qolmaganligi (IsFull) tekshiriladi (agar to'lgan bo'lsa, bu Stack Overflow deyiladi).
6. Elementni o'chirishdan oldin stek bo'sh emasligi (IsEmpty) tekshiriladi (agar bo'sh bo'lsa, bu Stack Underflow deyiladi).

Stekning turli tillardagi to'liq dastur kodi

Stekni amalga oshirishning eng keng tarqalgan usuli massivlardan (yoki dinamik massiv / slice) foydalanishdir. Quyida birinchi o'rinda Go, so'ngra Python, Java, C va C++ tillaridagi to'liq yechim keltirilgan:

package main

import (
    "errors"
    "fmt"
)

// Stack strukturasi
type Stack struct {
    items []int
}

// Push - element qo'shish
func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
    fmt.Printf("Qo'shildi: %d\n", item)
}

// IsEmpty - stek bo'shligini tekshirish
func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

// Pop - eng yuqoridagi elementni o'chirish va qaytarish
func (s *Stack) Pop() (int, error) {
    if s.IsEmpty() {
        return 0, errors.New("stek bo'sh (Stack Underflow)")
    }
    topIndex := len(s.items) - 1
    poppedItem := s.items[topIndex]
    s.items = s.items[:topIndex]
    return poppedItem, nil
}

// Peek - eng yuqoridagi element qiymatini ko'rish
func (s *Stack) Peek() (int, error) {
    if s.IsEmpty() {
        return 0, errors.New("stek bo'sh")
    }
    return s.items[len(s.items)-1], nil
}

// PrintStack - stek holatini chop etish
func (s *Stack) PrintStack() {
    fmt.Println("Stek:", s.items)
}

func main() {
    stack := &Stack{}

    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    stack.Push(4)

    stack.PrintStack()

    popped, err := stack.Pop()
    if err == nil {
        fmt.Printf("Olib tashlangan element: %d\n", popped)
    }

    fmt.Println("Element olib tashlangandan so'ng:")
    stack.PrintStack()
}

Stekning vaqt murakkabligi

Massivga asoslangan stekda barcha asosiy amallar:

• push(): O(1) — doimiy vaqt
• pop(): O(1) — doimiy vaqt
• isEmpty(): O(1) — doimiy vaqt
• isFull(): O(1) — doimiy vaqt
• peek(): O(1) — doimiy vaqt

Chunki bu amallarda qidiruv talab etilmaydi, faqatgina TOP indeksi orqali to'g'ridan-to'g'ri elementga murojaat qilinadi.

Stek ma'lumotlar tuzilmasining qo'llanilishi

Garchi stekni amalga oshirish juda sodda bo'lsa-da, u kompyuter tizimlarida juda qudratli vositadir:

1. So'zni teskarisiga aylantirish (Reversing a word): Barcha harflarni stekka push qilib, so'ngra birma-bir pop qilinsa, LIFO prinsipi sababli so'z teskari tartibda chiqadi.
2. Kompilyatorlarda (Compilers): Kompilyatorlar arifmetik ifodalarni (masalan, 2 + 4 / 5 * (7 - 9)) hisoblashda qavslarning to'g'ri ochilib-yopilishini tekshirish (Parentheses Balancing) hamda ularni prefiks/postfiks shakllarga o'tkazishda stekdan foydalanadi.
3. Veb-brauzerlarda (Browsers): Brauzerdagi "Orqaga" (Back) tugmasi siz kirgan sahifalar manzillarini (URL) stekda saqlaydi. Har bir yangi sahifaga o'tganingizda URL stekka qo'shiladi. "Orqaga" tugmasi bosilganda joriy manzil o'chiriladi va eng oxirgi ko'rilgan sahifa ochiladi.
4. Matn muharrirlarida (Text Editors): Ctrl + Z (Undo / Bekor qilish) buyrug'i oxirgi qilingan amallarni stekda saqlash hisobiga ishlaydi.

package main

import "fmt"

func main() {
	// Go tilida slice yordamida Stek (Stack) yaratish
	var stack []string

	// Push amallari
	stack = append(stack, "Google")
	stack = append(stack, "YouTube")
	stack = append(stack, "GoDasturchi.uz")

	fmt.Println("Brauzer tarixi (Stek):", stack)

	// Pop amali (Back tugmasi)
	topIndex := len(stack) - 1
	current := stack[topIndex]
	stack = stack[:topIndex]

	fmt.Printf("Orqaga qaytildi: %s dan chiqdik\n", current)
	fmt.Println("Hozirgi sahifa:", stack[len(stack)-1])
	fmt.Println("Qolgan tarix:", stack)
}