Deque

Deque (Double Ended Queue — ikki tomonlama navbat) navbatning maxsus turi bo'lib, unda elementlarni qo'shish va o'chirish amallari navbatning ham oldi (front), ham orqa (rear) tomonidan amalga oshirilishi mumkin. Shu sababli, u FIFO (First In First Out) qoidasiga to'liq bo'ysunmaydi.

Deque turlari

• Input Restricted Deque (Kiritish cheklangan Deque): Ushbu dequeda yangi element kiritish faqat bitta tomondan cheklangan, ammo elementlarni o'chirish har ikki tomondan ham ruxsat etiladi.
• Output Restricted Deque (Chiqarish cheklangan Deque): Ushbu dequeda element chiqarish (o'chirish) faqat bitta tomondan cheklangan, ammo elementlarni kiritish har ikki tomondan ham ruxsat etiladi.

Deque amallari

Quyida dequening aylanma massiv (circular array) orqali amalga oshirilishi keltirilgan. Aylanma massivda, agar massiv to'lsa, yana boshidan boshlanadi.

To'g'ri chiziqli oddiy massivda esa massiv oxiriga yetsa, boshqa element kiritib bo'lmaydi. Quyidagi har bir amalda agar massiv to'lsa, "overflow" (to'lib ketish) xabari chiqariladi.

Quyidagi amallarni bajarishdan oldin ushbu boshlang'ich qadamlar bajariladi:

1. n o'lchamli massiv (deque) olinadi.
2. Ikkita ko'rsatkich o'rnatiladi: front = -1 va rear = 0.

1. Insert Front

Old tomondan qo'shish:

Bu amal yangi elementni navbatning old tomoniga (front) qo'shadi:

1. Dequening to'lganligini tekshirish.

2. Agar deque to'lgan bo'lsa (ya'ni (front == 0 && rear == n - 1) || (front == rear + 1)), qo'shish amali bajarilmaydi (overflow holati).
3. Agar deque bo'sh bo'lsa, front = 0 va rear = 0 qilib qayta o'rnatiladi va yangi element array[front] ga qo'shiladi.
4. Agar front == 0 bo'lsa, front = n - 1 (oxirgi indeks) qilib o'rnatiladi.

5. Aks holda, front qiymati 1 taga kamaytiriladi (front = front - 1).
6. Yangi element array[front] ga joylashtiriladi.

2. Insert Rear

Orqa tomondan qo'shish:

Bu amal yangi elementni navbatning orqa tomoniga (rear) qo'shadi:

1. Dequening to'lganligini tekshirish.

2. Agar deque to'lgan bo'lsa, qo'shish amali bajarilmaydi (overflow holati).
3. Agar deque bo'sh bo'lsa, front = 0 va rear = 0 qilib qayta o'rnatiladi va yangi element array[rear] ga qo'shiladi.
4. Agar rear == n - 1 bo'lsa, rear = 0 (birinchi indeks) qilib o'rnatiladi.
5. Aks holda, rear qiymati 1 taga oshiriladi (rear = rear + 1).

6. Yangi element array[rear] ga joylashtiriladi.

3. Delete Front

Old tomondan o'chirish:

Bu amal elementni old tomondan (front) o'chiradi:

1. Dequening bo'shligini tekshirish.

2. Agar deque bo'sh bo'lsa (front == -1), o'chirish amali bajarilmaydi (underflow holati).
3. Agar dequeda faqat bitta element bo'lsa (front == rear), front = -1 va rear = -1 qilib o'rnatiladi.
4. Aks holda, agar front oxirgi indeksda bo'lsa (front == n - 1), front = 0 qilib o'rnatiladi.
5. Aks holda, front = front + 1 qilib oshiriladi.

4. Delete Rear

Orqa tomondan o'chirish:

Bu amal elementni orqa tomondan (rear) o'chiradi:

1. Dequening bo'shligini tekshirish.

2. Agar deque bo'sh bo'lsa (front == -1), o'chirish amali bajarilmaydi (underflow holati).
3. Agar dequeda faqat bitta element bo'lsa (front == rear), front = -1 va rear = -1 qilib o'rnatiladi.
4. Aks holda, agar rear birinchi indeksda bo'lsa (rear == 0), rear = n - 1 qilib o'rnatiladi.
5. Aks holda, rear = rear - 1 qilib kamaytiriladi.

5. Check Empty

Bo'shlikka tekshirish:

Bu amal dequening bo'sh yoki bo'sh emasligini tekshiradi. Agar front == -1 bo'lsa, deque bo'sh hisoblanadi.

6. Check Full

To'lganlikka tekshirish:

Bu amal dequening to'lganligini tekshiradi. Agar (front == 0 && rear == n - 1) || (front == rear + 1) bo'lsa, deque to'lgan hisoblanadi.

Dequening Go, Python, Java, C va C++ tillaridagi dasturiy kodi

// Deque implementation in Go
package main

import "fmt"

const MAX = 100

type Deque struct {
	arr   [MAX]int
	front int
	rear  int
	size  int
}

func NewDeque(size int) *Deque {
	return &Deque{
		front: -1,
		rear:  0,
		size:  size,
	}
}

// Deque to'lganligini tekshirish
func (dq *Deque) isFull() bool {
	return (dq.front == 0 && dq.rear == dq.size-1) || (dq.front == dq.rear+1)
}

// Deque bo'shligini tekshirish
func (dq *Deque) isEmpty() bool {
	return dq.front == -1
}

// Old tomondan element kiritish
func (dq *Deque) insertFront(key int) {
	if dq.isFull() {
		fmt.Println("Overflow")
		return
	}

	if dq.front == -1 {
		dq.front = 0
		dq.rear = 0
	} else if dq.front == 0 {
		dq.front = dq.size - 1
	} else {
		dq.front = dq.front - 1
	}

	dq.arr[dq.front] = key
}

// Orqa tomondan element kiritish
func (dq *Deque) insertRear(key int) {
	if dq.isFull() {
		fmt.Println("Overflow")
		return
	}

	if dq.front == -1 {
		dq.front = 0
		dq.rear = 0
	} else if dq.rear == dq.size-1 {
		dq.rear = 0
	} else {
		dq.rear = dq.rear + 1
	}

	dq.arr[dq.rear] = key
}

// Old tomondan elementni o'chirish
func (dq *Deque) deleteFront() {
	if dq.isEmpty() {
		fmt.Println("Queue Underflow")
		return
	}

	if dq.front == dq.rear {
		dq.front = -1
		dq.rear = -1
	} else if dq.front == dq.size-1 {
		dq.front = 0
	} else {
		dq.front = dq.front + 1
	}
}

// Orqa tomondan elementni o'chirish
func (dq *Deque) deleteRear() {
	if dq.isEmpty() {
		fmt.Println("Underflow")
		return
	}

	if dq.front == dq.rear {
		dq.front = -1
		dq.rear = -1
	} else if dq.rear == 0 {
		dq.rear = dq.size - 1
	} else {
		dq.rear = dq.rear - 1
	}
}

// Old elementni ko'rish
func (dq *Deque) getFront() int {
	if dq.isEmpty() {
		fmt.Println("Underflow")
		return -1
	}
	return dq.arr[dq.front]
}

// Orqa elementni ko'rish
func (dq *Deque) getRear() int {
	if dq.isEmpty() || dq.rear < 0 {
		fmt.Println("Underflow")
		return -1
	}
	return dq.arr[dq.rear]
}

func main() {
	dq := NewDeque(4)

	fmt.Println("insert element at rear end : 12")
	dq.insertRear(12)

	fmt.Println("insert element at rear end : 14")
	dq.insertRear(14)

	fmt.Println("get rear element :", dq.getRear())

	dq.deleteRear()
	fmt.Println("After delete rear element new rear become :", dq.getRear())

	fmt.Println("inserting element at front end")
	dq.insertFront(13)

	fmt.Println("get front element:", dq.getFront())

	dq.deleteFront()
	fmt.Println("After delete front element new front become :", dq.getFront())
}

Vaqt murakkabligi

Dequening barcha asosiy amallari (old va orqa tomondan kiritish, o'chirish va ko'rish) o'zgarmas vaqt murakkabligiga ega, ya'ni O(1).

Dequening qo'llanilishi

Deque quyidagi maqsadlarda qo'llaniladi:

1. Dasturiy ta'minotlardagi bekor qilish (undo) operatsiyalarida.
2. Veb-brauzerlarda kirilgan sahifalar tarixini (browser history) saqlashda.
3. Ham Stack, ham Queue ma'lumotlar tuzilmalarini amalga oshirishda.