Mündəricat
Problem bəyanat
“Dairəvi massivdən istifadə edərək Deque-nin tətbiqi” dairəvi massivdən istifadə edərək bir Deque-in aşağıdakı funksiyalarının həyata keçirilməsini xahiş edir (ikiqat sonlu növbə),
- insertFront (x) : Deque'nin ön hissəsinə x elementi daxil edin
- arxa (x) : Deque-nin arxasına x elementi daxil edin
- deleteFront () : Deque'nin ön hissəsindən bir element silin
- deleteRear () : Deque'nin arxasındakı bir elementi silin
- getFront () : Deque'nin ön hissəsindəki elementi qaytarın
- getRear () : Deque'nin arxasındakı elementi qaytarın
- boşdur() : Deque'nin boş olub olmadığına dönün
- isFull () : Deque dolu olub-olmamasına dönün
misal
Input
insertFront (5)
arxa (10)
arxa (11)
insertFront (19)
getFront ()
getRear ()
isFull ()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
boşdur()
Buraxılış
19
11
saxta
10
5
saxta
Dairəvi massivdən istifadə edərək Deque-nin tətbiqi alqoritmi
Həyata keçirmək üçün Nə haqqında dairəvi bir sıra istifadə edərək serialdakı iki göstəricinin ön və arxa hissələrini izləməyimiz lazımdır. Bütün əməliyyatlar bu iki göstərici üzərində olacaq.
Dairəvi massivin mənasını aşağıdakı şəkil ilə başa düşmək olar
Bu şəkildə arxa önün arxasındadır, yəni arxa massivin sonunda idi və massivin başlanğıcında boş boşluqlar var idi, bu səbəbdən arxa tərəfə bir element qoyulması arxanın 0 mövqeyinə gəlməsinə səbəb olardı. , bunun səbəbi dairəvi array dairəvi xarakter daşıyır.
N ölçüsündə bir sıra düzəldin, burada n Deque-nin maksimum ölçüsüdür və Deque-də hər hansı bir əməliyyatdan əvvəl ön və arxa hissəni -1 olaraq işə salın.
Array dairəvi artım şəklində olduqda, massivin sonunda olduqda onları başlanğıc nöqtəsinə aparacaq və başlanğıc nöqtəsində olduqda ön və arxa hissəni azaldaraq onları sonuna aparacaqlar. array.
insertFront (x)
- Dizi doludursa, element daxil edilə bilməz.
- Deque-də (və ya massivdə) heç bir element yoxdursa, yəni ön bərabərdir -1, ön və arxa artırın və arr [front] -i x olaraq təyin edin.
- Başqa azalma cəbhəsi və arr [ön] x olaraq qoyulur.
Zamanın mürəkkəbliyi = O (1)
insertRear ()
- Dizi doludursa, element daxil edilə bilməz.
- Deque-də heç bir element yoxdursa, yəni arxa -1-ə bərabərdirsə, ön və arxa tərəfi artırın və arr [arxa] nı x olaraq təyin edin.
- Else artımı arxa və arr [arxa] nı x olaraq təyin edin.
Zaman Mürəkkəbliyi = O (1)
deleteFront ()
- Deque boşdursa, geri qayıdın.
- Deque-də yalnız bir element varsa, yəni ön arxaya bərabərdirsə, ön və arxanı -1 olaraq təyin edin.
- Öndə başqa 1 artım.
Zaman Mürəkkəbliyi = O (1)
deleteRear ()
- Deque boşdursa, geri qayıdın.
- Deque-də yalnız bir element varsa, yəni arxa önə bərabərdirsə, ön və arxanı -1 olaraq təyin edin.
- Digər arxada 1 azalma.
Zaman Mürəkkəbliyi = O (1)
getFront ()
- Deque boşdursa, geri qayıdın.
- Else return arr [ön].
Zaman Mürəkkəbliyi = O (1)
getRear ()
- Deque boşdursa, geri qayıdın.
- Else return arr [arxa].
Zaman Mürəkkəbliyi = O (1)
boşdur()
Cəbhəsi -1-ə bərabərdirsə, Deque boşdur, əks halda deyil.
Zaman Mürəkkəbliyi = O (1)
isFull ()
Əgər (arxa + 1)% n önə bərabərdirsə, Deque doludur, əksinə deyil. Burada n Deque'nin maksimum ölçüsüdür.
Zaman Mürəkkəbliyi = O (1)
Dairəvi massivdən istifadə edərək Deque-nin tətbiqi üçün Java kodu
class ImplementationOfDequeUsingCircularArray {
// Maximum size of Deque
private static final int MAX_SIZE = 100;
// Array to implement Deque
private static int deque[];
// Variables to represent front and rear of dequeue
private static int front = -1;
private static int rear = -1;
private static void insertFront(int x) {
// if array is not full
if (!isFull()) {
// case 1 : there are no elements
// increment front and rear and add element at arr[front]
if (front == -1) {
front = rear = 0;
deque[front] = x;
}
// else, decrement front circularly and add the
// new element at arr[front]
else {
if (front == 0) {
front = MAX_SIZE - 1;
} else {
front--;
}
deque[front] = x;
}
}
}
private static void insertRear(int x) {
// if array is not full
if (!isFull()) {
// if this is the first element to be inserted
// increment front and rear and add element at arr[rear]
if (rear == -1) {
front = rear = 0;
deque[rear] = x;
}
// else increment rear circularly and add
// new element at arr[rear]
else {
if (rear == MAX_SIZE - 1) {
rear = 0;
} else {
rear++;
}
deque[rear] = x;
}
}
}
private static void deleteFront() {
// if array is not empty
if (!isEmpty()) {
// if there is only 1 element
// make front and rear as -1
if (front == rear) {
front = rear = -1;
}
// else increment front circularly
else {
if (front == MAX_SIZE - 1) {
front = 0;
} else {
front++;
}
}
}
}
private static void deleteRear() {
// if array is not empty
if (!isEmpty()) {
// if there is only 1 element
// make front and rear as -1
if (front == rear) {
rear = front = -1;
}
// else decrement rear circularly
else {
if (rear == 0) {
rear = MAX_SIZE - 1;
} else {
rear--;
}
}
}
}
private static int getFront() {
// if array is not empty return arr[front]
if (!isEmpty()) {
return deque[front];
}
return -1;
}
private static int getRear() {
// if array is not empty return arr[rear]
if (!isEmpty()) {
return deque[rear];
}
return -1;
}
private static boolean isEmpty() {
// if front is -1 then deque is empty
if (front == -1) {
return true;
}
return false;
}
private static boolean isFull() {
// if front is 1 ahead of rear then
// deque is full
if ((rear + 1) % MAX_SIZE == front) {
return true;
}
return false;
}
public static void main(String[] args) {
deque = new int[MAX_SIZE];
// Example
insertFront(5);
insertRear(10);
insertRear(11);
insertFront(19);
System.out.println(getFront());
System.out.println(getRear());
System.out.println(isFull());
deleteRear();
System.out.println(getRear());
deleteFront();
System.out.println(getFront());
System.out.println(isEmpty());
}
}
19 11 false 10 5 false
C ++ dairəvi massivdən istifadə edərək Deque tətbiqetmə qaydası
#include <iostream>
using namespace std;
// Maximum size of Deque
const int MAX_SIZE = 100;
// Array to implement Deque
int deque[MAX_SIZE];
// Variables to represent front and rear of dequeue
int front = -1;
int rear = -1;
bool isEmpty() {
// if front is -1 then deque is empty
if (front == -1) {
return true;
}
return false;
}
bool isFull() {
// if front is 1 ahead of rear then
// deque is full
if ((rear + 1) % MAX_SIZE == front) {
return true;
}
return false;
}
void insertFront(int x) {
// if array is not full
if (!isFull()) {
// case 1 : there are no elements
// increment front and rear and add element at arr[front]
if (front == -1) {
front = rear = 0;
deque[front] = x;
}
// else, decrement front circularly and add the
// new element at arr[front]
else {
if (front == 0) {
front = MAX_SIZE - 1;
} else {
front--;
}
deque[front] = x;
}
}
}
void insertRear(int x) {
// if array is not full
if (!isFull()) {
// if this is the first element to be inserted
// increment front and rear and add element at arr[rear]
if (rear == -1) {
front = rear = 0;
deque[rear] = x;
}
// else increment rear circularly and add
// new element at arr[rear]
else {
if (rear == MAX_SIZE - 1) {
rear = 0;
} else {
rear++;
}
deque[rear] = x;
}
}
}
void deleteFront() {
// if array is not empty
if (!isEmpty()) {
// if there is only 1 element
// make front and rear as -1
if (front == rear) {
front = rear = -1;
}
// else increment front circularly
else {
if (front == MAX_SIZE - 1) {
front = 0;
} else {
front++;
}
}
}
}
void deleteRear() {
// if array is not empty
if (!isEmpty()) {
// if there is only 1 element
// make front and rear as -1
if (front == rear) {
front = rear = -1;
}
// else decrement rear circularly
else {
if (rear == 0) {
rear = MAX_SIZE - 1;
} else {
rear--;
}
}
}
}
int getFront() {
// if array is not empty return arr[front]
if (!isEmpty()) {
return deque[front];
}
return -1;
}
int getRear() {
// if array is not empty return arr[rear]
if (!isEmpty()) {
return deque[rear];
}
return -1;
}
int main() {
// Example
insertFront(5);
insertRear(10);
insertRear(11);
insertFront(19);
cout<<getFront()<<endl;
cout<<getRear()<<endl;
if (isFull()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
deleteRear();
cout<<getRear()<<endl;
deleteFront();
cout<<getFront()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
19 11 false 10 5 false
