Implementation Of Queue Using Array In C++

What is a Queue in Data Structure?

It is a type of linear data structure that enforces the first-in-first-out (FIFO) mechanism to categorize objects successively, according to their need to be added or removed. Data leaves the queue through the FRONT and enters from REAR. To make the concept clearer, picture this: In day to day life, those who discharge their bills first in the shopping line in a supermarket get to leave first with the items purchased! So, in this tutorial, we are gonna learn the algorithms to implement various operations of Queue using array in c++.

Operations of Queue in C++

  • enqueue: adds an item at the back of the queue.
  • dequeue: removes an element from the front end of the queue.
  • peek: fetches the front element without removing (de-queuing) it.
  • isEmpty: conducts a check to determine whether a queue is empty.
  • isFull: checks to detect whether the queue is full.
  • size: returns the total number of elements.

Fundamental Operations Of Queue Using Array:

Operation 1 : Insertion In Queue Using Array

An array that contains zero elements (empty array) has both the FRONT and REAR (segments/pointers) pointing to the null position. This condition is needed before inserting the elements. Follow the steps below to perform the insertion operation.

Example:

  • Insert an element, say 10, at the 0th index, which is also conducted by the REAR pointer.
  • Then the FRONT pointer would perform the delete operation
  • Continue to keep inserting other elements, say 20, 30, and so on.
  • As you keep inserting a new element, the REAR would move ahead, but the FRONT maintains its position
  • Therefore, when you insert the element ‘30’, the REAR would move to the second index while the FRONT remains at the 0th index itself

Insertion In Queue Using Array

Operation 2 – Deletion In Queue Using Array

Unlike the Insert operation where the REAR moved and the FRONT remained steady, in Delete operation, the FRONT moves while the REAR remains steady.

Deletion Operation In Queue Using Array

Example:

  • Remove the element present at the 0th index (in this case, 10)
  • Now the value of FRONT would increase by a factor of 1, i.e., it would take up an address that is one digit higher than what it was before
  • But however, the REAR still remains in its original position rather than moving
  • So, its index does not change and remains ‘2’
  • If you would continue to delete further, it would result in obtaining the original information, with both REAR and FRONT pointing to the same null index.

Deletion Operation In Queue Using Array

Operation 3 : Searching In Queue

This operation is used to scan the queue in C++ for an element and display the resultant object’s position in the queue. This is accomplished by either of two primary methods as listed below:

  • Linear Search

In this technique, the element to be found is searched sequentially along the queue, and this action can be performed well in sorted/unsorted arrays. Starting from the 0th element, the search continues until the desired element is found.

  • Binary Search

Unlike the slow searching process in Linear Search, in Binary Search the array is split in two: one from the 0th to the middle element, and the other from the center to the last element. Here search results are obtained fast.

  • Search using a temporary array

Consider 5 elements (5,4,3,2,1) for which the central element has to be removed through search. We can do this by popping three elements into another data structure, then popping the desired element, pushing the three elements back into the queue, and thereby pushing the required element to its destined position, with the new queue order being rearranged as 2,5,4,3,1.

Implementation of Queue Using Array In C++:

Array, Stack or Linked List can be used to implement queues in C++. Let us explore the array implementation technique.

As the array elements are fed, the REAR moves ahead, positioning itself on the index where the next element will be added, while the FRONT remains at the first index. As per this approach, removal of an element in the FRONT index ensures a shift of the successive elements in the forwarding order.

C++ Program For Implementing Queue Using Array In C++

#include<stdio.h>;
#define SIZE 5
int queue[SIZE];
int front=0,rear=0;
void insert(int);
void traverse();
void del();
int main()
{
  int item,ele,opt;
  while(1)
  {
    printf("Choose The Operation You Want To perform\n");
    printf("1.Insert\n 2.Delete\n 3.Traverse\n 4.Exit\n");
    scanf("%d",&amp;opt);
    switch(opt)
    {
      case 1:
        printf("Enter The Element You Want To Insert\n");
        scanf("%d",&amp;item);
        insert(item);
        break;
      
      case 2:
          del();
        break;
        
      case 3:
          traverse();
        break;
        
      case 4:
          return 0;
        
      default:printf("Invalid Choice");				
    }
  }
  
}
void insert(int ele)
{
  if(SIZE==rear)
  {
    printf("Queue Is Full\n");
  }
  else
  {
    queue[rear]=ele;
    rear++;
    printf("%d Inserted Successfully\n",ele);
  }
}

void traverse()
{
  int i;
  if(front==rear)
  {
    printf("Queue Is Empty\n");
  }
  else
  {
    printf("Elements In The Queue Are\n");
    for(i=front;i&lt;=rear;i++)
    {
      printf("%d\n",queue[i]);
    }
  }
}

void del()
{
  int i;
  if(front==rear)
  {
    printf("Queue Is Empty\n");
  }
  else
  {
    printf("%d Deleted\n",queue[front]);
    for(i=0;i&lt;rear;i++)
    {
      queue[i]=queue[i+1];	
    }
    rear--;
  }
}

 

Leave a Comment