Steklar
Stack - bu oxirgi kelgan birinchi chiqish (LIFO) tamoyiliga amal qiluvchi chiziqli ma’lumotlar strukturasi.
Buni pancakes to‘plami kabi tasavvur qiling - siz faqat yuqoridan krep qo‘shishingiz yoki olib tashlashingiz mumkin.
Staklar
Stack - bu ko‘plab elementlarni o‘z ichiga oladigan ma’lumotlar strukturasi va oxirgi qo‘shilgan element birinchi bo‘lib o‘chiriladi.
Bir qoziq pancakes kabi, pancakes ham qo‘shiladi, ham yuqoridan chiqariladi. Shunday qilib, krepni olib tashlaganingizda, u har doim siz qo‘shgan oxirgi krep bo‘ladi. Elementlarni tartibga solishning bunday usuli LIFO: Last In First Out deb ataladi.
Biz stekda bajarishimiz mumkin bo‘lgan asosiy operatsiyalar:
- Push: stekga yangi element qo‘shadi.
- Pop: stekdan yuqori elementni olib tashlaydi va qaytaradi.
- Peek: stekdagi yuqori (oxirgi) elementni qaytaradi.
- isEmpty: stek bo‘sh yoki yo‘qligini tekshiradi.
- Hajmi: stekdagi elementlar sonini topadi.
Stacks massivlar yoki bog‘langan listlar yordamida amalga oshirilishi mumkin.
Steklardan bekor qilish mexanizmlarini amalga oshirish, oldingi holatga qaytish, grafiklarda chuqurlikdan birinchi bo‘lib qidirish algoritmlarini yaratish yoki orqaga qaytish uchun foydalanish mumkin.
Stacks ko‘pincha navbatdagi sahifada tasvirlangan o‘xshash ma’lumotlar tuzilmasi bo‘lgan Queues bilan birga eslatib o‘tiladi.
Python ro‘yxatlari yordamida stekni amalga oshirish
Python ro‘yxatlari (va massivlar) uchun stek quyidagicha ko‘rinishi va harakat qilishi mumkin:
Add: Remove:Python ro‘yxatlari steklarni amalga oshirish uchun zarur bo‘lgan funksionallikni yaxshi qo‘llab-quvvatlaganligi sababli, biz stek yaratishdan boshlaymiz va shu kabi bir nechta stringlar bilan stek operatsiyalarini bajaramiz:
Misol
Python ro‘yxatini stek sifatida ishlatish:
stack = []
# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)
# Peek
topElement = stack[-1]
print("Peek: ", topElement)
# Pop
poppedElement = stack.pop()
print("Pop: ", poppedElement)
# Stack after Pop
print("Stack after Pop: ", stack)
# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)
# Size
print("Size: ",len(stack))
O‘zingiz sinab ko‘ring »
Python ro‘yxatlari stek sifatida ishlatilishi mumkin bo‘lsa-da, maxsus Stack sinfini yaratish yaxshiroq inkapsulyatsiya va qo‘shimcha funksiyalarni ta’minlaydi:
Misol
Klass yordamida stek yaratish:
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("Stack after Pop: ", myStack.stack)
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.size())
Misolni ishga tushirish »
Listlar/massivlar yordamida steklarni amalga oshirish sabablari:
- Xotira samaradorligi: massiv elementlari bog‘langan list tugunlari kabi keyingi elementlar manzilini saqlamaydi.
- Amalga oshirish va tushunish osonroq: steklarni amalga oshirish uchun massivlardan foydalanish bog‘langan listlarni ishlatishdan ko‘ra kamroq kod talab qiladi va shuning uchun uni tushunish ham osonroq.
Staklarni amalga oshirish uchun massivlardan foydalanmaslikning sababi:
- Ruxsat etilgan o‘lcham: massiv xotiraning belgilangan qismini egallaydi. Bu shuni anglatadiki, u kerak bo‘lgandan ko‘proq xotirani egallashi mumkin yoki massiv to‘ldirilsa, u ko‘proq elementlarni sig‘dira olmaydi.
Bog‘langan listlar yordamida stekni amalga oshirish
Bog‘langan list qandaydir ma’lumotlarga ega bo‘lgan tugunlardan va keyingi tugunga ko‘rsatgichdan iborat.
Bog‘langan ro‘yxatlardan foydalanishning katta foydasi shundaki, tugunlar xotirada bo‘sh joy bo‘lgan joyda saqlanadi, elementlar massivlarda saqlangan kabi tugunlarni bir-biridan keyin bir-biriga yaqin joyda saqlash shart emas. Bog‘langan listlarning yana bir yaxshi tomoni shundaki, tugunlarni qo‘shish yoki o‘chirishda ro‘yxatdagi qolgan tugunlarni siljitish shart emas.
Steklarni amalga oshirish uchun massivlar yoki bog‘langan ro‘yxatlardan foydalanishning afzalliklarini yaxshiroq tushunish uchun massivlar va bog‘langan listlar xotirada qanday saqlanishini tushuntiruvchi ushbu sahifani ko‘rib chiqishingiz kerak.
Bog‘langan list yordamida stekni shunday amalga oshirish mumkin.
Misol
Bog‘langan ro‘yxat yordamida stek yaratish:
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
def traverseAndPrint(self):
currentNode = self.head
while currentNode:
print(currentNode.value, end=" -> ")
currentNode = currentNode.next
print()
myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')
print("LinkedList: ", end="")
myStack.traverseAndPrint()
print("Peek: ", myStack.peek())
print("Pop: ", myStack.pop())
print("LinkedList after Pop: ", end="")
myStack.traverseAndPrint()
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())
Misolni ishga tushirish »
Staklarni amalga oshirish uchun bog‘langan ro‘yxatlardan foydalanishning sababi:
- Dinamik o‘lcham: stek massivlardan farqli o‘laroq, dinamik ravishda o‘sishi va qisqarishi mumkin.
Stacklarni amalga oshirish uchun bog‘langan ro‘yxatlardan foydalanmaslik sabablari:
- Qo‘shimcha xotira: Har bir stek elementi keyingi elementga (keyingi bog‘langan list tuguniga) manzilni o‘z ichiga olishi kerak.
- O‘qilishi: Ba’zilar uchun kodni o‘qish va yozish qiyinroq bo‘lishi mumkin, chunki u uzoqroq va murakkabroq.
Umumiy stack ilovalari
Stacks ko‘plab real stsenariylarda qo‘llaniladi:
- Matn muharrirlarida bekor qilish/qayta bajarish amallari
- Brauzer tarixi (orqaga/oldinga)
- Dasturlashda funksiya chaqiruvi stegi
- Ifodani baholash
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!