Queue Data Structure

Queue is an linear data structure which follows the First In First Out (FIFO) principle.

Simple Queue Application

In a bank, people are standing in the queue. The person who stands first in the line will be served first.

Similarly, the person who stands last in the line will be served at the end.

This is the simplest example of First In First Out (FIFO) principle.

Let's implement the queue data structure using array

Requirements

Array

int arr[size];

To point the front and rear element of the queue

int front;
int rear;

isQueueFull()

This function will return true(1) if the queue is full.

Otherwise, it will return false(0).

int isQueueFull();

enqueue(data)

enqueue function will add the element at the end of the queue.

Example

enqueue(1). queue[] = {1}

enqueue(20). queue[] = {1,20}

enqueue(30). queue[] = {1,20,30}

Let's take an integer data.

void enqueue(int);

isQueueEmpty()

This function will return true(1) if the queue is empty.

Otherwise, it will return false(0).

int isQueueEmpty();

dequeue()

dequeue function will remove the element from the front of the queue.

Example

Existing queue[] = {1,20,30}

dequeue(). queue[] = {20,30}. Removed element = 1

dequeue(). queue[] = {30}. Removed element = 20

void dequeue();

Let's Initialize the variables

we are going to initialize front and rear as 0.

front = 0 and rear = 0 indicates the empty queue.

Let's assume the array size as 5.

enqueue

To enqueue the data,

Check if the queue is full.

If its full

we can't insert data.

Otherwise

insert the data in arr[rear] and increment the rear variable by 1.

Example

i) enqueue 10

ii) enqueue 20

iii) enqueue 30

iv) enqueue 40

v) enqueue 50

vi) enqueue 60

The queue is full when rear == size.

enqueue function

/*
 * It will check whether the queue if full or not
 * return 1, if the queue is full
 * return -1, otherwise
 */
int isQueueFull()
{
    if(rear == size)
        return 1;
    return -1;
}

//adds element at the end of the queue
void enqueue(int val)
{
    if(isQueueFull() == 1)
        printf("Queue is Full\n");
    else
    {
        arr[rear] = val;
        rear++;
    }
}

dequeue

To dequeue element from the queue,

Check if the queue is empty

if it's empty

We can't dequeue an element from the empty queue.

Otherwise

Print/return arr[front] and increment the front by 1.

Example

i) dequeue

ii) dequeue

iii) dequeue

iv) dequeue

v) dequeue

vi) dequeue

The queue is empty when front == rear.

dequeue function

/*
  * It will check whether the queue is empty or not
  * return 1, if the queue is empty
  * return -1, otherwise
  */
 int isQueueEmpty()
 {
     if(front == rear)
         return 1;
     return -1;
 }

 //removes the current beginning element from the queue.
 void dequeue()
 {
     if(isQueueEmpty() == 1)
         printf("Queue is Empty.\n");
     else
     {
         printf("Dequeued element = %d\n",arr[front]);
         front++;
     }
 }

Implementation of the queue data structure using array

Example

/*
 * Program  : Queue data structure using array
 * Language : C
 */

#include<stdio.h>

//size of the queue
#define size 5

int arr[size];

/*
 * intialize front and rear as 0
 * which indicates that the queue is empty initially.
 */
int front  = 0;
int rear   = 0;

/*
 * It will check whether the queue is empty or not
 * return 1, if the queue is empty
 * return -1, otherwise
 */
int isQueueEmpty()
{
   if(front == rear)
       return 1;
   return -1;
}

//removes the current beginning element from the queue.
void dequeue()
{
   if(isQueueEmpty() == 1)
       printf("Queue is Empty.\n");
   else
   {
       printf("Dequeued element = %d\n",arr[front]);
       front++;
   }
}

/*
 * It will check whether the queue if full or not
 * return 1, if the queue is full
 * return -1, otherwise
 */
int isQueueFull()
{
   if(rear == size)
       return 1;
   return -1;
}

//adds element at the end of the queue
void enqueue(int val)
{
   if(isQueueFull() == 1)
       printf("Queue is Full\n");
   else
   {
       arr[rear] = val;
       rear++;
   }
}

int main()
{
   enqueue(10);
   enqueue(20);
   enqueue(30);
   enqueue(40);
   enqueue(50);
   enqueue(60);    //Can't insert 60 as the queue is full.
   dequeue();      //10
   dequeue();      //20
   dequeue();      //30
   dequeue();      //40
   dequeue();      //50
   dequeue();      //can't dequeue as the queue is empty

   return 0;
}