Ma’lumotlar tuzilmasi va algoritmlar” fanidan 7- laboratoriya ishini bajarishga namuna

Stek bilan bog'liq quyidagi funksiyalar mavjud:

• 
  empty() - stek bo'sh yoki yo'qligini qaytaradi - Vaqt murakkabligi: O(1)
  
• 
  size() – stek hajmini qaytaradi – Vaqt murakkabligi: O(1)
  
• 
  top() – stekning eng yuqori elementiga havolani qaytaradi – Vaqt murakkabligi: O(1)
  
• 
  push(a) – “a” elementini stekning yuqori qismiga kiritadi – Vaqt murakkabligi: O(1)
  
• 
  pop() - stekning eng yuqori elementini o'chiradi - Vaqt murakkabligi: O (1)
  

Pythonda stekni amalga oshirishning turli usullari mavjud. Python kutubxonasidagi ma'lumotlar tuzilmalari va modullaridan foydalangan holda stekni amalga oshirishimiz mumkin.
Pythonda stek quyidagi usullar yordamida amalga oshirilishi mumkin: 

• 
  Ro'yxat orqali ifodalash;
  
• 
  Collections.deque
  
• 
  Navbat.LifoQueue
  

Stekni ro'yxat yordamida amalga oshirish. Pythonning o'rnatilgan ma'lumotlar strukturasi ro'yxati stek sifatida ishlatilishi mumkin. Push() o'rniga append() metodi orqali stekning yuqori qismiga elementlar qo'shish mumkin, pop() esa elementni LIFO tartibida olib tashlaydi. 

Afsuski, ro'yxatda bir nechta kamchiliklar mavjud. Eng katta muammo shundaki, u o'sib borishi bilan tezlik bilan bog'liq muammolarga duch kelishi mumkin. Ro'yxatdagi elementlar xotirada bir-birining yonida saqlanadi, agar stek hozirda mavjud bo'lgan xotira blokidan kattaroq bo'lsa, Python xotirani ba'zida taqsimlashi kerak bo’ladi. Bu ba'zi append() chaqiruvlarining boshqalariga qaraganda ancha uzoq davom etishiga olib kelishi mumkin.

stack = [] stack.append('a') stack.append('b') stack.append('c') print("Dastlabki stek:") print(stack) print("Quyidagi elementlar stekdan olib tashlandi:") print(stack.pop()) print(stack.pop()) print(stack.pop()) print("Elementlar olingandan keyingi stek:") print(stack)

Output: 

Dastlabki stek:

['a', 'b', 'c']

Quyidagi elementlar stekdan olib tashlandi:

c

b

a

Elementlar olingandan keyingi stek:

[]

Stekni collections.deque yordamida amalga oshirish. Python stekini collections.deque yordamida amalga oshirish mumkin. Konteynerning ikkala uchidan ham tezroq qo'shish va pop operatsiyalarini bajarish zarur bo'lgan hollarda ro'yxatga nisbatan deque afzalroqdir, chunki deque O(n) bilan ta'minlaydigan ro'yxatga nisbatan qo'shish va pop operatsiyalari uchun O(1) vaqt murakkabligini ta'minlaydi.

Ro'yxatda ko'rsatilganidek, deque bo'yicha bir xil usullar qo'llaniladi, append() va pop().

from collections import deque stack = deque() stack.append('abbos') stack.append('botir') stack.append('salim') print("Dastlabki stek:") print(stack) print("Quyidagi elementlar stekdan olib tashlandi:") print(stack.pop()) print(stack.pop()) print(stack.pop()) print("Elementlar olingandan keyingi stek:") print(stack)

Output: 

Dastlabki stek:

deque(['abbos', 'botir', 'salim'])

Quyidagi elementlar stekdan olib tashlandi:

salim

botir

abbos

Elementlar olingandan keyingi stek:

deque([])

Stekni queue (navbat) yordamida amalga oshirish. Navbat modulida LIFO navbati ham mavjud, bu asosan stek prinspiga asoslanadi. Ma’lumotlar “put()” funksiyasi yordamida “queue” ga kiritiladi va get() “queue”dan ma’lumotlarni chiqaradi. 

Ushbu modulda turli xil funksiyalar mavjud: 

•