Types Of Queues in data structure

A queue data structure can be classified into the following types:

Circular Queue
Deque
Priority Queue
Multiple Queue

Table of Contents

Circular Queue

In the circular queue, the first index comes right after the last index

The circular queue will be full only when front = 0 and rear = Max – 1. A circular queue is implemented in the same manner as a linear queue is implemented. The only difference will be in the code that performs insertion and deletion operations. For insertion, we now have to check for the following three conditions:

**Inserting an element in a circular queue**

If front = 0 and rear = MAX – 1, then the circular queue is full. Look at the queue given in Fig. 8.16 which illustrates this point
If rear != MAX – 1, then rear will be incremented and the value will be inserted as illustrated in Fig. 8.17
If front != 0 and rear = MAX – 1, then it means that the queue is not full. So, set rear = 0 and insert the new element there, as shown in Fig. 8.18.

Algorithm to insert an element in a circular queue

Step 1: IF FRONT = and Rear = MAX-1
Write OVERFLOW
IF FRONT=-1 and REAR=-1
SET FRONT = REAR =
ELSE IF REAR = MAX-1 and FRONT !=
SET REAR =
ELSE
SET REAR = REAR+1
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT

C program to implement a circular queue

#include <stdio.h>
#include <conio.h>
#define MAX 10
int queue[MAX];
int front=–1, rear=–1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main()
{
int option, val;
clrscr();
do
{
 printf("\n ***** MAIN MENU *****");
 printf("\n 1. Insert an element");
 printf("\n 2. Delete an element");
 printf("\n 3. Peek");
 printf("\n 4. Display the queue");
 printf("\n 5. EXIT");
 printf("\n Enter your option : ");
 scanf("%d", &option);
switch(option)
 {
 case 1:
 insert();
break;
 case 2:
 val = delete_element();
if(val!=–1)

printf("\n The number deleted is : %d", val);
 break;
 case 3:
 val = peek();
if(val!=–1)
printf("\n The first value in queue is : %d", val);
 break;
 case 4:
 display();
break;
 }
}while(option!=5);
getch();
return 0;
}
void insert()
{
int num;
printf("\n Enter the number to be inserted in the queue : ");
scanf("%d", &num);
if(front==0 && rear==MAX–1)
 printf("\n OVERFLOW");
else if(front==–1 && rear==–1)
{
front=rear=0;
 queue[rear]=num;
}
else if(rear==MAX–1 && front!=0)
{
rear=0;
 queue[rear]=num;
}
else
{
 rear++;
 queue[rear]=num;
}
}
int delete_element()
{
int val;
if(front==–1 && rear==–1)
 {
 printf("\n UNDERFLOW");
 return –1;
 }
val = queue[front];
if(front==rear)
 front=rear=–1;
else
{
 if(front==MAX–1)
front=0;
 else
 front++;
}
return val;
}
int peek()
{
if(front==–1 && rear==–1)
{
 printf("\n QUEUE IS EMPTY");
 return –1;

}
else
{
 return queue[front];
}
}
void display()
{
int i;
printf("\n");
if (front ==–1 && rear= =–1)
 printf ("\n QUEUE IS EMPTY");
else
{
 if(front<rear)
 {
 for(i=front;i<=rear;i++)
 printf("\t %d", queue[i]);
 }
 else
 {
 for(i=front;i<MAX;i++)
 printf("\t %d", queue[i]);
for(i=0;i<=rear;i++)
 printf("\t %d", queue[i]);
 }
}
}

Output

***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 25
Enter your option : 2
The number deleted is : 25
Enter your option : 3
QUEUE IS EMPTY
Enter your option : 5

Deques

A deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted or deleted at either end. It is also known as a head-tail linked list because elements can be added to or removed from either the front (head) or the back (tail) end

However, no element can be added and deleted from the middle. In the computer’s memory, a deque is implemented using either a circular array or a circular doubly linked list. In a deque, two pointers are maintained, LEFT and RIGHT, which point to either end of the deque. The elements in a deque extend from the LEFT end to the RIGHT end and since it is circular, Dequeue[N–1] is followed by Dequeue[0]. Consider the deques shown in Fig. 8.24

There are two variants of a double-ended queue. They include

Input restricted deque In this dequeue, insertions can be done only at one of the ends, while deletions can be done from both ends
Output restricted deque In this dequeue, deletions can be done only at one of the ends, while insertions can be done on both ends.

program to implement input and output restricted deques

#include <stdio.h>
#include <conio.h>
#define MAX 10
int deque[MAX];
int left = –1, right = –1;
void input_deque(void);
void output_deque(void);
void insert_left(void);
void insert_right(void);
void delete_left(void);
void delete_right(void);
void display(void);
int main()
{
int option;
clrscr();
printf("\n *****MAIN MENU*****");
printf("\n 1.Input restricted deque");
printf("\n 2.Output restricted deque");
printf("Enter your option : ");
scanf("%d",&option);
switch(option)
{
 case 1:
 input_deque();
break;
 case 2:
 output_deque();
break;
}
return 0;
}
void input_deque()
{
int option;
do
{
 printf("\n INPUT RESTRICTED DEQUE");
 printf("\n 1.Insert at right");
 printf("\n 2.Delete from left");
 printf("\n 3.Delete from right");
 printf("\n 4.Display");
 printf("\n 5.Quit");
 printf("\n Enter your option : ");
 scanf("%d",&option);
switch(option)
 {
 case 1:
 insert_right();
break;
 case 2:
 delete_left();
break;
 case 3:
 delete_right();
break;
 case 4:
 display();
break;
 }
}while(option!=5);

}
void output_deque()
{
int option;
do
{
 printf("OUTPUT RESTRICTED DEQUE");
 printf("\n 1.Insert at right");
 printf("\n 2.Insert at left");
 printf("\n 3.Delete from left");
 printf("\n 4.Display");
 printf("\n 5.Quit");
 printf("\n Enter your option : ");
 scanf("%d",&option);
switch(option)
 {
 case 1:
 insert_right();
break;
 case 2:
 insert_left();
break;
 case 3:
 delete_left();
break;
 case 4:
 display();
break;
 }
}while(option!=5);
}
void insert_right()
{
int val;
printf("\n Enter the value to be added:");
scanf("%d", &val);
if((left == 0 && right == MAX–1) || (left == right+1))
{
 printf("\n OVERFLOW");
 return;
}
if (left == –1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
{
 if(right == MAX–1) /*right is at last position of queue */
right = 0;
 else
 right = right+1;
}
deque[right] = val ;
}
void insert_left()
{
int val;
printf("\n Enter the value to be added:");
scanf("%d", &val);
if((left == 0 && right == MAX–1) || (left == right+1))
{
 printf("\n Overflow");
 return;
}

if (left == –1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
{
if(left == 0)
 left=MAX–1;
 else
 left=left–1;
}
deque[left] = val;
}
void delete_left()
{
if (left == –1)
{
 printf("\n UNDERFLOW");
 return ;
}
printf("\n The deleted element is : %d", deque[left]);
if(left == right) /*Queue has only one element */
{
 left = –1;
 right = –1;
}
else
{
 if(left == MAX–1)
left = 0;
 else
 left = left+1;
}
}
void delete_right()
{
if (left == –1)
{
 printf("\n UNDERFLOW");
 return ;
}
printf("\n The element deleted is : %d", deque[right]);
if(left == right) /*queue has only one element*/
{
 left = –1;
 right = –1;
}
else
{
if(right == 0)
 right=MAX–1;
 else
 right=right–1;
}
}
void display()
{
int front = left, rear = right;
if(front == –1)
{
 printf("\n QUEUE IS EMPTY");
 return;
}
printf("\n The elements of the queue are : ");

if(front <= rear )
{
while(front <= rear)
 {
 printf("%d",deque[front]);
front++;
 }
}
else
{
while(front <= MAX–1)
 {
 printf("%d", deque[front]);
front++;
 }
front = 0;
while(front <= rear)
 {
 printf("%d",deque[front]);
front++;
 }
}
printf("\n");
}