Masala: [], {} va () uchta tiplardan tashkil topgan satr berilgan. Qavslar to’g’ri qo’yilganligini tekshiring (boshqa simvollarga qaramagan holda). Masalan:
[()]{} ][ [({)]}
Yechim: qavslar ichma ichligini hisoblagich. Agarda hisoblagich 0 bo’lsa, qavs to’gri qo’yilgan bo’ladi.
Bu masalani uchta hisoblagich bilan qilsa bo’ladimi?
?
[ ( { ) ] }
(: 0 1 0
[: 0 1 0
{: 0 1 0
[ ( { ) ] }
( ( ) ) ( )
1 2 1 0 1 0
( ( ) ) ( )
( ( ) ) ) (
1 2 1 0 -1 0
( ( ) ) ) (
( ( ) ) (
1 2 1 0 1
( ( ) ) (
Qavslar masalasi
Algoritm:
Boshida stek bo’sh;
Sikl boshida satr barcha simvollarini tartib bo’yiicha ko’rib chiqamiz;
Agar navbatdagi simvol ochiladigan qavs bo’lsa, uni stek boshiga o’tkazamiz;
Agar simvol yopiladigan qavs bo’lsa, stek boshini tekshiramiz: u yerda berilgan qavsga mos ochiluvchi qavs bo’lishi lozim (agarda bunday bo’lmasa, u holda xatolik);
Agar stek oxiri bo’sh bo’lmasa, u holda ifoda noto’g’ri.
Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi.
Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi.
Navbat bizga nima uchun kerak!
!
Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur.
Navbat qanday ishlaydi!
!
Navbat
Biz hammamiz magazinda navbatga turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat.
Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori).
Klassik navbatni ko’rib chiqamiz:
birinchi kelgan birinchi ketadi (FIFO – first input, first output)
Navbat har ikkala tomondan ochiq bo’ladi.
Navbat
Universal navbat har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir:
struct slist_node
{
void* info;
struct slist_node* next;
};
struct que
{
struct slist_node* beg;
struct slist_node* end;
int size;
int width;
};
Bu yerda beg birinchi tugunga ko’rsatkich, end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni