Queues in Data Structures

  • A queue is also a list of elements with insertions permitted at one end—called the rear, and deletions permitted from the other end—called the front.
  • This means that the removal of elements from a queue is possible in the same order in which the insertion of elements is made into the queue.
  • Thus, a queue data structure exhibits the FIFO (first in first out) property.
  • People moving on an escalator. The people who got on the escalator first will be the first one to step out of it.
  • People waiting for a bus. The first person standing in the line will be the first one to get into the bus.
  • People standing outside the ticketing window of a cinema hall. The first person in the line will get the ticket first and thus will be the first one to move out of it.
  • Luggage kept on conveyor belts. The bag which was placed first will be the first to come out at the other end.
  • Cars lined at a toll bridge. The first car to reach the bridge will be the first to leave.

Difference between Stack and Queue

Stack Queue
A Linear List Which allows insertion or deletion of an element at one end only is called as Stack A Linear List Which allows insertion atone end and deletion at another end is called as Queue
Since insertion and deletion of an element are performed at one end of the stack, the elements can only be removed in the opposite order of insertion. Since insertion and deletion of an element are performed at opposite end of the queue, the elements can only be removed in the same order of insertion.
Stack is called as Last In First Out (LIFO) List. Queue is called as First In First Out (FIFO) List.
The most and least accessible elements are called as TOP and BOTTOM of the stack Insertion of element is performed at FRONT end and deletion is performed from REAR end
Example of stack is arranging plates in one above one. Example is ordinary queue in provisional store.
Insertion operation is referred as PUSH and deletion operation is referred as POP Insertion operation is referred as ENQUEUE and deletion operation is referred as DQUEUE
Function calling in any languages uses Stack Task Scheduling by Operating System uses queue

Implementation of Queue

Queue can be implemented in two ways : 

  1. Static implementation (using arrays)
  2. Dynamic implementation (using linklist)

Operations on a Queues

The basic operations that can be performed on queue are : 

  • To insert an element in a queue.
  • To delete an element from the queue.

Algorithm to insert an element in a queue

 Step 1: IF REAR = MAX-1
            Write OVERFLOW
            Goto step 4 
         [END OF IF] 
 Step 2: IF FRONT=-1 and REAR=-1
            SET FRONT = REAR = 0
         ELSE
            SET REAR = REAR+1 [END OF IF]
 Step 3: SET QUEUE[REAR] = NUM
 Step 4: EXIT

In this algorithm to insert an element in a queue.

  • In Step 1, we first check for the overflow condition.
  • In Step 2, we check if the queue is empty.
  • In case the queue is empty, then both FRONT and REAR are set to zero, so that the new value can be stored at the 0th location. Otherwise, if the queue already has some values, then REAR is incremented so that it points to the next location in the array.
  • In Step 3, the value is stored in the queue at the location pointed by REAR.

 

Algorithm to delete an element from a queue

 Step 1: IF FRONT = -1 OR FRONT > REAR
            Write UNDERFLOW
         ELSE
            SET VAL = QUEUE[FRONT]
            SET FRONT = FRONT+1
        [END OF IF]
 Step 2: EXIT

In this algorithm to delete an element from a queue.

  • In Step 1, we check for underflow condition. An underflow occurs if FRONT = –1 or FRONT > REAR.
  • However, if queue has some values, then FRONT is incremented so that it now points to the next value in the queue.

 

 Write a program to implement a linear queue. 
#include<stdio.h>
#include<conio.h>
#define MAX 10 // Changing this value will change length of array 
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; 
	do 
​​​​​​​	{
		printf(“\n\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(rear == MAX-1)
		printf(“\n OVERFLOW”);
		else if(front == -1 && rear == -1)
		front = rear = 0;
		else
		rear++;
		queue[rear] = num;
	}
 int delete_element()
	{ 
		int val;
		if(front == -1 || front>rear)
		{
			printf(“\n UNDERFLOW”);
			return -1;
		}
		else
		{
			val = queue[front];
			front++; if(front > rear)
			front = rear = -1;
			return val;
		}
	}
 int peek()
	{
		if(front==-1 || front>rear)
		{ 
			printf(“\n QUEUE IS EMPTY”);
			return -1;
		}
		else
		{ 
			return queue[front];
		}
	}
 void display()
	{ 
		int i;
		printf(“\n”);
		if(front == -1 || front > rear)
			printf(“\n QUEUE IS EMPTY”);
		else
		{ 
			for(i = front;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 : 50

Applications of Queues

  • Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
  • Queues are used to transfer data asynchronously (data not necessarily received at same rate as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets.
  • Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
  • Queues are used in Playlist for jukebox to add songs to the end, play from the front of the list.
  • Queues are used in operating system for handling interrupts. When programming a real-time system that can be interrupted, for example, by a mouse click, it is necessary to process the interrupts immediately, before proceeding with the current job. If the interrupts have to be handled in the order of arrival, then a FIFO queue is the appropriate data structure.

Points to Remember

  • A queue is also a list with insertions permitted from one end, called rear, and deletions permitted from the other end, called front. So it is a data structure that exhibits the FIFO property.
  • The operations that are permitted on a queue are insert and delete.
  • A circular queue is a queue in which the element next to the last element is the first element.
  • When the size of the stack/queue is known beforehand, the array implementation can be used and is more efficient.
  • When the size of the stack/queue is not known beforehand, then the linked representation is used. It provides more flexibility.