09 / 69

Queue

Navbat ma'lumotlar tuzilmasi

Navbat (Queue) — dasturlashda eng ko'p ishlatiladigan foydali ma'lumotlar tuzilmasidir. U xuddi kinoteatr kassasi oldidagi chipta olish navbatiga o'xshaydi: navbatga birinchi bo'lib kelgan odam birinchi bo'lib chipta oladi va navbatdan chiqadi.

Navbat FIFO (First In First Out — birinchi kirgan birinchi chiqadi) qoidasiga amal qiladi: navbatga birinchi kiritilgan element undan birinchi bo'lib chiqariladi.

Navbatning FIFO tartibida ishlashi

Yuqoridagi rasmda 1 soni 2 dan oldin navbatga qo'yilgani sababli, navbatdan birinchi bo'lib ham aynan 1 o'chiriladi. Bu FIFO qoidasidir.

Dasturlash atamalarida, elementlarni navbatga kiritish enqueue deb, elementlarni navbatdan chiqarish esa dequeue deb ataladi.

Biz navbatni C, C++, Java, Python, Go yoki C# kabi istalgan dasturlash tilida yaratishimiz mumkin, ammo ularning ishlash tamoyili bir xil bo'lib qoladi.

Navbat — bu quyidagi amallarni bajarishga imkon beruvchi obyekt (abstrakt ma'lumot turi — ADT):

  • Enqueue: Navbatning oxiriga yangi element qo'shish
  • Dequeue: Navbatning boshidan elementni o'chirish (olish)
  • IsEmpty: Navbatning bo'shligini tekshirish
  • IsFull: Navbatning to'lganligini tekshirish
  • Peek: Navbat boshidagi elementni o'chirmasdan uning qiymatini ko'rish

Navbat amallari quyidagicha ishlaydi:

  • Ikki ko'rsatkich (pointer): FRONT (boshi) va REAR (oxiri) ishlatiladi
  • FRONT navbatning birinchi elementini kuzatib boradi
  • REAR navbatning oxirgi elementini kuzatib boradi
  • Dastlab, FRONT va REAR qiymatlari -1 ga teng qilib o'rnatiladi

Navbatda Enqueue va Dequeue amallarining ishlashi

1. Enqueue

Element qo'shish (Enqueue):

  • Navbat to'lganligini tekshirish
  • Birinchi element uchun FRONT qiymatini 0 ga o'rnatish
  • REAR indeksini 1 taga oshirish
  • Yangi elementni REAR ko'rsatib turgan joyga joylashtirish

2. Dequeue

Element o'chirish (Dequeue):

  • Navbat bo'shligini tekshirish
  • FRONT ko'rsatib turgan qiymatni qaytarish
  • FRONT indeksini 1 taga oshirish
  • Oxirgi element ham o'chirilganda, FRONT va REAR qiymatlarini qaytadan -1 ga o'rnatish

Java va C/C++ tillarida navbatni amalga oshirishda odatda massivlar (arrays), Python tilida esa ro'yxatlar (lists) ishlatiladi.

// Queue implementation in Go
package main

import "fmt"

const SIZE = 5

type Queue struct {
	items [SIZE]int
	front int
	rear  int
}

func NewQueue() *Queue {
	return &Queue{
		front: -1,
		rear:  -1,
	}
}

// Navbat to'lganligini tekshirish
func (q *Queue) isFull() bool {
	return q.rear == SIZE-1
}

// Navbat bo'shligini tekshirish
func (q *Queue) isEmpty() bool {
	return q.front == -1
}

// Element qo'shish (Enqueue)
func (q *Queue) enQueue(element int) {
	if q.isFull() {
		fmt.Println("Queue is full")
	} else {
		if q.front == -1 {
			q.front = 0
		}
		q.rear++
		q.items[q.rear] = element
		fmt.Printf("Inserted %d\n", element)
	}
}

// Element o'chirish (Dequeue)
func (q *Queue) deQueue() int {
	if q.isEmpty() {
		fmt.Println("Queue is empty")
		return -1
	}

	element := q.items[q.front]
	if q.front >= q.rear {
		q.front = -1
		q.rear = -1
	} else {
		q.front++
	}
	fmt.Printf("Deleted -> %d\n", element)
	return element
}

// Navbat elementlarini ekranga chiqarish
func (q *Queue) display() {
	if q.isEmpty() {
		fmt.Println("Empty Queue")
		return
	}

	fmt.Printf("\nFront index-> %d\n", q.front)
	fmt.Print("Items -> ")
	for i := q.front; i <= q.rear; i++ {
		fmt.Printf("%d ", q.items[i])
	}
	fmt.Printf("\nRear index-> %d\n", q.rear)
}

func main() {
	q := NewQueue()

	// Bo'sh navbatda deQueue bajarib bo'lmaydi
	q.deQueue()

	// 5 ta element qo'shish
	q.enQueue(1)
	q.enQueue(2)
	q.enQueue(3)
	q.enQueue(4)
	q.enQueue(5)

	// 6-elementni qo'shib bo'lmaydi, chunki navbat to'lgan
	q.enQueue(6)

	q.display()

	// deQueue birinchi kiritilgan elementni (1) olib tashlaydi
	q.deQueue()

	// Endi bizda 4 ta element qoldi
	q.display()
}

Oddiy navbatning cheklovlari

Quyidagi rasmda ko'rishingiz mumkinki, biroz elementlar kiritilib (enqueue) va o'chirilgandan (dequeue) so'ng, navbatning o'lchami qisqarib boradi:

Oddiy chiziqli navbatning cheklovi

Va biz 0 hamda 1 indekslariga faqat navbat to'liq bo'shatilib, qaytadan boshlangandagina element qo'sha olamiz.

REAR oxirgi indeksga yetib borgandan so'ng, agar biz oldinda bo'shagan joylarga (0 va 1 indekslarga) qo'shimcha elementlarni saqlay olsak, bo'sh joylardan unumli foydalangan bo'lardik. Ushbu imkoniyat Doiraviy navbat (Circular Queue) deb ataladigan takomillashtirilgan navbat orqali amalga oshiriladi.

Murakkablik tahlili

Massiv yordamida yaratilgan navbatda enqueue va dequeue amallarining vaqt murakkabligi O(1) ga teng. Agar siz Python kodida pop(N) dan foydalansangiz, o'chirilayotgan elementning o'rniga qarab murakkablik O(n) bo'lishi mumkin.

  • CPU va Disk rejalashtirish (CPU scheduling, Disk Scheduling)
  • Ma'lumotlar ikki jarayon o'rtasida asinxron uzatilganda sinxronizatsiya uchun navbat ishlatiladi. Masalan: IO buferlari, quvurlar (pipes), fayl IO va boshqalar.
  • Real vaqtli tizimlarda uzilishlarni (interrupts) boshqarish.
  • Call Center telefon tizimlari qo'ng'iroq qiluvchilarni navbat tartibida kutib turish uchun navbat ma'lumotlar tuzilmasidan foydalanadi.

Tavsiya etilgan keyingi mavzular: