Circular Queue

Doiraviy navbat (Circular Queue) — bu oddiy navbatning (regular queue) kengaytirilgan ko'rinishi bo'lib, unda oxirgi element birinchi elementga ulangan bo'ladi. Shu tariqa u aylanma (doira shaklidagi) tuzilmani hosil qiladi.

Doiraviy navbat oddiy navbatning eng katta kamchiligini bartaraf etadi. Oddiy navbatda ma'lum miqdorda element kiritilib va o'chirilgandan so'ng, foydalanib bo'lmaydigan bo'sh joylar paydo bo'ladi.

Bu yerda 0 va 1 indekslaridan faqat butun navbat tozalangandan (barcha elementlar o'chirilgandan) keyingina qayta foydalanish mumkin. Bu esa navbatning haqiqiy sig'imini kamaytirib yuboradi.

Doiraviy navbat qanday ishlaydi?

Doiraviy navbat doiraviy oshirish (circular increment) jarayoni orqali ishlaydi, ya'ni ko'rsatkichni oshirib navbatning oxiriga yetganimizda, yana navbat boshiga o'tamiz.

Doiraviy oshirish navbat o'lchamiga qoldiq bo'lish (modulo bo'lish — %) amali yordamida bajariladi:

if REAR + 1 == 5 (to'ldi!), REAR = (REAR + 1) % 5 = 0 (navbatning boshi)

Doiraviy navbat amallari

Doiraviy navbat quyidagi tartibda ishlaydi:

• Ikki ko'rsatkich: FRONT va REAR ishlatiladi
• FRONT navbatning birinchi elementini kuzatib boradi
• REAR navbatning oxirgi elementini kuzatib boradi
• Dastlab, FRONT va REAR qiymatlari -1 ga tenglashtiriladi

1. Enqueue

Element qo'shish (Enqueue):

• Navbat to'lganligini tekshirish
• Birinchi element kiritilayotganda, FRONT qiymatini 0 ga o'rnatish
• REAR indeksini doiraviy ravishda 1 taga oshirish (ya'ni rear oxiriga yetsa, keyingisi navbat boshiga o'tadi)
• Yangi elementni REAR ko'rsatib turgan joyga qo'shish

2. Dequeue

Element o'chirish (Dequeue):

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

Biroq, navbat to'lganligini tekshirishda yangi qo'shimcha holat mavjud:

• 1-holat: FRONT == 0 && REAR == SIZE - 1
• 2-holat: FRONT == REAR + 1

Ikkinchi holat doiraviy oshirish sababli REAR 0 dan boshlanib, uning qiymati FRONT dan atigi 1 taga kichik bo'lganda yuz beradi — bu navbatning to'lganligini bildiradi.

Navbatni amalga oshirishning eng keng tarqalgan usuli massivlardan foydalanishdir, ammo uni ro'yxatlar (linked list) yordamida ham amalga oshirish mumkin.

Doiraviy navbatning Go, Python, Java, C va C++ tillaridagi dasturiy kodi

// Circular Queue implementation in Go
package main

import "fmt"

const SIZE = 5

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

func NewCircularQueue() *CircularQueue {
	return &CircularQueue{
		front: -1,
		rear:  -1,
	}
}

// Navbat to'lganligini tekshirish
func (q *CircularQueue) isFull() bool {
	if q.front == 0 && q.rear == SIZE-1 {
		return true
	}
	if q.front == q.rear+1 {
		return true
	}
	return false
}

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

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

// Element o'chirish (Dequeue)
func (q *CircularQueue) 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 = (q.front + 1) % SIZE
	}
	return element
}

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

	fmt.Printf("Front -> %d\n", q.front)
	fmt.Print("Items -> ")
	i := q.front
	for {
		fmt.Printf("%d ", q.items[i])
		if i == q.rear {
			break
		}
		i = (i + 1) % SIZE
	}
	fmt.Printf("\nRear -> %d\n", q.rear)
}

func main() {
	q := NewCircularQueue()

	// front = -1 bo'lgani uchun amal bajara olmaydi
	q.deQueue()

	q.enQueue(1)
	q.enQueue(2)
	q.enQueue(3)
	q.enQueue(4)
	q.enQueue(5)

	// front == 0 va rear == SIZE - 1 bo'lgani uchun to'lgan deb xabar beradi
	q.enQueue(6)

	q.display()

	elem := q.deQueue()
	if elem != -1 {
		fmt.Printf("Deleted Element is %d\n", elem)
	}

	q.display()

	q.enQueue(7)
	q.display()

	// front == rear + 1 bo'lgani uchun to'lgan
	q.enQueue(8)
}

Doiraviy navbatning murakkablik tahlili

Massiv yordamida yaratilgan doiraviy navbatda enqueue va dequeue amallarining vaqt murakkabligi O(1) ga teng.

Doiraviy navbatning amaliy qo'llanilishi

• CPU rejalashtirish (CPU scheduling)
• Xotirani boshqarish (Memory management)
• Trafikni boshqarish (Traffic Management)