10-ma’ruza: navbat tuzilmalari: stek, navbat va dek reja

struct Node {

int data;

Node *next, *prev;

};

typedef Node *PNode;

Ro’yxat oxiri va boshi uchun alohida ko’rsatkich bilan ishlamasdan, navbat haqidagi barcha axborotlarni saqlovchi tuzilmani e’lon qilamiz:

struct Queue {

PNode head, tail;

};

Eng birinchi o’rinda ikkita ko’rsatkichga ham NULL qiymatni ta’minlaymiz. Aynan shunday holatni stek 0443un ham ishlatgan edik. Xuddi shunday navbatning birinchi elementni olish funktsiyasi (Pop) stek cho’qqisidan elementni o’chirish funktsiyasiga mos keladi. Ushbu fnuktsiyani mustaqil ravishda yozing.

Navbat oxiridan element qo’shish. Navbat oxiridan element qo’shish ikki bog’lamli ro’yxat oxiridan yangi element qo’shish protsedurasi bilan bir xil. Protsedura parametrida yangi tugun qo’shish emas, balki tugun uchun ma’lumot (qiymat), ya’ni butun son qo’shish kerak bo’ladi. Yangi element uchun xotira protseduraning ichida ajratiladi.

void PushTail (Queue &Q, int x) {

PNode NewNode;

NewNode = new Node; // yangi tugun hosil qilish

NewNode->data = x; // tugunni ma’lumot bilan to’ldirish

NewNode->prev = Q.Tail;

NewNode->next = NULL;

if (Q.tail) // ro’yxat oxiridan tugun qo’shish

Q.tail->next = NewNode;

Q.tail = NewNode;

if (!Q.head ) Q.head = Q.tail;

} 

3. Dek

Dek (deque) – bu tartiblangan elementlar to’plami bo’lib, yangi elemento qo’shish va mavjud elementni o’chirish tuzilmaning ixtiyoriy oxiridan ruxsat beriladi.

Dekni massiv asosida yoki ikki bog’lamli ro’yxat asosida tadbiq qilish mumkin. Dek tuzilmasi ustida quyidagi to’rtta amalni bajarish mumkin:

1)   boshidan element qo’shish;

2)   oxiridan element qo’shish;

3)   boshidan elementni o’chirish;

4)   oxiridan elementni o’chirish.

Bu amallarni yuqorida stek va navbat tuzilmalarida qo’llanilgan protseduralar yordamida tadbiq qilish mumkin. 

4. Mustaqil ishlash uchun masalalar

1-masala. Stekka element qo’shish va elementni o’chirish amallarini stekni massiv orqali tadbiq qilish yordamida bajarish dasturini tuzing.

2-masala. Oddiy va tsiklik navbatga element qo’shish va elementni o’chirish amallarini navbatni massiv orqali tadbiq qilish yordamida bajarish dasturini tuzing.

3-masala. Dek ustida bajariladigan standart amallarni bajarish dasturini tuzing. 

Adabiyotlar

1. [RU]  Alfred V. Axo., Djon E. Xopkroft, Djefri D. Ul’man. Struktura dannыx i algoritmы. //Ucheb.pos., M.: Izd.dom: "Vil’yams", 2000, — 384 s.

2. [EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.

3. [UZ] I.M.Boynazarov. Dinamik ma’lumotlar tuzilmasi. Uslubiy qo’llanma. -Samarqand, TATU Samarqand filiali, 2018 y. 215 bet.

4. [UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.