In this lesson we’ll learn about Data Structures and look at the Queue Data structure which follows FIFO approach.

Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed.

Elements are always added to the back and removed from the front. Think of it as a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.

Variables used

• queue[]queue[]: Array in which queue is simulated
• arraySizearraySize: Maximum number of elements that can be stored in a queue[]queue[]
• frontfront: Points at the index where the next deletion will be performed
• rearrear: Points at the index where the next insertion will be performed

Functions supported

Queues support the following fundamental functions:

Enqueue

If the queue is not full, this function adds an element to the back of the queue, else it prints “OverFlow”.

void enqueue(int queue[], int element, int& rear, int arraySize) {
   if(rear == arraySize)            // Queue is full
           printf(“OverFlow\n”);
   else{
        queue[rear] = element;    // Add the element to the back
        rear++;
   }
}

Dequeue

If the queue is not empty, this function removes the element from the front of the queue, else it prints “UnderFlow”.

void dequeue(int queue[], int& front, int rear) {
   if(front == rear)            // Queue is empty
       printf(“UnderFlow\n”);
   else {
       queue[front] = 0;        // Delete the front element
       front++;
   }
}

Front

This function returns the front element of the queue.

int Front(int queue[], int front) {
   return queue[front];
}

Support functions

Size

This function returns the size of a queue or the number of elements in a queue.

int size(int front, int rear) {
   return (rear - front);
}

IsEmpty

If a queue is empty, this function returns 'true', else it returns 'false'.

bool isEmpty(int front, int rear) {
   return (front == rear);
}

Example

Let us try a problem.

You are given a string. Take the first character of the string and put it at the end of the string.

Find out what the string will be after NN steps.

The string can be considered as a queue. At each step, dequeue the character from the front and enqueue it at the end. Repeat this process NN times.

Let us code this problem.

#include <iostream>
#include <cstdio>

using namespace std;

void enqueue(char queue[], char element, int& rear, int arraySize) {
   if(rear == arraySize)            // Queue is full
       printf("OverFlow\n");
   else {
       queue[rear] = element;    // Add the element to the back
       rear++;
   }
}


void dequeue(char queue[], int& front, int rear) {
   if(front == rear)            // Queue is empty
       printf("UnderFlow\n");
   else {
       queue[front] = 0;        // Delete the front element
       front++;
   }
}

char Front(char queue[], int front) {
   return queue[front];
}


int main() {
   char queue[20] = {'a', 'b', 'c', 'd'};        
   int front = 0, rear = 4;                
   int arraySize = 20;                // Size of the array
   int N = 3;                    // Number of steps
   char ch;
   for(int i = 0;i < N;++i) {
       ch = Front(queue, front);
       enqueue(queue, ch, rear, arraySize);
       dequeue(queue, front, rear);
   }
   for(int i = front;i < rear;++i)
       printf("%c", queue[i]);
   printf("\n");
   return 0;
}

Output

dabc

Queue variations

The standard queue data structure has the following variations:

1. Double-ended queue
2. Circular queue

Double-ended queue

In a standard queue, a character is inserted at the back and deleted in the front. However, in a double-ended queue, characters can be inserted and deleted from both the front and back of the queue.

Functions supported

The following functions are supported by double-ended queues:

Insert at back

void insert_at_back(int queue[], int element, int &rear, int array_size){
   if(rear == array_size)
       printf("Overflow\n");
   else{
       queue[rear] = element;
       rear = rear + 1;
   }
}

Delete from back

void delete_from_back(int queue[], int &rear, int front){
   if(front == rear)
       printf("Underflow\n");
   else{
       rear = rear - 1;
       queue[rear] = 0;
   }
}

Insert at front

void insert_at_front(int queue[], int &rear, int &front, int element, int array_size){
   if(rear == array_size)
       printf("Overflow\n");
   else{
       for(int i=rear; i>front; i--)
           queue[i] = queue[i-1];
       queue[front] = element;
       rear = rear+1;
   }
}

Delete from front

void delete_front_front(int queue[], int &front, int &rear){
   if(front == rear)
       printf("Underflow\n");
   else{
       queue[front] = 0;
       front = front + 1;
   }
}

Get front element

int get_front(int queue[], int front){
   return queue[front];
}

Get rear element

int get_rear(int queue[], int rear){
   return queue[rear-1];
}

Support functions

Size and IsEmpty are implemented in the same way as in a standard queue.

Circular queues

A circular queue is an improvement over the standard queue structure. In a standard queue, when an element is deleted, the vacant space is not reutilized. However, in a circular queue, vacant spaces are reutilized.

While inserting elements, when you reach the end of an array and you need to insert another element, you must insert that element at the beginning (given that the first element has been deleted and the space is vacant).

Variables used

In addition to all the variables that are used in a standard queue, circular queues support the following variable:

countcount: Number of elements present in a queue

Functions supported

Circular queues support all the functions that are supported by standard queues, however, there is a difference in the implementation of these functions.

Enqueue

void enqueue(int queue[], int element, int& rear, int arraySize, int& count) {
   if(count == arraySize)            // Queue is full
           printf(“OverFlow\n”);
   else{
       queue[rear] = element;
       rear = (rear + 1)%arraySize;
       count = count + 1;
   }
}

Dequeue

void dequeue(int queue[], int& front, int rear, int& count) {
   if(count == 0)            // Queue is empty
       printf(“UnderFlow\n”);
   else {
       queue[front] = 0;        // Delete the front element
       front = (front + 1)%arraySize;
       count = count - 1;
   }
}

Front

int Front(int queue[], int front) {
   return queue[front];
}

Size

int size(int count) {
   return count;
}

IsEmpty

bool isEmpty(int count) {
   return (count == 0);
}

Application of Queue

• When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
• When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
• Queue is used in BFS(Breadth First Search) algorithm. It helps in traversing a tree or graph.
• Queue is also used by Operating systems for job scheduling.
• Queue is used in networking to handle congestion.