DSA steklar

Steklar

Stek — ko‘plab elementlarni saqlay oladigan ma’lumotlar tuzilmasi.

Stekni bir taxlam quymoq deb tasavvur qiling.

Bir taxlam quymoqda quymoqlar ham tepadan qo‘shiladi, ham tepadan olinadi. Shuning uchun quymoq olganingizda u har doim siz eng oxirida qo‘shgan quymoq bo‘ladi. Elementlarni bunday tartibda tashkil etish LIFO deb ataladi: Last In First Out (oxirgi kirgan birinchi chiqadi).

Stek ustida bajarishimiz mumkin bo‘lgan asosiy amallar:

• Push: Stekka yangi element qo‘shadi.
• Pop: Stekning eng yuqorisidagi elementni olib tashlaydi va qaytaradi.
• Peek: Stekning eng yuqorisidagi elementni qaytaradi.
• isEmpty: Stek bo‘sh yoki bo‘sh emasligini tekshiradi.
• Size: Stekdagi elementlar sonini aniqlaydi.

Yuqoridagi stek animatsiyasida ushbu asosiy amallarni sinab ko‘ring.

Steklarni massivlar yoki bog‘langan ro‘yxatlar yordamida amalga oshirish mumkin.

Steklardan bekor qilish (undo) mexanizmlarini amalga oshirishda, oldingi holatlarga qaytishda, graflarda chuqurlik bo‘yicha qidiruv algoritmlarini yaratishda yoki orqaga qaytish (backtracking) uchun foydalanish mumkin.

Steklar ko‘pincha navbatlar bilan birga tilga olinadi. Navbat — keyingi sahifada tasvirlangan o‘xshash ma’lumotlar tuzilmasi.

Stekni massivlar yordamida amalga oshirish

Steklarni amalga oshirishda massivlar yoki bog‘langan ro‘yxatlardan foydalanishning afzalliklarini yaxshiroq tushunish uchun massivlar va bog‘langan ro‘yxatlar xotirada qanday saqlanishini tushuntiruvchi ushbu sahifani ko‘rib chiqing.

Massivdan stek sifatida foydalanganimizda u quyidagicha ko‘rinadi:

Steklarni massivlar yordamida amalga oshirish sabablari:

• Xotirani tejaydi: Massiv elementlari bog‘langan ro‘yxat tugunlari kabi keyingi elementning manzilini saqlamaydi.
• Amalga oshirish va tushunish osonroq: Steklarni massivlar yordamida amalga oshirish bog‘langan ro‘yxatlardan foydalanishga qaraganda kamroq kod talab qiladi va shu sababli odatda tushunish ham osonroq.

Steklarni amalga oshirishda massivlardan foydalanmaslik sababi:

• Qat’iy o‘lcham: Massiv xotiraning belgilangan qismini egallaydi. Bu shuni anglatadiki, u keragidan ko‘proq xotira egallashi mumkin yoki massiv to‘lib qolsa, unga boshqa element sig‘maydi.

Python ro‘yxatlari steklarni amalga oshirish uchun kerakli funksionallikni yaxshi qo‘llab-quvvatlagani sababli, stek yaratish va stek amallarini bajarishni atigi bir necha qator kod bilan boshlaymiz:

stack = []

# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)

# Pop
element = stack.pop()
print("Pop: ", element)

# Peek
topElement = stack[-1]
print("Peek: ", topElement)

# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)

# Size
print("Size: ",len(stack))

Biroq steklar uchun asosiy amallarga ega ma’lumotlar tuzilmasini aniq yaratish uchun buning o‘rniga stek sinfini (class) yaratishimiz kerak. Python’da steklarni bu tarzda yaratish C va Java kabi boshqa dasturlash tillarida steklar yaratilishiga ham ko‘proq o‘xshaydi.

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack.pop()
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack[-1]
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

# Create a stack
myStack = Stack()

myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Stack: ", myStack.stack)

print("Pop: ", myStack.pop())

print("Peek: ", myStack.peek())

print("isEmpty: ", myStack.isEmpty())

print("Size: ", myStack.size())

Stekni bog‘langan ro‘yxatlar yordamida amalga oshirish

Steklarni bog‘langan ro‘yxatlar yordamida amalga oshirish sababi:

• Dinamik o‘lcham: Massivlardan farqli ravishda, stek dinamik ravishda kattalashishi va kichrayishi mumkin.

Steklarni amalga oshirishda bog‘langan ro‘yxatlardan foydalanmaslik sabablari:

• Qo‘shimcha xotira: Har bir stek elementi keyingi elementning (bog‘langan ro‘yxatdagi keyingi tugunning) manzilini saqlashi kerak.
• O‘qilishi: Kod uzunroq va murakkabroq bo‘lgani uchun ba’zilarga uni o‘qish va yozish qiyinroq bo‘lishi mumkin.

Stekni bog‘langan ro‘yxat yordamida quyidagicha amalga oshirish mumkin.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, value):
        new_node = Node(value)
        if self.head:
            new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        popped_node = self.head
        self.head = self.head.next
        self.size -= 1
        return popped_node.value
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.head.value
    
    def isEmpty(self):
        return self.size == 0
    
    def stackSize(self):
        return self.size

myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')

print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Quyidagi rasm "Stek" ma’lumotlar tuzilmasini ifodalaydi.

Yuqoridagi stekda peek() metodi ishga tushirilsa, nima qaytariladi?

Javobni yuborish »

Mashqni boshlash