Ma’lumotlar tuzilmasi va algoritmlar 11- ma’ruza: Stek, navbat va dek. Ma’ruza rejasi Plan lecture

#include
Navbatni dasturda e’lon qilish quyidagicha:
Queue nav1;

Navbatdagi asosiy amallar

Navbat ustida quyidagi amallar bajariladi:

• Insert( q , i ) – navbatga yangi element kiritish, bu yerda q – stek uchi, i - stekga kiritiladigan element;
• Remove ( q ) – navbat boshidan elementni o’chirish;
• Empty ( q ) – navbatni bo’sh yoki bo’sh emasligini tekshirish (natija: true - bo’sh, false – bo’sh emas);
• Clear()- navbatni tozalash.
• isEmpty()– navbatni bo’shlikka tekshirish
• enqueue(el)—elelementni navbatga joylashtirish
• dequeue() —navbatdan birinchi elementni olish
• firstEl() — navbatning birinchi elementini uni o’chirmasdan qaytaradi

Navbatdagi asosiy amallar

Navbatda bajariladigan enqueue va dequeue amallari rasmda keltirilgan. Steklardan farqli ravishda navbatlarda o’zgarishlar uning oxirida va boshida bo’lishi nazorat qilinishi lozim. Elementlar navbatga oxiridan joylashtiriladi, olish esa boshidan amalga oshiriladi.

Navbatdagi asosiy amallar

Faraz qilaylik, navbat bir o’lchamli massiv ko’rinishida ifodalangan bo’lib uning uzunligi max_q ga teng bo’lsin, ya’ni queue[max_q]. Bu yerda first –navbat boshi, last navbat oxiri, x esa BT turga tegishli element.

void Insert(int last, BT x) {

if (last= =max_q) exit(1);

queue[last]=x;

last++; }

void Empty(int first, last) {

if (first= =last) p=1;

else p=2; }

void Remove(int first, last) {

if (first= =last) exit(1);

first++; }

Navbatning turlari

• Navbatning yana bir turi bu dekdir.
• Dek (DEQ - Double Ended Queue) - ikkita chetli navbat.
• Dekning o’ziga xos xususiyati shundan iboratki, elementlarni yozish va o’qishni har ikkala chetidan xam amalga oshirish mumkin.

• Dekni quyi chegaralari birlashtirilgan ikkita stek ko’rinishda qarash mumkin.
• Barcha turdagi navbatlarni foydalanuvchi dasturlarida massiv yoki bir bog’lamli (oshkor) ro’yxatlar ko’rinishida tasvirlash qulay va tushunarli.