Stek (Stack) - Algoritmlar va ma'lumotlar tuzilmasi

Stek - eng sodda, lekin eng ko'p ishlatiladigan tuzilmalardan biri. Uning butun mohiyati bitta qoidada: oxirgi kirgan birinchi chiqadi.

LIFO prinsipi #

LIFO - Last In, First Out. Bu qoidani tushunish uchun idishdagi likopchalar uyumini tasavvur qiling: eng oxirida qo'yilgan likopcha eng birinchi olinadi.

Stekka faqat bir tomondan - yuqoridan kirish mumkin

Stek amallari #

Amal	Vazifasi	Murakkablik
`push(x)`	Yuqoriga element qo'shadi	O(1)
`pop()`	Yuqoridagini olib tashlaydi va qaytaradi	O(1)
`peek()`	Yuqoridagini qaytaradi, olmaydi	O(1)
`bosh_mi()`	Stek bo'shligini tekshiradi	O(1)
`__len__()`	Elementlar sonini qaytaradi	O(1)

Amalga oshirish #

Python'da list allaqachon stek sifatida ishlaydi, lekin o'z klassimizni yozamiz - shunda niyat aniq bo'ladi:

Python

class Stek:
    """LIFO prinsipida ishlaydigan stek."""

    def __init__(self):
        self._elementlar = []

    def push(self, qiymat):
        """Yuqoriga qo'shadi. O(1)."""
        self._elementlar.append(qiymat)

    def pop(self):
        """Yuqoridagini olib tashlaydi. O(1)."""
        if self.bosh_mi():
            raise IndexError("Stek bo'sh")
        return self._elementlar.pop()

    def peek(self):
        """Yuqoridagiga qaraydi, lekin olmaydi. O(1)."""
        if self.bosh_mi():
            raise IndexError("Stek bo'sh")
        return self._elementlar[-1]

    def bosh_mi(self):
        return len(self._elementlar) == 0

    def __len__(self):
        return len(self._elementlar)

    def __str__(self):
        return "pastdan yuqoriga: " + str(self._elementlar)


stek = Stek()
for harf in "ABCD":
    stek.push(harf)

print(stek)
print("Yuqoridagi:", stek.peek())
print("Olindi:", stek.pop())
print("Olindi:", stek.pop())
print(stek)

Natija

pastdan yuqoriga: ['A', 'B', 'C', 'D']
Yuqoridagi: D
Olindi: D
Olindi: C
pastdan yuqoriga: ['A', 'B']

list.pop(0) ishlatmang

Stek uchun har doim pop() (oxiridan) ishlating - u O(1). pop(0) esa O(n), chunki qolgan hamma element suriladi. Bu stekni sekin tuzilmaga aylantiradi.

Qo'llanilishi 1: qavslarni tekshirish #

Bu steksiz yechish deyarli imkonsiz bo'lgan klassik masala. Har qanday kod muharriri shu algoritmni ishlatadi.

Python

def qavslar_togrimi(matn):
    """Qavslar to'g'ri joylashganini tekshiradi."""
    juftliklar = {")": "(", "]": "[", "}": "{"}
    ochiqlar = set(juftliklar.values())
    stek = []

    for belgi in matn:
        if belgi in ochiqlar:
            stek.append(belgi)
        elif belgi in juftliklar:
            if not stek or stek.pop() != juftliklar[belgi]:
                return False

    return len(stek) == 0        # hammasi yopilgan bo'lishi kerak


sinovlar = [
    "(a + b) * [c - d]",
    "{[()]}",
    "(a + b]",
    "((a)",
    "",
]

for matn in sinovlar:
    holat = "to'g'ri" if qavslar_togrimi(matn) else "XATO"
    print(f"{matn!r:<22} -> {holat}")

Natija

'(a + b) * [c - d]'    -> to'g'ri
'{[()]}'               -> to'g'ri
'(a + b]'              -> XATO
'((a)'                 -> XATO
''                     -> to'g'ri

Nima uchun aynan stek?

Qavslar ichma-ich joylashadi: eng oxirgi ochilgan qavs eng birinchi yopilishi kerak. Bu aynan LIFO. Shuning uchun stek bu masala uchun tabiiy tanlov.

Qo'llanilishi 2: teskari polshacha yozuv #

Kalkulyatorlar ifodani (2 + 3) * 4 ko'rinishida emas, 2 3 + 4 * ko'rinishida hisoblaydi. Bu postfiks yozuv va u stek bilan juda oson hisoblanadi:

Python

def postfiksni_hisobla(ifoda):
    """Postfiks (teskari polshacha) ifodani hisoblaydi."""
    stek = []
    amallar = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: a / b,
    }

    for belgi in ifoda.split():
        if belgi in amallar:
            if len(stek) < 2:
                raise ValueError(f"'{belgi}' uchun operand yetarli emas")
            ikkinchi = stek.pop()
            birinchi = stek.pop()
            stek.append(amallar[belgi](birinchi, ikkinchi))
        else:
            stek.append(float(belgi))

    if len(stek) != 1:
        raise ValueError("Ifoda noto'g'ri")

    return stek[0]


print(postfiksni_hisobla("2 3 +"))
print(postfiksni_hisobla("2 3 + 4 *"))
print(postfiksni_hisobla("5 1 2 + 4 * + 3 -"))

Natija

5.0
20.0
14.0

Oxirgi ifoda odatiy yozuvda 5 + ((1 + 2) * 4) - 3 = 14.

Qo'llanilishi 3: orqaga qaytarish tarixi #

Matn muharrirlaridagi Ctrl + Z aynan shunday ishlaydi:

Python

class MatnMuharriri:
    """Orqaga qaytarish imkoniyati bo'lgan oddiy muharrir."""

    def __init__(self):
        self.matn = ""
        self._tarix = []

    def yoz(self, qoshimcha):
        self._tarix.append(self.matn)      # holatni saqlab qo'yamiz
        self.matn += qoshimcha

    def ochir(self, belgilar_soni):
        self._tarix.append(self.matn)
        self.matn = self.matn[:-belgilar_soni]

    def orqaga(self):
        """Ctrl+Z"""
        if not self._tarix:
            return
        self.matn = self._tarix.pop()


muharrir = MatnMuharriri()
muharrir.yoz("Salom")
muharrir.yoz(", dunyo")
muharrir.yoz("!")
print(muharrir.matn)

muharrir.orqaga()
print(muharrir.matn)
muharrir.orqaga()
print(muharrir.matn)

Natija

Salom, dunyo!
Salom, dunyo
Salom

Stek va rekursiya #

Bu eng muhim bog'liqlik. Har bir rekursiv chaqiruv chaqiruvlar stekiga qo'yiladi.

Python

def faktorial(n):
    if n <= 1:
        return 1
    return n * faktorial(n - 1)


print(faktorial(4))

Ichkarida quyidagilar sodir bo'ladi:

Natija

faktorial(4) chaqirildi   -> stekka qo'yildi, faktorial(3) ni kutmoqda
  faktorial(3) chaqirildi -> stekka qo'yildi, faktorial(2) ni kutmoqda
    faktorial(2) chaqirildi -> stekka qo'yildi, faktorial(1) ni kutmoqda
      faktorial(1) = 1      -> qaytdi, stekdan olindi
    faktorial(2) = 2 * 1    -> qaytdi, stekdan olindi
  faktorial(3) = 3 * 2      -> qaytdi, stekdan olindi
faktorial(4) = 4 * 6 = 24   -> qaytdi

RecursionError nima uchun chiqadi?

Chaqiruvlar steki cheksiz emas. Python'da uning chuqurligi sukut bo'yicha 1000 ta chaqiruv bilan cheklangan:

Python

def cheksiz(n):
    return cheksiz(n + 1)

cheksiz(1)

Natija

RecursionError: maximum recursion depth exceeded

Har bir rekursiv funksiya albatta bazaviy holatga ega bo'lishi kerak.

Har qanday rekursiyani stek yordamida sikl ko'rinishida qayta yozish mumkin:

Python

def faktorial_stek_bilan(n):
    """Rekursiyasiz, o'z stekimiz bilan."""
    stek = []
    while n > 1:
        stek.append(n)
        n -= 1

    natija = 1
    while stek:
        natija *= stek.pop()
    return natija


print(faktorial_stek_bilan(5))

Natija

Bog'langan ro'yxat asosidagi stek #

Massiv o'rniga bog'langan ro'yxat ham ishlatilishi mumkin - bunda hajmni oshirish uchun ko'chirish kerak bo'lmaydi:

Python

class TugunliStek:
    """Bog'langan tugunlar asosidagi stek - barcha amallar aniq O(1)."""

    class _Tugun:
        __slots__ = ("qiymat", "keyingi")

        def __init__(self, qiymat, keyingi):
            self.qiymat = qiymat
            self.keyingi = keyingi

    def __init__(self):
        self._yuqori = None
        self._soni = 0

    def push(self, qiymat):
        self._yuqori = self._Tugun(qiymat, self._yuqori)
        self._soni += 1

    def pop(self):
        if self._yuqori is None:
            raise IndexError("Stek bo'sh")
        qiymat = self._yuqori.qiymat
        self._yuqori = self._yuqori.keyingi
        self._soni -= 1
        return qiymat

    def __len__(self):
        return self._soni


stek = TugunliStek()
for son in [10, 20, 30]:
    stek.push(son)
print(stek.pop(), stek.pop(), len(stek))

Natija

30 20 1

Qaysi biri yaxshiroq?

Massiv asosidagi stek amalda tezroq (kesh tufayli) va Python'da list allaqachon optimallashtirilgan. Bog'langan variant esa har bir push uchun aniq O(1) kafolatlaydi - ko'chirish hech qachon bo'lmaydi. Real vaqt tizimlarida shu kafolat muhim bo'lishi mumkin.

Stek qayerda ishlatiladi? #

Soha	Qo'llanilishi
Kompilyatorlar	Sintaksisni tahlil qilish, qavslarni tekshirish
Brauzerlar	"Orqaga" tugmasi tarixi
Muharrirlar	Ctrl+Z / Ctrl+Y
Operatsion tizim	Funksiya chaqiruvlari steki
Algoritmlar	DFS (chuqurlik bo'yicha qidiruv)
Kalkulyatorlar	Postfiks ifodalarni hisoblash

Amaliy topshiriq

Stek klassidan foydalanib matnni teskari o'giradigan funksiya yozing.
min_qiymat() metodi bo'lgan stek yarating - u har doim O(1) da eng kichik elementni qaytarsin (maslahat: ikkinchi yordamchi stekdan foydalaning).
Postfiks kalkulyatorini ** (daraja) amali bilan to'ldiring.
Odatiy (infiks) ifodani postfiksga o'giradigan algoritmni yozing - bu Shunting-yard algoritmi.

Xulosa #

Stek LIFO prinsipida ishlaydi: oxirgi kirgan birinchi chiqadi.
push, pop, peek - barchasi O(1).
Python'da list.append() va list.pop() tayyor stek beradi; pop(0) dan qoching.
Stek qavslarni tekshirish, ifodalarni hisoblash va orqaga qaytarish tarixi uchun tabiiy tanlov.
Har bir rekursiv chaqiruv chaqiruvlar stekiga tushadi - shundan RecursionError kelib chiqadi.

Keyingi bo'limda stekning teskarisi - navbat bilan tanishamiz.

LIFO prinsipi #

Stek amallari #

Amalga oshirish #

Qo'llanilishi 1: qavslarni tekshirish #

Qo'llanilishi 2: teskari polshacha yozuv #

Qo'llanilishi 3: orqaga qaytarish tarixi #

Stek va rekursiya #

Bog'langan ro'yxat asosidagi stek #

Stek qayerda ishlatiladi? #

Xulosa #

Xatolik topdingizmi?