Salom blogimning o’quvchilari! Siz bilan kamina Oxunjon. Bugungi maqolam ma’lumotlar tuzilishi va algoritm mavzusiga tegishli bo’ladi yana ham aniqrog’i Queue ma’lumot tuzilishi haqida.
Queue – dasturlashda foydali ma’lumot tuzilishi. Bu kino zalidan tashqarida chipta olish uchun navbatda turgan odamlarga o’xshaydi, navbatta birinchi turgan, birinchi chipta oladi.
Queue First in First out (FIFO) qoidasiga bo’yicha ishlaydi ya’ni birinchi kelgan element birinchi chiqadi.
Yuqoridagi rasmda, queued 1 2-dan oldin turgani uchun ham queuedan birinchi bo’lib o’chiriladi. Bu FIFO qoidasiga amal qiladi.
Dasturlash terminlarida, queueda biron bir elementni qo’yish “enqueue” deb nomlanadi va elementni olib tashlash “dequeuer” deb ataladi.
Biz C, C ++, Java, Python yoki C # kabi biron bir dasturiy tilda Queueni bajarishimiz mumkin, lekin xususiyatlari deyarli bir xil.
DIQQAT E’LON! Java dasturlash tillari bo’yisha video kurs tayyor. Video kurs haqidagi ma’lumotni quyidagi rasm ustiga bosib o’qishingiz mumkin:
Queue xususiyatlari
Queue obyektdir yoki quyidagi operatsiyalarni bajarish imkonini beradigan maxsus mavhum ma’lumot tuzilishi (ADT):
- Enqueue: queuening oxiriga element qo’shadi.
- Dequeue: queuening boshidan elementni olib tashlaydi.
- IsEmpty: Queue bo’shligini tekshiradi.
- IsFull: Queue to’liq ekanligini tekshiradi.
- Peek: Queuening eng oldingi qiymatini olib tashlamasdan qaytaradi.
Queue qanday ishlaydi?
Queue operatsiyalari quyidagi kabi ishlaydi:
- FRONT va REAR deb ataladigan ikkita pointerlar (ko’rsatkichlar) queuedagi birinchi va oxirgi elementni kuzatish uchun ishlatiladi.
- Queuega boshlang’ich qiymat berganda, FRONT va REAR ning qiymatini -1 ga tenglab qo’yamiz.
- Element qo’shishda, REAR indeksining qiymatini oshiramiz va yangi elementni REAR tomonidan ko’rsatilgan joyga joylashtiramiz.
- Elementni olib tashlashda, FRONT tomonidan ko’rsatilgan qiymatni qaytaramiz va FRONT indeksini oshiramiz.
- Element qo’shishdan oldin queue allaqachon to’liqmi yoki yo’qmi tekshiramiz.
- Elementni olib tashlashdan oldin queue bo’sh yoki bo’sh emasligini tekshiramiz.
- Birinchi elementni qo’shishda FRONT ning qiymatini 0 ga tenglashtiramiz.
- Oxirgi elementni olib tashlashda FRONT va REAR ning qiymatini -1 ga tenglashtiramiz.
Dasturlash tillarida queuening amalga oshirilishi.
Ko’pincha queuelar massivlardan foydalanib amalga oshiriladi, lekin u list-lardan foydalanib ham amalga oshirilishi mumkin.
C++ dasturlash yordamida amalga oshirish.
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if (front == 0 && rear == SIZE – 1){
return true;
}
return false;
}
bool isEmpty(){
if (front == -1) return true;
else return false;
}
void enQueue(int element){
if (isFull()){
cout << «Queue to’lgan»;
}
else {
if (front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl << «Kiritildi (qo’shildi) « << element << endl;
}
}
int deQueue(){
int element;
if (isEmpty()){
cout << «Queue is empty» << endl;
return(-1);
}
else {
element = items[front];
if (front >= rear){
front = -1;
rear = -1;
} /* Queueda faqat bitta element bor, uni olib tashlaganimizdan so’ng queueni
qayta sozlaymiz */
else {
front++;
}
cout << endl << «Olib tashlandi -> « << element << endl;
return(element);
}
}
void display()
{
/* Queuening elementlarini ko’rsatadigan funksiya */
int i;
if (isEmpty()) {
cout << endl << «Queue bo’sh» << endl;
}
else
{
cout << endl << «Front -> « << front;
cout << endl << «Elementlar -> «;
for (i = front; i <= rear; i++)
cout << items[i] << «\t»;
cout << endl << «Rear -> « << rear << endl;
}
}
};
int main()
{
Queue q;
// bo’sh queueda deQueue mumkin emas
q.deQueue();
//enQueue 5 – 5 ta elementni kiritish
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// 6-elementni queuega qo’shib bo’lmaydi, chunki queue to’lgan
q.enQueue(6);
q.display();
// deQueue birinchi kiritilgan elementni olib tashlaydi
q.deQueue();
// Endi to’rtta element bor
q.display();
system(«pause»);
return 0;
}
Bu bajarishning cheklovliklari
Quyidagi rasmda ko’rib turganingiz kabi, qo’shish va olib tashlashdan so’ng, queuening o’lchami kamaygan.
0 va 1 indekslaridan faqat barcha elementlar o’chirilganda queueni tiklashdan keyin foydalanish mumkin. Shuning uchun ham Circular queuening imkoniyatlaridan foydalanamiz.
Ammo bu to’g’risida keyingi maqolalarimizda to’xtalamiz. Hozircha esa maqolaga yakun yasab, sizlar bilan xayrlashaman, xayr!
Muallif: Oxunjon G’aybullayev
