Kompyuter injiniringi” fakulteti “axborot texnologiyalari” kafedrasi

Fan o‘qituvchisi: kat.o‘q. Kudratov R.B.

Bajardi:20-06-guruh talabasi Ibroximov Abdulhay

S a m a r q a n d _ 2021

7.1. Stack konteyneri. Stek usulda amallar. Steklarni massiv va ro‘yxatlar yordamida ishlov berish

Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar dasturlashda yarimstatik ma’lumotlar tuzilmalari stek, navbat va dek tuzilmalariga oid dasturlar tuzishni o'zlashtirishlari kerak.

Nazariy qism

Stek - bu elementlarni “birinchi kirgan, oxiri chiqadi (LIFO)” tarzida saqlaydigan chiziqli ma'lumotlar strukturasi. Stekning bir uchiga yangi element qo'shiladi va element faqat shu uchidan olib tashlanadi. Qo'shish va o'chirish operatsiyalari ko'pincha push va pop deb ataladi.

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 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. 

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.

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: 

• 
  maxsize - navbatda ruxsat etilgan elementlar soni.
  
•