Double ended Queue implementation in C
It is called deque. You can add or delete data in both the ends. It can be implemented by arrays or linked list.
Key terms:
- Front: it represents the first element.
- Rear: it denotes the last element.
Operations:
- Insert the data in front end.
- Delete data in front end.
- Insert the data in rear end.
- Delete the data in rear end.
- Display the elements.
Let us implement the deque in C as follows.
#include <stdio.h>
#define MAX 9
int deque[MAX];
int d_front = -1, d_rear = -1;
void insert_Front(int x) {
if ((d_front == 0
&& d_rear == MAX-1) || (d_front == d_rear+1)) {
printf("Deque is full with data elements.\n");
return;
}
if (d_front == -1)
{
d_front =
d_rear = 0;
} else if (d_front
== 0) {
d_front =
MAX-1;
} else {
d_front--;
}
deque[d_front] =
x;
}
if ((d_front == 0
&& d_rear == MAX-1) || (d_front == d_rear+1)) {
printf("Deque is full.you can't add data\n");
return;
}
if (d_front == -1)
{
d_front =
d_rear = 0;
} else if (d_rear
== MAX-1) {
d_rear = 0;
} else {
d_rear++;
}
deque[d_rear] = x;
}
void delete_Front() {
if (d_front == -1)
{
printf("Deque is empty.No data is found\n");
return;
}
printf("Deleted the element in front: %d\n", deque[d_front]);
if (d_front ==
d_rear) {
d_front =
d_rear = -1;
} else if (d_front
== MAX-1) {
d_front = 0;
} else {
d_front++;
}
}
void delete_Rear() {
if (d_front == -1)
{
printf("Deque is empty.There is no data\n");
return;
}
printf("yes.
The data is Deleted in the Rear: %d\n", deque[d_rear]);
if (d_front ==
d_rear) {
d_front =
d_rear = -1;
} else if (d_rear
== 0) {
d_rear =
MAX-1;
} else {
d_rear--;
}
}
void displayIt() {
if (d_front == -1)
{
printf("Deque is empty\n");
return;
}
int i = d_front;
while (1) {
printf("%d ", deque[i]);
if (i ==
d_rear) break;
i = (i+1) %
MAX;
}
printf("\n");
}
int main() {
insert_Rear(100);
insert_Rear(22);
insert_Front(9);
insert_Front(65);
insert_Rear(90);
displayIt();
delete_Front();
delete_Rear();
displayIt();
return 0;
}
Output:
65 9 100 22 90
Deleted the element in front: 65
yes. The data is Deleted in the Rear: 90
9 100 22
That’s all. The C implementation of deque was done
successfully. It is easy to understand. Keep Coding!!!
Comments
Post a Comment