Double ended queue in C
A deque is an order in which components can be added to or removed from either end (they call it a "deck" or "dequeue"). Since entries can be introduced or eliminated through the top (head) or backside (tail) ends, it is often referred to as a head-tail linked list.
The center, however, cannot have any elements modified or omitted. A deque is performed in the memory of a machine employing either an annular array or a concentric doubly linked list. Two pointer values, LEFT and RIGHT, are kept in a deque and direct attention to the two ends of the deque. An allocated is circular and has elements that stretch from the LEFT end to the RIGHT end. Dequeue[N-1] is followed by Dequeue[0].
A double-ended queue has two variations. They comprise:
- Restricted deque structure entry Only one of the endpoints of this queue can be used for insertions; however, neither can be used for deletions.
- Limited output queue structure Only one of the endpoints of this queue can be used for modifications, whereas the two opposite ends could be used for insertions.
Code:
# include<stdio.h>
# define MAX 5
int darray[MAX];
int l = -1;
int r = -1;
/*Begin of insert_right*/
void insert_right()
{
int added_item;
if((l == 0 && r == MAX-1) || (l == r+1))
{ printf("Queue Overflow\n");
return;}
if (l == -1) /* if queue is initially empty */
{ l = 0;
r=0;
}
/*End of insert_right*/
/*Begin of insert_left*/
void insert_left()
{ int added_item;
if((l == 0 && r == MAX-1) || (l == r+1))
{ printf("Queue Overflow \n");
return; }
if (l== -1)/*If queue is initially empty*/
{ l = 0;
r = 0; }
else
if(l== 0)
l=MAX-1;
else
l=l-1;
printf("Input the element to insert in to the queue : ");
scanf("%d", &added_item);
darray[l] = added_item ; }
/*End of insert_left*/
/*Begin of delete_left*/
void delete_left()
{ if (l == -1)
{ printf("Queue Underflow\n");
return ; }
printf("entity deleted from the queue : %d\n",darray[l]);
if(l == r) /*Queue has only one element */
{ l = -1;
r=-1; }
else
if(l == MAX-1)
l = 0;
else
l = l+1;
}
/*End of delete_left*/
/*Begin of delete_right*/
void delete_right()
{if (l == -1)
{printf("Queue Underflow\n");
return ; }
printf("Element deleted from queue is : %d\n",darray[r]);
if(l == r) /*queue has only one element*/
{ l = -1;
r=-1; }
else
if(r == 0)
r=MAX-1;
else
r=r-1; }
/*End of delete_right*/
/*Begin of input_que*/
void display_queue()
{ int front_pos = l,rear_pos = r;
if(l == -1)
{ printf("Queue is empty\n");
return; }
printf("Queue elements :\n");
if( front_pos <= rear_pos )
{ while(front_pos <= rear_pos)
{ printf("%d ",darray[front_pos]);
front_pos++; } }
else
{ while(front_pos <= MAX-1)
{ printf("%d ",darray[front_pos]);
front_pos++; }
front_pos = 0;
while(front_pos <= rear_pos)
{ printf("%d ",darray[front_pos]);
front_pos++;
}
}
printf("\n");
}
/*End of display_queue*/
/*Begin of input_que*/
void input_que()
{ int choice;
do
{ printf("1.Insert from right\n");
printf("2.Delete from left\n");
printf("3.Delete from right\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{ case 1:
insert_right();
break;
case 2:
delete_left();
break;
case 3:
delete_right();
break;
case 4:
display_queue();
break;
case 5:
break;
default:
printf("Wrong choice\n");
}
}while(choice!=5);
}
/*End of input_que*/
/*Begin of output_que*/
void output_que()
{ int choice;
do
{ printf("1.Insert at right\n");
printf("2.Insert at left\n");
printf("3.Delete from left\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert_right();
break;
case 2:
insert_left();
break;
case 3:
delete_left();
break;
case 4:
display_queue();
break;
case 5:
break;
default:
printf("Wrong choice\n");
}
}while(choice!=5);
}
main()
{
int choice;
printf("1.Input restricted dequeue\n");
printf("2.Output restricted dequeue\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
input_que();
break;
case 2:
output_que();
break;
default:
printf("Wrong choice\n");
}
}
Output:
![Double ended queue in C](https://static.tutorialandexample.com/c/double-ended-queue-in-c1.png)
Applications:
At least two popular approaches for successfully running a deque are using a doubly linked list or an altered dynamic array. The constantly growing array method uses a dynamic array variant known as an array deque, which can expand from the two ends. These collection deques contain all the characteristics of a flexible array, including amortized constant-time insertion and removal at both extremities rather than just one, acceptable localization of reference, and useless insertion and removal in the center. Some popular techniques are as follows:
- Utilizing a revolving buffer to store deque items and only resizing whenever the buffer is full. Thus, resizing happens less frequently.
- Deque elements are allocated from the array's middle, and the array is resized when both ends become available. When pieces are only added at one end, this method may necessitate a greater quantity of scaling and use a more incredible amount of space.
- Accumulating data in several smaller arrays, adding more arrays as necessary at the initial stage or conclusion. A dynamic array that contains references to every single one of the tiny arrays is kept to accomplish indexing.
Complexity:
All deque actions have an O(1) time complexity in a doubly-linked list design and assume neither an allocation nor a deallocation cost. Furthermore, given an iterator, the time complexity of adding or subtracting in the center is O(1), whereas the time complexity of accession at random by the index is O(n).