Queue & Circular Queue
Queue
Queue is
also an abstract data type or a linear data structure, just like stack
data structure, in which the first element is inserted from one end
called the REAR(also called tail), and the removal of
existing element takes place from the other end called as FRONT(also
called head).
This makes queue as FIFO(First
in First Out) data structure, which means that element inserted first will be
removed first.
Which is exactly how queue system works in
real world. If you go to a ticket counter to buy movie tickets, and are first
in the queue, then you will be the first one to get the tickets. Right? Same is
the case with Queue data structure. Data inserted first, will leave the queue
first.
The process to add an element into queue
is called Enqueue and the process of removal of an element
from queue is called Dequeue.
Basic features of Queue
1. Like stack, queue is also an ordered list of elements
of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the
elements inserted before the new element in the queue must be removed, to
remove the new element.
4. peek( ) function
is oftenly used to return the value of first element without dequeuing it.
Applications of Queue
Queue, as the name suggests is used
whenever we need to manage any group of objects in an order in which the first
one coming in, also gets out first while the others wait for their turn, like
in the following scenarios:
1. Serving requests on a single shared resource, like a
printer, CPU task scheduling etc.
2. In real life scenario, Call Center phone systems uses
Queues to hold people calling them in an order, until a service representative
is free.
3. Handling of interrupts in real-time systems. The
interrupts are handled in the same order as they arrive i.e First come first
served.
Implementation of Queue Data Structure
Queue can be implemented using an Array,
Stack or Linked List. The easiest way of implementing a queue is by using an
Array.
Initially the head(FRONT) and
the tail(REAR) of the queue points at the first index of the array
(starting the index of array from 0). As we add elements to
the queue, the tail keeps on moving ahead, always pointing to
the position where the next element will be inserted, while the head remains
at the first index.
When we remove an element from Queue, we
can follow two possible approaches (mentioned [A] and [B] in above diagram). In
[A] approach, we remove the element at head position, and then
one by one shift all the other elements in forward position.
In approach [B] we remove the element
from head position and then move head to the
next position.
In approach [A] there is an overhead
of shifting the elements one position forward every time we remove the
first element.
In approach [B] there is no such overhead,
but whenever we move head one position ahead, after removal of first element,
the size on Queue is reduced by one space each time.
Algorithm for ENQUEUE operation
1. Check if the queue is full or not.
2. If the queue is full, then print overflow error and
exit the program.
3. If the queue is not full, then increment the tail and
add the element.
Algorithm for DEQUEUE operation
1. Check if the queue is empty or not.
2. If the queue is empty, then print underflow error and
exit the program.
3. If the queue is not empty, then print the element at
the head and increment the head.
Circular queue
It avoids the wastage of space in a
regular queue implementation using array
As you can see in the above image,
after a bit of enqueueing and dequeueing, the size of the queue has been reduced.
The indexes 0 and 1 can only be used
after the queue is reset when all the elements have been dequeued.
How Circular
Queue Works
Circular Queue works by the process
of circular increment i.e. when we try to increment any variable and we reach
the end of queue, we start from the beginning of queue by modulo division with
the queue size.i.e.
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Queue operations work as follows:
- Two
pointers called FRONT and REAR are
used to keep track of the first and last elements in the queue.
- When
initializing the queue, we set the value of FRONT and REAR to
-1.
- On
enqueing an element, we circularly increase the value of REAR index
and place the new element in the position pointed to by REAR.
- On
dequeueing an element, we return the value pointed to by FRONT and
circularly increase the FRONT index.
- Before
enqueing, we check if queue is already full.
- Before
dequeuing, we check if queue is already empty.
- When
enqueing the first element, we set the value of FRONT to
0.
- When
dequeing the last element, we reset the values of FRONT and REAR to
-1.
However, the check for full queue has
a new additional case:
- Case 1: FRONT =
0 &&
REAR == SIZE - 1 - Case 2:
FRONT = REAR + 1
The second case happens when REAR starts
from 0 due to circular increment and when its value is just 1 less than FRONT,
the queue is full.
Implementation using C
programming
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
int isFull()
{
if( (front == rear + 1) || (front == 0 && rear ==
SIZE-1)) return 1;
return 0;
}
int isEmpty()
{
if(front == -1) return 1;
return 0;
}
void enQueue(int element)
{
if(isFull()) printf("\n Queue is full!! \n");
else
{
if(front ==
-1) front =
0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
int deQueue()
{
int element;
if(isEmpty()) {
printf("\n Queue is empty !! \n");
return(-1);
}
else {
element = items[front];
if (front ==
rear){
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after
dequeing it. ? */
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d
\n", element);
return(element);
}
}
void display()
{
int i;
if(isEmpty()) printf(" \n Empty Queue\n");
else
{
printf("\n Front -> %d ",front);
printf("\n Items -> ");
for( i =
front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
printf("\n Rear -> %d \n",rear);
}
}
int main()
{
// Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0;
}
When you run this program, the output will be
Queue is empty
Inserted 1
Inserted 2
Inserted 3
Inserted 4
Inserted 5
Queue is full
Front -> 0
Items -> 12345
Rear -> 4
Deleted Element is 1
Front -> 1
Items -> 2345
Rear -> 4
Inserted 7
Front -> 1
Items -> 23457
Rear -> 0
Queue is full
