Stek va navbat

Ma’lumotlar tuzilmasi — ma’lumotlarni saqlash va ular ustida amallar bajarish usuli. Eng sodda tuzilmalardan biri — stek: u “oxirgi kirgan — birinchi chiqadi” (LIFO, Last In — First Out) tamoyilida ishlaydi. Uni bir-birining ustiga qo‘yilgan likopchalar bilan solishtirish mumkin: yangi likopchani tepaga qo‘yasiz va faqat tepadagisini olasiz. Asosiy amallar: push — tepaga qo‘shish, pop — tepadagini olib tashlash, peek — olmasdan ko‘rish.

Navbat “birinchi kirgan — birinchi chiqadi” (FIFO, First In — First Out) tamoyilida ishlaydi, xuddi do‘kondagi navbat kabi: yangi odam oxiriga turadi, xizmat esa boshidagidan boshlanadi. Asosiy amallar: enqueue — oxiriga qo‘shish, dequeue — boshidagini olish.

Python’da stekni oddiy ro‘yxat bilan yasash mumkin: s.append(x) elementni tepaga qo‘shadi, s.pop() esa tepadagisini qaytarib, olib tashlaydi. Navbat uchun collections modulidagi deque qulay: q.append(x) oxiriga qo‘shadi, q.popleft() esa boshidagisini oladi. Navbat uchun oddiy ro‘yxatdagi a.pop(0) dan foydalanmagan ma’qul, chunki u qolgan barcha elementlarni suradi va katta ro‘yxatlarda sekin ishlaydi.

Stek hamma joyda uchraydi: brauzerdagi “Orqaga” tugmasi, matn muharririda amalni bekor qilish (Ctrl+Z), funksiyalar chaqiruvlari tartibi (rekursiyada ham), ifodadagi qavslar to‘g‘riligini tekshirish. Navbat esa printerga yuborilgan hujjatlar, tarmoqdagi paketlar va operatsion tizimdagi jarayonlarni bajarish tartibida qo‘llaniladi.

Asosiy xulosalar

Stek LIFO tamoyilida ishlaydi: oxirgi qo‘shilgan element birinchi olinadi.
Navbat FIFO tamoyilida ishlaydi: birinchi qo‘shilgan element birinchi olinadi.
Stek amallari: push, pop, peek; navbat amallari: enqueue, dequeue.
Python’da stek ro‘yxat bilan, navbat esa collections.deque bilan qulay amalga oshiriladi.
Stek bekor qilish va qavslarni tekshirishda, navbat esa vazifalarni tartib bilan bajarishda qo‘llaniladi.

Amaliy topshiriqlar

Bo‘sh stekka ketma-ket 1, 2, 3 elementlarini qo‘shing, so‘ng ikki marta pop bajaring; qaysi elementlar olinishini va stekda nima qolishini yozing. Xuddi shuni bo‘sh navbat bilan takrorlang (enqueue, dequeue) va natijalarni solishtiring.
Python’da stek yordamida qavslar to‘g‘ri joylashganini tekshiradigan dastur yozing: (()[]) to‘g‘ri, ([)] esa noto‘g‘ri hisoblansin.
deque yordamida “printer navbati” dasturini yozing: foydalanuvchi hujjat nomlarini kiritsin, dastur esa ularni kiritilish tartibida “chop etsin” (ekranga chiqarsin).

Mustahkamlash savollari

O‘zingizni sinab ko‘ring: avval o‘ylab ko‘ring, keyin javobni oching.

1Stek va navbat orasidagi asosiy farq nimada?Javobni ko‘rish

Stekda oxirgi kirgan element birinchi chiqadi (LIFO), navbatda esa birinchi kirgan birinchi chiqadi (FIFO).

2Brauzerdagi “Orqaga” tugmasi qaysi tuzilmaga o‘xshaydi va nima uchun?Javobni ko‘rish

Stekka: oxirgi ochilgan sahifaga birinchi bo‘lib qaytiladi.

3Nima uchun navbat uchun odatda oddiy ro‘yxat emas, `deque` ishlatiladi?Javobni ko‘rish

Ro‘yxatda `pop(0)` barcha elementlarni surishni talab qiladi va sekin; `deque` esa ikkala uchida ham tez ishlaydi.