Queue Data structure is a simple algorithm in a data structure which allows to add and remove the element in particular order.

Queue Data structure

What is a Queue in data structure? : Queue is a linear type of data structure similar to the stack Data structure. It follows a particular order in which operations on the Queue are performed. The operations such as adding an element, removing an element or displaying are performed on the queue.

Queue Data structure: Unlike the stack queue data structure is open at both the end. The element is added from one end which is called as the Front end of queue and elements are removed from another end which is referred to as Rear end of the queue.

Queue Definition: Queue is an unordered group of an element in which elements are added at one end (rear end) and removed from one end (front end).
Queue data structure follows FIRST IN FIRST OUT (FIFO) methodology that is the element added first is accessed first.

Queue Data Structure
Queue Data Structure

Queue example
Queue in a ticket counter or line at a bank.

To understand this in a better way let us consider a queue containing 3 elements.

Queue
If we want to add 4 to this queue we can do add rear-end then the queue looks like.

QueueNow, If you want to remove from the queue it should be done from the front that is value 1 is remove first and the front will point the next element in a queue.

Queue

Operation on queue

1. Create (Q):-
This operation is to create an empty queue it is the first step and when we create a queue first step is to assign the Front and Rear value to -1.

2. ENQ (i):-
The ENQ operation in queue means to insert or to add an element of queue. Enqueue always inserts the elements at Rear end of the queue.

3. DEQ (Q):-
The DEQ operation in queue means to delete or remove element from a queue. DEQ removes element of queue from a front end.

4. Empty (Q):-
It checks the queue is empty or not. When queue is empty it returns true otherwise false.

5. Queue size (Q):-
It returns the number of entries (size) of queue.

Note:-
The queue has two pointers Front and Rear.
Element added from Rear end and Removed from the Front end.
The ENQ and DEQ are main two operations of the queue.

Queue Data structure example

Consider queue with size=3 and front = rear = -1.
1. ENQ 10

Queue

2. ENQ 20

Queue

3. ENQ 30

Queue
4. ENQ 40, Now Rear = size-1 that is queue is full.

Queue
5. DEQ 10

Queue

6. DEQ 20

Queue
7. DEQ 30

Queue
If front==end then we reached the end of queue so we again set it to initial stage.
8. DEQ
Now, Front=Rear, So queue will be empty.

Queue algorithm

  1. Set queue Front = End ==-1
  2. Write function ENQ() data to queue
  3. Function to Remove data from queue DEQ()
  4. Function to display queue element.

Flowchart for Queue

Flowchart for Queue Data structure
Flowchart for Queue Data structure

Queue program in c

#include<conio.h>
#include<stdio.h>
#define max 5
int queue[max],front=0,rear=0;
int menu();
void enqueue();
void dequeue();
void display();
void main()
{
int ch;
clrscr();
printf("\n Queues using Arrays\n");
do
{
ch=menu();
switch(ch)
{
case 1: enqueue();
break;
case 2: dequeue();
break;
case 3: display();
break;
case 4: exit();
break;
default:printf("\n Please enter a valid choice!!");
}
}while(1);
}

int menu()
{
int ch;
printf("\n1.ENQUEUE \n2.DEQUEUE \n3.DISPLAY \n4.EXIT");
printf("\nEnter your Choice:");
scanf("%d",&ch);
return ch;
}

void enqueue()
{
int element;
if(rear==max)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter Element:");
scanf("%d",&element);
queue[rear++]=element;
printf("\n %d Enqueued at %d",element,rear);
}

}

void dequeue()
{
if(rear==front)
{
printf("\nUnderflow!!");
}
else
{
front++;
printf("\nElement is Dequeued from %d",front);
}
}
void display()
{
int i;
if(front==rear)
{
printf("\nQueue is Empty!!!");
}
else
{
printf(" \n");
for(i=front;i<max;i++)
{
printf(" | %d ",queue[i]);
}
printf("|");
}
}

Output :

Queue

Complexity of Queue

The time complexity for Queue

The time complexity for Enqueue: When we add an element to Queue we make one movement so time complexity for queue operation is O(1).
The time complexity for Dequeue: When we delete element from Dequeue we make one movement so time complexity for Dequeue operation is O(1).
The worst time complexity for Dequeue: O(n).

Space complexity for Queue:

Worst-case O(n) and best case O(1)

Application of queue

  • In the time-sharing system.
  • In the operating system.

What is the difference between Stack and queue?
The main difference is removing the element. In Stack, we have only one end from which addition and deletion of elements are done whereas queue has two end the one end for addition and another end for deletion. So for implementing stack we require one pointer and queue requires two pointers.

Write A Comment