Queues
A queue is a FIFO (First-In, First-Out) data structure in which the
element that is inserted first is the first one to be taken out.
//Enqueue : The process of inserting an element in queue is called enqueue
//Dequeue : The process of deleting an element from queue is called dequeue
[Link] Queue
The elements in a queue are added at one end called the REAR
The elements in a queue are removed from the other end called the FRONT
Queues can be implemented by using either arrays or linked lists
DRAWBACK of Linear Queue:
After inserting elements upto MAX value and deleting some elements from front ,the
REAR end variable stays at last position
It is not possible to insert new elements even though there is space available at front end
Program to implement Linear queue using arrays to perform operations:
[Link] [Link] [Link]
//Implementing Linear queue using arrays
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int front=-1,rear=-1,Q[MAX];
//Function for inserting an element(enqueue)
void enqueue(int x)
{
if(rear==MAX-1)
printf("Queue is overflow\n");
else
{
rear=rear+1;
Q[rear]=x;
if(front==-1)
front=0;
}
}
//Function for deleting an element(dequeue)
void dequeue()
{
if(front==-1)
printf("Queue is underflow i.e; empty\n");
else
{
printf("Deleted value from queue : %d\n",Q[front]);
if(front==rear)
front=rear=-1;
else
front=front+1;
}
}
//Function to display the queue
void display()
{
if(front==-1)
printf("Queue is underflow/empty\n");
else
{
for(int i=front;i<=rear;i++)
printf("%d ",Q[i]);
printf("\n");
}
}
//main function
void main()
{
int choice,x;
while(1)
{
printf("\n----MAIN MENU----\n");
printf("[Link] an element(Enqueue)\n");
printf("[Link] an element(Dequeue)\n");
printf("[Link] queue\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter number to be inserted:");
scanf("%d",&x);
enqueue(x);
break;
case 2: dequeue();
break;
case 3: display();
break;
case 4: printf("Operations going to be terminated terminated\n");
exit(0);
break;
default:printf("Entered invalid choice\n");
break;
}
}
}
Program to implement Linear queue using linked lists to perform
operations:
[Link] [Link] [Link]
//Implementing Linear queue using liked lists
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*front=NULL,*rear=NULL,*temp,*p,*queue=NULL;
//Function for inserting element(Enqueue)
struct node *enqueue(struct node *queue)
{
temp=(struct node*)malloc(sizeof(struct node));
int x;
printf("Enter data to be inserted:");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
if(rear==NULL)
front=rear=temp;
else
{
rear->next=temp;
rear=temp;
}
return queue;
}
//Function for deleting an element(Dequeue)
struct node *dequeue(struct node *queue)
{
if(front==NULL)
printf("Queue is underflow i.e; empty\n");
else if(front->next==NULL)
{
temp=front;
front=rear=NULL;
free(temp);
}
else
{
temp=front;
front=front->next;
temp->next=NULL;
free(temp);
}
return queue;
}
//Function to display the linked queue
struct node *display(struct node *queue)
{
if(front==NULL)
printf("Queue is underflow i.e; empty\n");
else
{
for(p=front;p!=NULL;p=p->next)
{
printf("%d",p->data);
if(p->next!=NULL)
printf(" -> ");
}
}
return queue;
}
//main function
void main()
{
int choice,x;
while(1)
{
printf("\n----MAIN MENU----\n");
printf("[Link] an element(Enqueue)\n");
printf("[Link] an element(Dequeue)\n");
printf("[Link] queue\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: queue=enqueue(queue);
break;
case 2: queue=dequeue(queue);
break;
case 3: queue=display(queue);
break;
case 4: printf("Operations going to be terminated\n");
exit(0);
break;
default:printf("Entered invalid choice\n");
break;
}
}
}
[Link] Queue
Circular Queue is a linear data structure
The rear end is connected to the front end in circular queue
The elements in a queue are added at one end called the REAR
The elements in a queue are removed from the other end called the FRONT
Circular Queue is used to overcome the problem of unutilized space in linear queue
Program to implement Circular queue using arrays to perform
operations:
[Link] [Link] [Link]
//Implenting Circular queue using arrays
#include<stdio.h>
#include<stdlib.h>
#define MAX 7
int front=-1,rear=-1,CQ[MAX];
//Function for inserting an element(enqueue)
void enqueue(int x)
{
if((rear+1)%MAX==front)
printf("Circular Queue is overflow\n");
else
{
rear=(rear+1)%MAX;
CQ[rear]=x;
if(front==-1)
front=0;
}
}
//Function for deleting an element(dequeue)
void dequeue()
{
if(front==-1)
printf("Circular Queue is underflow i.e; empty\n");
else
{
printf("Deleted value from circular queue : %d\n",CQ[front]);
if(front==rear)
front=rear=-1;
else
front=(front+1)%MAX;
}
}
//Function to display the queue
void display()
{
if(front==-1)
printf("Queue is underflow/empty\n");
else if(front<=rear)
{
for(int i=front;i<=rear;i++)
printf("%d ",CQ[i]);
printf("\n");
}
else
{
for(int i=front;i<MAX;i++)
printf("%d ",CQ[i]);
for(int i=0;i<=rear;i++)
printf("%d ",CQ[i]);
printf("\n");
}
}
//main function
void main()
{
int choice,x;
while(1)
{
printf("\n----MAIN MENU----\n");
printf("[Link] an element(Enqueue)\n");
printf("[Link] an element(Dequeue)\n");
printf("[Link] circular queue\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter number to be inserted:");
scanf("%d",&x);
enqueue(x);
break;
case 2: dequeue();
break;
case 3: display();
break;
case 4: printf("Operations going to be terminated\n");
exit(0);
break;
default:printf("Entered invalid choice\n");
break;
}
}
}
[Link]-ended Queue(DEQUE)
A deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted
or deleted at either end.
No element can be added and deleted from the middle.
Types of DEQUES:
[Link] restricted deque
[Link] restricted deque
[Link] restricted deque:
Insertion can be done only at REAR end
Deletion can be done from both FRONT and REAR ends
[Link] restricted deque:
Deletion can be done only at FRONT end
Insertion can be done from both FRONT and REAR ends
Program to implement Double-ended queue using arrays to perform
operations:
[Link] [Link] [Link]
//Implementing Double-Ended Queue(DEQUE) using arrays
#include<stdio.h>
#include<stdlib.h>
#define MAX 7
int front=-1,rear=-1,DQ[MAX];
//Function for inserting an element at rear end
void EnqueueRear(int x)
{
if(rear==MAX-1)
printf("DEQUE is overflow\n");
else
{
rear=rear+1;
DQ[rear]=x;
if(front==-1)
front=0;
}
}
//Function for deleting an element at front end
void DequeueFront()
{
if(front==-1)
printf("DEQUE is underflow i.e; empty\n");
else
{
printf("Deleted value from queue front end: %d\n",DQ[front]);
if(front==rear)
front=rear=-1;
else
front=front+1;
}
}
//Function for inserting an element at front end
void EnqueueFront(int x)
{
if(front<=0)
printf("Not possible to insert an element\n");
else
{
front=front-1;
DQ[front]=x;
}
}
//Function for deleting element at rear end
void DequeueRear()
{
if(front==-1)
printf("DEQUE is underflow i.e; empty\n");
else
{
printf("Deleted value from queue rear end: %d\n",DQ[rear]);
if(rear==front)
front=rear=-1;
else
rear=rear-1;
}
//Function to display the deque
void display()
{
if(front==-1)
printf("DEQUE is underflow i.e; empty\n");
else
{
for(int i=front;i<=rear;i++)
printf("%d ",DQ[i]);
printf("\n");
}
}
//Function to implement input-restricted deque
void input_DQ()
{
int choice,x;
do
{
printf("\n----INPUT RESTRICTED DEQUE----\n");
printf("[Link] an element at rear end\n");
printf("[Link] an element at front end\n");
printf("[Link] an element at rear end\n");
printf("[Link] DEQUE\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter number to be inserted at rear end:");
scanf("%d",&x);
EnqueueRear(x);
break;
case 2: DequeueFront();
break;
case 3: DequeueRear();
break;
case 4: display();
break;
case 5: printf("Exit from i/p restricted operations\n");
break;
default:printf("Entered invalid choice\n");
break;
}
}while(choice!=5);
}
//Function to implement output-restricted deque
void output_DQ()
{
int choice,x;
do
{
printf("\n----OUTPUT RESTRICTED DEQUE----\n");
printf("[Link] an element at front end\n");
printf("[Link] an element at rear end\n");
printf("[Link] an element at front end\n");
printf("[Link] DEQUE\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter number to be inserted at front end:");
scanf("%d",&x);
EnqueueFront(x);
break;
case 2: printf("Enter number to be inserted rear end:");
scanf("%d",&x);
EnqueueRear(x);
break;
case 3: DequeueFront();
break;
case 4: display();
break;
case 5: printf("Exit from o/p restricted operations\n");
break;
default:printf("Entered invalid choice\n");
break;
}
}while(choice!=5);
}
//main function
void main()
{
int choice;
while(1)
{
printf("\n****MAIN MENU****\n");
printf("[Link] restricted DEQUE\n");
printf("[Link] restricted DEQUE\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: input_DQ();
break;
case 2: output_DQ();
break;
case 3: printf("Exit from loop\n");
exit(0);
break;
default:printf("Entered invalid choice\n");
break;
}
}
}