I hope we all have been in a line to pick our order at the cafe or restaurant. Technically, that line is a queue. Who will be served first? The one first in the queue or the later one? Well yes, the first one of course! What do you observe in a queue? First come First served. Those who come first will leave first. With this analogy, we shall continue to our topic.
Principle or Strategy:
As discussed, First In First Out (FIFO, commonly referred) is the strategy used in a queue unlike stack that uses LIFO. We will now understand some of the terms related to a queue.
In C or C++ programming language, we create an array of size n to store elements and show the working of a queue. We have collections in Java and modules in Python to implement but abstracting the working of queue.
Front: It represents the elements or values from the beginning of a queue. Elements are deleted from the front.
Rear: It represents the elements or values from the end of a queue. Elements are inserted at the end of the queue.
Enqueue: To the created queue, we have to insert the elements to it. The process is known as enqueuing.
Dequeue/pop: We delete the elements from the front of the queue, as it uses FIFO. The process is dequeuing.
Display: It is used to display all the elements of a queue.
Algorithm
Step 1: Create an array, say queue, of size n
Step 2: Define two variables front and rear and initialize them to -1. These point to the first and last elements of the queue.
Step 3: Perform the operations on queue (array) with a menu listed.
Enqueue:
Step 1: Check whether queue is full. (rear = n-1)
Step 2: If queue is full, print that elements cannot be inserted.
Step 3: If queue isn't full, increase the value of rear by 1 and queue[rear]=value_to_be_inserted
Dequeue:
Step 1: Check if the queue is empty. (front=rear)
Step 2: If queue is empty, print that deletion cannot be performed on the queue.
Step 3: If queue isn't empty, then increment the front value by one (front ++). Then display queue[front] as deleted element.
Step 4: Check if both front and rear are equal (front == rear), if TRUE, then set both front and rear to '-1'
(front = rear = -1).
Peek:
Step 1: Check if queue is empty. (front=rear)
Step 2: If queue is empty, print that there are no elements to display.
Step 3: If queue isn't empty, print the value at front, queue[front].
Notations
MAX ← size of the array
queue ← array created
i ← variable
front ← points to the start of the array
rear ← points to the end of the array
Implementation in C
#include<stdio.h>
#include<stdlib.h>
#define MAX 50
void enqueue();
void dequeue();
void display();
int queue[MAX];
int rear=-1,front=-1;
main(){
int ch,ch1;
choice:
printf("\n Enter your choice:");
printf("\n 1.Insert 2.Display 3.Delete 4.Exit");
scanf("%d",&ch);
if(ch==1){
enqueue();
choice1:
printf("\n Do you wish to continue?");
printf("\n 1.Yes 2.No");
scanf("%d",&ch1);
if(ch1==1)
goto choice;
else if(ch1==2)
printf("\n Program terminated!");
else{
printf("\n Invalid Choice");
goto choice1;
}
}
else if(ch==2){
display();
goto choice1;
}
else if(ch==3){
dequeue();
goto choice1;
}
else if(ch==4)
printf("\n Program terminated!");
else{
printf("\n Invalid Choice");
goto choice;
}
}
void enqueue(){
int value;
if(rear==MAX-1)
printf("Queue overflow");
else{
if(front==-1)
front=0;
printf("\n Insert the element");
scanf("%d",&value);
rear=rear+1;
queue[rear]=value;
}
}
void dequeue(){
if(front==-1 || front>rear){
printf("\n Queue Underflow");
return;
}
else{
printf("\n Element deleted from the queue is %d",queue[front]);
front=front+1;
}
}
void display(){
int i;
if(front==-1)
printf("\n Queue is Empty");
else{
printf("\n Queue is:");
for(i=front;i<=rear;i++)
printf("%d ",queue[i]);
printf("\n ");
}
}
The further implementations include Priority Queue and Double-ended Queue. The concepts will follow the lead. Till then, consider viewing our catalog!
Techprodezza 