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.

queue init




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

enqueue 10

ii) enqueue 20

enqueue 20

iii) enqueue 30

enqueue 30

iv) enqueue 40

enqueue 40

v) enqueue 50

enqueue 50

vi) enqueue 60

Queue full

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

dequeue 10

ii) dequeue

dequeue 20

iii) dequeue

dequeue 30

iv) dequeue

dequeue 40

v) dequeue

dequeue 50

vi) dequeue

Queue empty

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;
}


Topics You Might Like