Queue
Data structure: Introduction to Queue and it applications.
In the previous topic we talked about stack and its uses before learning about the concepts of queue it is requested as prerequisite to learn or do a quick recap about the concepts of stack. For learning the concepts of queue easily.
link for the concepts of stack :- stack
Above is an example of Queue in real life .
What is Queue ?
Queue is a linear data structure which follows FIFO (first in first out ) methodology( i.e. the element that is stored at the first will leave at first). Unlike stack Queue has two ways , one for insertion (sometimes commonly known as enqueue) and another for deletion (sometimes commonly called dequeue) .
How is Queue Repesented ?
As we had mentioned prior to this that the queue has two end , one for enqueue and the other for dequeue and in the diagram above all the operations along with the pointer variable is given as a visual reference .
Just as we had seen in stack , Queue can also be implemented using both array and linked list .
Some key points about Queue :-
- The FIFO methodology turns the data structure into a real life queue; meaning queue in a ticket counter or in official places.
- Unlike Stack, Queue has two pointer variable rear and front for keeping track of insertion (enqueue) and deletion (dequeue).
- The Queue is an ADT similar to Stack .
- It can be implemented using both (i) Array (ii) Linked list.
- some general conditions are : (i) Underflow condition (ii) Overflow condition
In this condition a variable front and rear is used to keep track of elements or values inserted or deleted ; as the value or element deleting in queue data structure (dequeue) takes place through the front end and insertion of elements (Enqueue) in queue data structure takes place from the rear end.
note : That when using rear and front variable is advisable to initialize the variables using -1 to represent the queue is empty otherwise if it is initialized with 0 the pointer may keep pointing towards the next block , as rear points to the last index of the array.
(ii) Overflow condition: The overflow condititon in queue is (rear = = Max-1), this means the queue is completely filled.
Basic Operations Performed on Queue: :
(i) enqueue: this operation means addition value or elements in the queue. insertion in queue takes place form the rear end. The value will be inserted after checking the queue is full or not (Overflow condition checking). If the array is not full, insert the element by arr[rear] and increase rear by 1. If the array is full, means the overflow condition is met; print "Queue is full".
(ii) dequeue : this operation means to delete value from the queue. deletion in queue takes place form the front end. The value is deleted after checking whether the queue is empty or not (Underflow condition checking).If the array is not empty, then delete the values in the queue by arr[front] and by increasing front by 1. If the array is empty, means the underflow condition is met; print "Queue is empty".
(iii) display: displaying the values present in the queue. Traverse through the queue and print the values.
Implementing Queue using array :
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int sort();
int display();
int Enqueue();
int dequeue();
int a[MAX],front=-1,rear=-1;
int main(void)
{
int ch,n;
while(6)
{
printf("\nEnter 1 for insert\nEnter 2 for delete\nEnter 3 for display\
nEnter 4 for exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter a number\n");
scanf("%d", &n);
Enqueue(n);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("wrong choice\n");
}
}
return 0;
}
int Enqueue(int n)
{
if(rear==MAX-1)
{
printf("Overflow,The queue is full");
}
else
{
if(rear==-1)
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
a[rear]=n;
}
}
int dequeue()
{
if(front==-1)
{
printf("Underflow, the queue is empty");
}
else
{
if (front==rear)
{
printf("The deleted element is %d",a[front]);
front=-1;
rear=-1;
}
else
{
printf("The deleted element is %d",a[front]);
front=front+1;
}
}
}
int display()
{
int i;
if(front!=-1)
{
for (i=front;i<=rear;i++)
{
printf("%d\t",a[i]);
}
}
else
{
printf("underflow,the queue is empty");
}
}
output :-
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
1
Enter a number
10
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
1
Enter a number
20
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
1
Enter a number
30
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
3
10 20 30
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
2
The deleted element is 10
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
2
The deleted element is 20
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
2
The deleted element is 30
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
2
Underflow, the queue is empty
Enter 1 for insert
Enter 2 for delete
Enter 3 for display
Enter 4 for exit
4
… program finished with exit code 0
To run the above code you can use this online code editor link https://onlinegdb.com/HH_olZbaV
you can even edit the code and implement some thing that may come to your mind 😏😇
Implementing queue using linked list : -
We will implementing queue using linked list with the same basic operations mentioned above and implemented with queue using array. While implementing queue using linked list
we will have two pointer type variables front and rear.
code :-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
typedef struct node node;
node *front=NULL;
node *rear=NULL;
int Enqueue();
int dequeue();
int display();
void main(void)
{
int ch,n;
while(6)
{
printf("Enter 1 for Enqueue\nEnter 2 for dequeue\nEnter 3 for display\n
Enter 4 for exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter a number\n");
scanf("%d", &n);
Enqueue(n);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("wrong choice\n");
}
}
}
int Enqueue(int n)
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->info=n;
temp->next=NULL;
if(rear==NULL)
{
rear=temp;
front=temp;
}
else
{
rear->next=temp;
rear=rear->next;
}
}
int dequeue()
{
node*temp;
if(front==NULL)
{
printf("underflow, Queue is empty\n");
}
else
{
if(front->next==NULL)
{
printf(" the deleted value is %d\n",front->info);
front=NULL;
rear=front;
}
else{
printf("the deleted value is %d\n",front->info);
temp=front;
front=front->next;
free(temp);
}
}
}
int display()
{
node*temp=front;
if(front==NULL)
{
exit(0);
}
while(temp!=NULL)
{
printf("%",temp->info);
temp=temp->next;
}
}
output :-
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
1
Enter a number
10
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
1
Enter a number
20
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
1
Enter a number
30
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
1
Enter a number
40
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
3
10 20 30 40
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
2
the deleted value is 10
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
2
the deleted value is 20
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
2
the deleted value is 30
Enter 1 for Enqueue
enter 2 for dequeue
Enter 3 for display
Enter 4 for exit
4
… program finished with exit code 0
link https://onlinegdb.com/fKfOsAebK
you can even edit the code and implement some thing that may come to your mind 😎😇
Comments
Post a Comment