11-dars: Stek

2-darajaKumush — usullar9–16 darslar

HayotdaKutubxona

Stol ustida kitoblar ustma-ust turibdi. Pastdagisini olish uchun avval ustidagi hammasini olib qo’yish kerak. Hech kim bunga e’tibor bermaydi — bu shunchalik tabiiy. Lekin aynan shu tartib programmalashda eng ko’p ishlatiladigan tuzilmalardan biri.

Bu darsdan keyin siz

• stekni Python ro’yxati bilan yozasiz va uning ikki amalini bilasiz
• qavslar to’g’riligini tekshirasiz
• «keyingi katta element» masalasini O(n) da yechasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·5–6 ta kitob yoki daftar

Kitoblarni birma-bir ustma-ust qo’ying va har qo’yganda nomini ayting. Endi sinfdoshingiz «uchinchi qo’ygan kitobingni ber» desin.

Nechta kitobni olib qo’yishga to’g’ri keldi? Endi «oxirgi qo’yganingni ber» desin — necha harakat kerak bo’ldi?

Nimani sezishingiz kerak

Oxirgisi bepul, o’rtadagisi qimmat. Stek aynan shuni ta’minlaydi: bitta uchi tez ishlaydi va shu cheklov uni sodda va ishonchli qiladi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Stek nima

stekstack

Elementlar faqat bir uchidan qo’shiladigan va o’sha uchidan olinadigan tuzilma. «Oxirgi kelgan birinchi ketadi» qoidasi bilan ishlaydi.

Python’da alohida tur kerak emas: oddiy ro’yxatning append() va pop() amallari aynan stek amallari va ikkalasi ham o’zgarmas vaqtda ishlaydi.

Siz stek bilan allaqachon tanishsiz. Python Basic 14-darsidagi chaqiruv steki — o’sha narsa: funksiya chaqirilganda stekka qo’shiladi, tugaganda olinadi. RecursionError esa stek to’lganini bildiradi.

Birinchi misol: qavslar

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1def togrimi(s):2  stek = []3  juft = {")": "(", "]": "[", "}": "{"}4  for b in s:5      if b in "([{":6          stek.append(b)7      elif not stek or stek.pop() != juft[b]:8          return False9  return not stek10print(togrimi("([]{})"), togrimi("(]"), togrimi("(("))

Sizning bashoratingizTekshirish

Javobni ko'rish

True False False

Uchta holat: to'g'ri, mos kelmagan juftlik va yopilmagan qavs. Oxirgi return not stek aynan uchinchi holatni ushlaydi — stekda qolgan qavs ochiq qolgan degani.

Nega stek: yopuvchi qavs har doim eng oxirgi ochilgan qavsga tegishli. Bu esa stekning ta’rifi bilan bir xil gap.

Sekin yechim

Endi asosiy masala. Qatorda o’quvchilar turibdi; har biri uchun o’ngdagi birinchi baland kishini toping. To’liq izlash har o’quvchidan o’ngga yuguradi.

sekin.pyNusxalash

1boy = [3, 1, 4, 1, 5, 9]2javob = []3for i in range(len(boy)):4  topilgan = -15  for j in range(i + 1, len(boy)):6      if boy[j] > boy[i]:7          topilgan = boy[j]8          break9  javob.append(topilgan)10print(javob)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1boy = [3, 1, 4, 1, 5, 9]2javob = []3for i in range(len(boy)):4  topilgan = -15  for j in range(i + 1, len(boy)):6      if boy[j] > boy[i]:7          topilgan = boy[j]8          break9  javob.append(topilgan)10print(javob)

Sizning bashoratingizTekshirish

Javobni ko'rish

[4, 4, 5, 5, 9, -1]

Oxirgi o'quvchidan baland hech kim yo'q, shuning uchun -1. Kamayuvchi tartibda turgan qatorda esa har o'quvchi oxirigacha yugurishga majbur bo'ladi.

Nega sekin

Eng yomon holat — qator kamayuvchi tartibda tursa. Unda har o’quvchi oxirigacha yuguradi va hech narsa topmaydi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 5 000	n = 200 000
Har birdan o‘ngga yugurishn^2	10⁶sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
Stek bilan bir yurishn	1 000sig‘adi	5 000sig‘adi	200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

O’ngdan chapga yuramiz va stekda faqat hali kerak bo’lishi mumkin bo’lganlarni saqlaymiz. Yangi o’quvchi kelganda undan past bo’lganlar stekdan chiqariladi: ular endi hech kimga «birinchi baland» bo’la olmaydi, chunki yangi kelgan ham balandroq, ham yaqinroq.

tez.pyNusxalash

1boy = [3, 1, 4, 1, 5, 9]2javob = [-1] * len(boy)3stek = []4for i in range(len(boy) - 1, -1, -1):5  while stek and stek[-1] <= boy[i]:6      stek.pop()7  if stek:8      javob[i] = stek[-1]9  stek.append(boy[i])10print(javob)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1boy = [3, 1, 4, 1, 5, 9]2javob = [-1] * len(boy)3stek = []4for i in range(len(boy) - 1, -1, -1):5  while stek and stek[-1] <= boy[i]:6      stek.pop()7  if stek:8      javob[i] = stek[-1]9  stek.append(boy[i])10print(javob)

Sizning bashoratingizTekshirish

Javobni ko'rish

[4, 4, 5, 5, 9, -1]

Javob avvalgisi bilan bir xil. Farqi — bu yechim har elementni bir marta ko'radi.

◆Asosiy g'oya

Ichkarida while turibdi, lekin yechim baribir O(n). Sabab: har element stekka bir marta kiradi va bir marta chiqadi. Jami pop() soni n dan oshmaydi, qanchalik chuqur ichma-ich ko’rinmasin.

Sinab ko’r

Vizualda stekdan nima chiqib ketayotganini kuzating. Chiqqan element boshqa hech qachon kerak bo’lmaydi — algoritmning butun tejami shunda.

Stek — keyingi katta element

Stekdan nima chiqib ketayotganiga qarang: chiqqan element boshqa hech qachon kerak bo'lmaydi.

O'ngdan chapga yurib, stekda kamayuvchi bo'ylar saqlanadi; stek uchi — javob.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Har o'quvchi uchun o'ngdagi birinchi baland kishini qidiramiz. O'ngdan chapga yuramiz — o'ng tomon allaqachon ko'rilgan bo'ladi.
2. Stek bo'sh: 9 dan o'ngda undan baland odam yo'q. Javob -1.
3. 5 uchun javob — stek uchidagi 9.
4. 1 uchun javob — stek uchidagi 5.
5. 1 stekdan chiqdi: u 4 dan past. Endi u hech kimga «birinchi baland» bo'la olmaydi — 4 ham balandroq, ham yaqinroq.
6. 4 uchun javob — stek uchidagi 5.
7. 1 uchun javob — stek uchidagi 4.
8. 1 stekdan chiqdi: u 3 dan past. Endi u hech kimga «birinchi baland» bo'la olmaydi — 3 ham balandroq, ham yaqinroq.
9. 3 uchun javob — stek uchidagi 4.
10. Tayyor. Ichkarida while sikli bo'lsa ham, jami 8 amal ketdi: har element stekka bir marta kirdi va bir marta chiqdi.

bo'ylar

301142135495

javob

stek

Har o'quvchi uchun o'ngdagi birinchi baland kishini qidiramiz. O'ngdan chapga yuramiz — o'ng tomon allaqachon ko'rilgan bo'ladi.

Amal0

OrqagaO‘ynatishOldinga1/10Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

11 / 40

MasalaQavslar to'g'ri joylashganini tekshiring.

Taklif qilingan yechim

1. 1Ochuvchi qavs uchrasa stekka qo‘shamiz.
2. 2Yopuvchi qavs uchrasa stekdan bittasini olamiz va mos kelishini tekshiramiz.
3. 3Mos kelmasa — javob «noto‘g‘ri».
4. 4Satr tugagach javob «to‘g‘ri».

Bu javobning 4-qismi noto'g'ri. Satr tugaganda stek BO'SH ekanini ham tekshirish kerak. (( satrida hech qanday nomuvofiqlik yo'q, lekin ikkita qavs ochiq qoladi. Shuningdek ikkinchi qadamda stek bo'sh bo'lsa pop() xato beradi — ) bilan boshlanadigan satrda shunday bo'ladi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Python'da stek uchun qaysi ikki amal ishlatiladi?

Javobni ko'rish

append() — uchiga qo’shish, pop() — uchidan olish. Ikkalasi ham o’zgarmas vaqtda ishlaydi, chunki ro’yxatning oxiri bilan ishlanadi.

2Nega qavslar masalasida aynan stek kerak?

Javobni ko'rish

Yopuvchi qavs har doim eng oxirgi ochilgan qavsga tegishli. «Eng oxirgisi» degan talab — stekning ta’rifi.

3Ichida while bo'lgan yechim nega O(n) bo'lib qoladi?

Javobni ko'rish

Har element stekka bir marta kiradi va bir marta chiqadi. Demak barcha pop() chaqiruvlari jami n tadan oshmaydi.

4Bo'sh stekdan pop() qilinsa nima bo'ladi?

Javobni ko'rish

IndexError chiqadi va programma to’xtaydi. Shuning uchun har pop() dan oldin if stek: tekshiruvi turishi kerak.

5Chaqiruv steki bilan bu darsdagi stek bir narsami?

Javobni ko'rish

Ha, bir tuzilma. Funksiya chaqirilganda chaqiruv stekiga qo’shiladi, tugaganda olinadi. RecursionError — o’sha stek to’lgani.

Masalalar

Masalalar

3 ta

• Nearest Smaller ValuesCSES 1645o'rta

  Darsdagi masalaning ko‘zgudagi aksi: chapda birinchi KICHIK element.

• Bracket SequenceCodeforces 223Ao'rta

  Stekda indekslarni saqlang — uzunlikni hisoblash uchun o‘rin kerak bo‘ladi.

• TowersCSES 1073o'rta

  Bu yerda stek emas, ko‘p stek kerak. Har kubni qaysi minoraga qo‘yish afzalligini o‘ylang.

Lokal mashq: mashqlar/11-keyingi-katta/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

3 1 4 1 5 9 2 6 qatori uchun har o’quvchining o’ngdagi birinchi baland qo’shnisini qog’ozda toping. Keyin xuddi shuni stek bilan qadamma-qadam yozib chiqing: stekda qachon nima turgan?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

11-keyingi-katta masalasini yeching. Yechimingizni ikki chegara holatida sinang: butunlay o’suvchi qator va butunlay kamayuvchi qator. Qaysi birida stek eng katta bo’ladi?

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Qavslar masalasini kengaytiring: satr noto’g’ri bo’lsa, nechanchi belgida buzilganini ham chiqaring. Ochiq qolgan qavs holatida javob nima bo’lishi kerak?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim