lOMoARcPSD|13574892
QUEUE
A queue is linear data structure and collection of elements. A queue is another special kind of list, where
items are inserted at one end called the rear and deleted at the other end called the front. The principle of
queue is a “FIFO” or “First-in-first-out”.
Queue is an abstract data structure. A queue is a useful data structure in programming. It is similar to the
ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the
ticket.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first.
More real-world examples can be seen as queues at the ticket windows and bus-stops and our college
library.
The operations for a queue are analogues to those for a stack; the difference is that the insertions go at the
end of the list, rather than the beginning.
Operations on QUEUE:
A queue is an object or more specifically an abstract data structure (ADT) that allows the following
operations:
• Enqueue or insertion: which inserts an element at the end of the queue.
• Dequeue or deletion: which deletes an element at the start of the queue.
Representation of Queue (or) Implementation of Queue:
The queue can be represented in two ways:
1. Queue using Array
2. Queue using Linked List
[Link] using Array:
Let us consider a queue, which can hold maximum of five elements. Initially the queue is empty.
Now, insert 11 to the queue. Then queue status will be:
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
Next, insert 22 to the queue. Then the queue status is:
Again insert another element 33 to the queue. The status of the queue is:
Now, delete an element. The element deleted is the element at the front of the [Link] the status of
the queue is:
Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So,
22 is deleted. The queue status is as follows:
Now, insert new elements 44 and 55 into the queue. The queue status is:
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the
rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The
queue status is as follows:
Now it is not possible to insert an element 66 even though there are two vacant positions in
the linear queue. To overcome this problem the elements of the queue are to be shifted
towards the beginning of the queue so that it creates vacant position at the rear end. Then
the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the
rear end. After this operation, the queue status is as follows:
This difficulty can overcome if we treat queue position with index 0 as a position that comes
after position with index 4 i.e., we treat the queue as a circular queue.
Algorithm to insert any element in a queue
Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error
If the item is to be inserted as the first element in the list, in that case set the value of front and
rear to 0 and insert the element at the rear end.
Otherwise keep increasing the value of rear and insert each element one by one having rear as
the index.
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
Algorithm to delete an element from the queue
If, the value of front is -1 or value of front is greater than rear , write an underflow message and
exit.
Otherwise, keep increasing the value of front and return the item stored at the front end of the
queue at each time.
display() - Displays the elements of a Queue
We can use the following steps to display the elements of a queue...
• Step 1 - Check whether queue is EMPTY.
• Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
• Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
• Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value reaches to rear (i <= rear)
Queue Implementation using Arrays
#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
printf("\n*************************Main
Menu*****************************\n");
printf("\n==============================================================
===\n");
printf("\[Link] an element\[Link] an element\[Link] the queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
queue[rear] = item;
printf("\nValue inserted ");
}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}
void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
Drawback of array implementation of Queue
Although, the technique of creating a queue is easy, but there are some drawbacks of using this
technique to implement a queue.
o Memory wastage : The space of the array, which is used to store queue elements, can
never be reused to store the elements of that queue because the elements can only be
inserted at front end and the value of front might be so high so that, all the space before
that, can never be filled.
The above figure shows how the memory space is wasted in the array representation of queue. In
the above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable
is 5, therefore, we can not reinsert the values in the place of already deleted element before the
position of front. That much space of the array is wasted and can not be used in the future (for
this queue).
o Deciding the array size
One of the most common problem with array implementation is the size of the array which
requires to be declared in advance. Due to the fact that, the queue can be extended at runtime
depending upon the problem, the extension in the array size is a time taking process and almost
impossible to be performed at runtime since a lot of reallocations take place. Due to this reason,
we can declare the array large enough so that we can store queue elements as enough as possible
but the main problem with this declaration is that, most of the array slots (nearly half) can never
be reused. It will again lead to memory wastage.
Types of Queues
There are four types of Queues:
1. Linear Queue
2. Circular Queue
3. Priority Queue
4. Deque
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
1. Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as front end. It strictly follows the FIFO rule. The linear Queue can
be represented, as shown in the below
figure:
The above figure shows that the elements are inserted from the rear end, and if we insert more
elements in a Queue, then the rear value gets incremented on every insertion. If we want to show
the deletion, then it can be represented as:
In the above figure, we can observe that the front pointer points to the next element, and the
element which was previously pointed by the front pointer was deleted.
The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even though
the space is available in a Linear Queue. In this case, the linear Queue shows
the overflow condition as the rear is pointing to the last element of the Queue.
Downloaded by [Link] Verma S (kishore.saj3@[Link])
lOMoARcPSD|13574892
2. Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known
as Ring Buffer as all the ends are connected to another end. The circular queue can be
represented as:
he drawback that occurs in a linear queue is overcome by using the circular queue. If the empty
space is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear.
3. Priority Queue
A priority queue is another special type of Queue data structure in which each element has some
priority associated with it. Based on the priority of the element, the elements are arranged in a
priority queue. If the elements occur with the same priority, then they are served according to the
FIFO principle.
In priority Queue, the insertion takes place based on the arrival while the deletion occurs based
on the priority. The priority Queue can be shown as:
The above figure shows that the highest priority element comes first and the elements of the
same priority are arranged based on FIFO structure.
4. Deque
Both the Linear Queue and Deque are different as the linear queue follows the FIFO principle
whereas, deque does not follow the FIFO principle. In Deque, the insertion and deletion can occur
from both ends.
Downloaded by [Link] Verma S (kishore.saj3@[Link])