Queue Data Structure
Data Structure Data Structure Notes

Queue Data Structure

Posted on Author admin Comment(0)

Queue Data Structure

Queue Data Structure follow the FIFO principle. In this tutorial we will learn about basic introduction of Queue, different operations on Queue and Array Implementation of Queue is also explained.

After the study of this tutorial students can easily answer the following frequently asked questions based on queue. Students also will be able to make a program in c to implement queue using array.

Frequently Asked Question

Some frequently asked questions from queue are given below

  • What is Queue ?
  • What is difference between Stack and Queue.
  • What is the condition to check queue is empty or full ?
  • Write the steps to insert an element in queue.
  • Write the steps to remove an element from queue.
  • Write a C Program to implement queue.

What is Queue ?

  • Queue is a non-primitive linear data structure that allows insertion of an element at one end and deletion of an element at the other end.
  • The end at which the deletion of an element take place is called Front, and the end at which insertion of a new element can take place is called Rear.
  • The first element that gets added into the queue is the first one to get removed from the list. Hence, Queue is also referred to as First-In-First-Out (FIFO) list.

Queue can be implemented using Array and Linked List. In this tutorial we will discuss the various concepts of queue using Array Implementation.

Representation of queue

  • In fig (1), 10 is the first element and 80 is the last element added to the Queue.

Similarly,10 would be the first element to get removed and 80 would be the last element  to get removed.

Operations on Queue

Various operations on queue that we can perform are as follow

Insertion Operation – Inserting a new element in queue

Deletion Operation – Deleting or removing an element from queue.

Searching – Looking for the presence a specific elements in queue.

Display – Display the elements of queue.

Also Read – Applications of Queue

Insertion in Queue

In this section we are going to discuss the algorithm for insertion operation in queue using Array.

Let QUEUE[MAXSIZE] is an array for implementing the Linear Queue & NUM is the element to be inserted in linear queue, FRONT represents the index number of the element to be deleted and REAR represents the index at which element will be insert.

We use the following steps to insert an element in queue.

Step 1 : If REAR = (MAXSIZE –1) : then

Write : “Queue Overflow” and return

[End of If structure]

Step 2 : Read NUM to be inserted in Linear Queue.

Step 3 : Set REAR := REAR + 1

Step 4 : Set QUEUE[REAR] := NUM

Step 5 : If FRONT = –1 : then

Set FRONT=0.

[End of If structure]

Step 6 : Exit

Note – In the above queue insertion algorithm Step 5 will be used when we are going to insert first element in queue.

Insertion in Queue Example

Insertion of some elements in queue is shown in following figure.

  • Initially when Front =-1 and Rear=-1 then queue is empty.
  • To insert first element 20 in queue we perform Rear = Rear + 1 and set Front =0 because now there is at least one element to be deleted in queue.
  • To insert next element 30 in queue first we increase Rear by one and then insert the element at the index value of Rear in queue.

insertion in queue

insertion in queue

Deletion in Queue

In this section we will see the steps to remove an element from queue data structure.

Let QUEUE[MAXSIZE] is an array for implementing the Linear Queue & NUM is the element to be deleted from linear queue

Step 1 : If FRONT = -1 : then

Write : “Queue Underflow” and return

[End of If structure]

Step 2 : Set NUM := QUEUE[FRONT]

Step 3 : Write “Deleted item is : ”, NUM

Step 4 : Set FRONT := FRONT + 1.

Step 5 : If FRONT>REAR : then

Set FRONT := REAR := -1.

[End of If structure]

Step 6 : Exit

Note – In the above queue deletion algorithm Step 5 will be used when we are going to delete the last element in queue. After that queue will be empty so we will set Front =-1 and Rear=-1

Deletion in Queue Example

Deletion of previously inserted elements in queue is as shown in following figure.

After deleting an element from queue we have to increase the front by one . New value of front represent the index from which next element will be deleted.

queuedeletion

 Array implementation of Queue

C program to implement the queue using array is explained.

Menu Driven program to perform insertion and deletion operations on queue is given below

#include<stdio.h>

#include<stdlib.h>

#define MAXSIZE 5

void qinsert();

void qdelete();

void qtraverse();

int queue[MAXSIZE];

int front=-1,rear=-1;

void main()

{

int choice;

while(choice !=4)

{

printf(“\n  IMPLEMENTATION OF LINEAR QUEUE USING ARRAY “);

printf(“\n————————————-“);

printf(“\n1. Insert”);

printf(“\n2. Delete”);

printf(“\n3. Traverse”);

printf(“\n4. Exit”);

printf(“\n————————————-“);

printf(“\n\nEnter your choice [1/2/3/4] : “);

scanf(“%d”,&choice);

switch(choice)

{

case 1 : qinsert();

break;

case 2 : qdelete();

break;

case 3 : qtraverse();

break;

case 4 : exit(0);

default : printf(“\nInvalid choice”);

}

}

}

// Function to insert an element into queue

void qinsert()

{

int num;

if(rear==MAXSIZE-1)

{

printf(“\nQueue is full (Queue overflow)”);

return;

}

printf(“\nEnter the element to be inserted : “);

scanf(“%d”,&num);

rear++;

queue[rear]=num;

if(front==-1)

front=0;

}

// Function for Delete an element from queue

void qdelete()

{

if(front==-1)

{

printf(“\nQueue is empty (Queue underflow)”);

return;

}

int num;

num=queue[front];

printf(“\nDeleted element is : %d”,num);

front++;

if(front>rear)

front=rear=-1;

}

// Function to visit the elements of Queue

void qtraverse()

{

if(front==-1)

{

printf(“\nQueue is empty (Queue underflow)”);

return;

}

else

{

printf(“\nQueue elements are : \n”);

for(int i=front;i<=rear;i++)

printf(“%d\t”,queue[i]);

}

}

Output

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 1

Enter the element to be inserted : 11

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 1

Enter the element to be inserted : 12

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 1

Enter the element to be inserted : 13

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 1

Enter the element to be inserted : 14

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 3

Queue elements are :

11        12        13        14

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 2

Deleted element is : 11

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

————————————-

Enter your choice [1/2/3/4] : 3

Queue elements are :

12        13        14

IMPLEMENTATION OF LINEAR QUEUE USING ARRAY

————————————-

  1. Insert
  2. Delete
  3. Traverse
  4. Exit

Conclusion and Summary

In this Queue Data Structure Tutorial we have discussed the Overview of Queue Data Structure , insertion and deletion in queue and array implementation of queue using array.

admin

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *