We observe in the deque diagram above that the "R" denotes movement to the right upon adding an element to the rear, and to the left when removing an element from the rear.
Likewise, the F shifts rightward when a front-end element is deleted and shifts leftward when a new element is added.
Operation on Double Ended Queue:
On the deque data structure, there exist four operations that can be performed.
- Enqueue at the back:
It is beneficial to append an item from the back.
- Remove from the End:
It assists in removing a part from the rear.
- Include Front:
It is beneficial to incorporate an element on the user interface.
- Remove from the Beginning:
It helps to remove a front end element.
We will use a circular array to create the Double Ended Queue.
Add Rear Operation in Deque
If the value of te exceeds the size of the array, the system will show the notification "Queue is full". In the alternative scenario, the value of R will be incremented using the formula R=(R+1)%Size, and the new element will be inserted into the array at the updated position of R. Subsequently, the value of te will be incremented by 1.
In this scenario, the variable te maintains the total count of elements in the array. The te variable increments by 1 when a new element is added and decrements by 1 when an element is removed.
Program:
Let's consider an instance to showcase the append back operation in deque in C++.
#include <stdio.h>
int main() {
int size = 10; // Define the size of the queue
int te = 0;
int R = -1; // Initialize the rear pointer (assuming -1 means empty queue)
int arr[10]; // Define the array to hold the queue elements
int new_item = 42;
if (te == size) {
printf("Queue is full\n");
} else {
R = (R + 1) % size;
arr[R] = new_item;
te = te + 1;
printf("Item %d added to the queue at position %d\n", new_item, R);
}
printf("Queue contents: ");
for (int i = 0; i < te; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Item 10 added to the queue at position 0
Queue contents: 10
Delete Rear Operation in Deque:
If the value of te equals 0, a notification will be shown stating that the queue is currently empty. Otherwise, the program will proceed to verify if the value of R is -1. If R equals -1, the value of R will be set to size minus 1. Subsequently, the updated content will be displayed on the screen, and both R and te will be decremented by 1 after removing the item from the queue.
Program:
Let's consider an example to showcase the remove last operation in deque in C++.
#include <stdio.h>
int main() {
int size = 10;
int te = 0;
int R = -1; // Initialize the rear pointer (assuming -1 means empty queue)
int arr[10]; // Define the array to hold the queue elements
int new_item = 42; // Replace this with the actual item you want to add
if (te == size) {
printf("Queue is full\n");
} else {
R = (R + 1) % size;
arr[R] = new_item;
te = te + 1;
printf("Item %d added to the queue at position %d\n", new_item, R);
}
if (te == 0) {
printf("Queue is empty\n");
} else {
if (R == -1) {
R = size - 1;
}
printf("Number Deleted From Rear End = %d\n", arr[R]);
R = (R - 1 + size) % size;
te = te - 1;
}
printf("Queue contents: ");
for (int i = 0; i < te; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Item 42 added to the queue at position 0
Number Deleted From Rear End = 42
Queue contents:
Add Front Operation in Deque:
When adding an element from the front end, the initial step involves checking if the value of te matches the size of the array. If it doesn't, indicating that the Queue is full, the next check is to determine whether F equals 0. If it does, F is set to size-1; otherwise, it is decremented by 1. Subsequently, the element is inserted into the array at the updated position of element F, followed by incrementing the value of te by 1.
Program:
Let's consider an illustration to showcase the process of adding an element to the front of a deque in C++.
#include <stdio.h>
int main() {
int size = 10; // Define the size of the queue
int te = 0; // Initialize the current number of elements in the queue
int F = 0; // Initialize the fronLogic Practiceer (assuming 0 means empty queue)
int arr[10]; // Define the array to hold the queue elements
// Placeholder for the item you want to add to the queue
int new_item = 42; // Replace this with the actual item you want to add
if (te == size) {
printf("Queue is full\n");
} else {
if (F == 0) {
F = size - 1;
} else {
F = F - 1;
}
arr[F] = new_item;
te = te + 1;
printf("Item %d added to the front end of the queue at position %d\n", new_item, F);
}
// Printing the contents of the queue
printf("Queue contents: ");
for (int i = F; i < F + te; i++) {
printf("%d ", arr[i % size]);
}
printf("\n");
return 0;
}
Output:
Item 42 added to the front end of the queue at position 9
Queue contents: 42
Delete Front Operation in Deque:
When removing an item from the user interface, the initial step involves verifying whether the value of te is equal to 0. If it is, a notification stating "Queue is empty" will be presented. If not, the deleted element will be exhibited on the interface. Subsequently, the value of F is updated using the formula F=(F+1)%Size and then the value of te is decremented by 1.
Program:
Let's consider an example to illustrate the removal of an element from the front of a deque in C++.
#include <stdio.h>
int main() {
int size = 10;
int te = 0;
int F = 0;
int arr[10];
int new_item = 42;
if (te == size) {
printf("Queue is full\n");
} else {
if (F == 0) {
F = size - 1;
} else {
F = F - 1;
}
arr[F] = new_item;
te = te + 1;
printf("Item %d added to the front end of the queue at position %d\n", new_item, F);
}
// Deleting an item from the front end of the queue
if (te == 0) {
printf("Queue is empty\n");
} else {
printf("Number Deleted From Front End = %d\n", arr[F]);
F = (F + 1) % size;
te = te - 1;
}
printf("Queue contents: ");
for (int i = 0; i < te; i++) {
printf("%d ", arr[(F + i) % size]);
}
printf("\n");
return 0;
}
Output:
Item 42 added to the front end of the queue at position 9
Number Deleted From Front End = 42
Queue contents:
A Deque program implementing a circular array:
Here is an example C program implementing a deque using a circular array with a capacity of 7 elements.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 7
struct Deque {
int arr[MAX_SIZE];
int front, rear;
int size;
};
void initDeque(struct Deque *deque) {
deque->front = -1;
deque->rear = -1;
deque->size = 0;
}
// Function to check if the deque is empty
int isEmpty(struct Deque *deque) {
return (deque->size == 0);
}
// Function to check if the deque is full
int isFull(struct Deque *deque) {
return (deque->size == MAX_SIZE);
}
// Function to add an element at the rear
void addRear(struct Deque *deque, int value) {
if (isFull(deque)) {
printf("Deque is full.\n");
} else {
if (deque->front == -1) {
deque->front = 0;
}
deque->rear = (deque->rear + 1) % MAX_SIZE;
deque->arr[deque->rear] = value;
deque->size++;
}
}
// Function to delete an element from the rear
void deleteRear(struct Deque *deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
} else {
printf("Number Deleted From Rear End = %d\n", deque->arr[deque->rear]);
deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
deque->size--;
if (deque->size == 0) {
deque->front = -1;
deque->rear = -1;
}
}
}
// Function to add an element at the front
void addFront(struct Deque *deque, int value) {
if (isFull(deque)) {
printf("Deque is full.\n");
} else {
if (deque->front == -1) {
deque->front = 0;
deque->rear = 0;
} else {
deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
}
deque->arr[deque->front] = value;
deque->size++;
}
}
// Function to delete an element from the front
void deleteFront(struct Deque *deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
} else {
printf("Number Deleted From Front End = %d\n", deque->arr[deque->front]);
deque->front = (deque->front + 1) % MAX_SIZE;
deque->size--;
if (deque->size == 0) {
deque->front = -1;
deque->rear = -1;
}
}
}
// Function to display the elements in the deque
void display(struct Deque *deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
} else {
int i, idx = deque->front;
printf("Deque Elements: ");
for (i = 0; i < deque->size; i++) {
printf("%d ", deque->arr[idx]);
idx = (idx + 1) % MAX_SIZE;
}
printf("\n");
}
}
int main() {
struct Deque deque;
initDeque(&deque);
int choice, value;
for (;;) {
printf("\n1. Add Rear\n");
printf("2. Delete Rear\n");
printf("3. Add Front\n");
printf("4. Delete Front\n");
printf("5. Display\n");
printf("6. Exit\n");
printf("Enter Choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter a number: ");
scanf("%d", &value);
addRear(&deque, value);
break;
case 2:
deleteRear(&deque);
break;
case 3:
printf("Enter a number: ");
scanf("%d", &value);
addFront(&deque, value);
break;
case 4:
deleteFront(&deque);
break;
case 5:
display(&deque);
break;
case 6:
exit(0);
break;
default:
printf("Wrong Choice\n");
}
}
return 0;
}
Output:
Runtime case:
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 1
Enter a number: 10
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 3
Enter a number: 5
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 1
Enter a number: 20
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 5
Deque Elements: 5 10 20
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 2
Number Deleted From Rear End = 20
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 4
Number Deleted From Front End = 5
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 5
Deque Elements: 10
1. Add Rear
2. Delete Rear
3. Add Front
4. Delete Front
5. Display
6. Exit
Enter Choice: 6