Implementing Queue using Array in C++ Program

Table of contents

Queue Using Array in C++

Introduction: Queue using array

A queue is a Non-Primitive Linear Data Structure so just like an Array. It is a homogenous (similar ) collection of elements in which new elements are inserted at one end Called the Rear end, and the existing elements are deleted from the other end called the Front end.

A Queue is logically a First in First Out ( FIFO ) type of list or a data structure.

Suppose there are some situations in our life when we have to wait in a line or a queue to get our job done e.g. waiting in a line at a ticket counter the person which comes first Will be served first thus follows a FIFO type of data structure.

Queue simply means a line and follows FIFO logical design, which means the element inserted first will be deleted first.

In Queue the elements are inserted at the Rear End and the elements present in the queue are deleted at the Front End.

It is a very useful data structure which is used in various aspects of programming fields and in the software development process.

There are two main ways to implement queues.

Queue Using Arrays = Static Implementation
Queue Using Linked Lists = Dynamic Implementation

Queue Using Array in C++

Whenever we use Arrays we must be sure about the size of the array needed for our program at the design time because array Size can not be changed during run time it is allocated at the compile time.

So, Therefore, you must declare the exact amount of size required for the queue elements.

Operations on a queue using array in c++.

Insert an element 2. Delete an Element.

Algorithm for Insertion.

Set Front = 0 & Rear = -1.
If Rear >= Size, write queue Overflow, return.
Else, Set Rear = Rear + 1. Queue [ Rear ] = Item.
If Front = -1, Return

Algorithm for Deletion.

If Front < 0, write queue empty.
Else, item = Queue [ Front].
If ( Front = Rear ) , set front = 0, rear = -1.
Else, Front = Front + 1.

Queue using arrays in c++ Program

//techindetail.com

//queue using arrays in c/c++

#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<process.h>

using namespace std;
 #define SIZE 3
		//make a class & name it stk
class stk
{
	int stack[SIZE]; //stack using arrays
	int top;
	public:
		void push();
		int pop();
		void display();
	stk()
	{
		top=-1;
	}
};

  void stk::push()
  {
  	int item;
    if(top==SIZE-1)
     	{
	cout<<"Stack is Full\n";
	return(0);

  		}
  else{
  	cout<<"Enter element to push: \n";
  	cin>>item;
  	top=top+1;
  	stack[top]=item;
  	
  	  }
  }
 int stk::pop()
 {
 	int temp;
 	if(top==-1)
 	 {
 		cout<<"Empty Stack:\n";
 		return(0);
	 }
	else
	{
		temp=stack[top];
		top=top-1;
	 }return(temp);
 }
 
	//travese and display
 void stk::display()
 {
 	if(top==-1)
 	 cout<<"stack empty\n";
 	 else
 	 {
 	 	for(int i=top; i>=0; i--)
 	 	{
 	 		cout<<"Elements are:\t";
 	 		cout<<stack[i];
 	 		
		  }
	  }cout<<endl;
 }
 
 int main(){
  	 
  	 int option=0;
  	 stk s;
  	 int element;
while(1)
{
	cout<<" ---------------------------------\n";
  cout<<"enter 1 to push:\nenter 2 for pop:\n";
  cout<<"enter 3 for display:\nenter 4 for exit\n";
  cout<<" ---------------------------------\n";

	cout<<"Enter option: \n";
  	 cin>>option;
  	
	   switch(option){
  	 	 case 1:
  	 		s.push();
		 	break;
		 case 2:
			element=s.pop();
		 	cout<<" ----  sucessful    ----";
		 	cout<<"popped element is= "<<element<<endl;
		 	break;
		  case 3:
		    s.display();
			break;
		 case 4:
		    exit(0);
		default:
		  cout<<"wrong choice\n";
		  break;
	}
}
  
getch();
  return 0;
  
}

	// techindetail.comCode language: C++ (cpp)

Real Life Uses of Queues.

When you send commands to the printer to print various documents, the given requests are organized In a queue data structure, and according to FIFO ( First in First Out ) pattern the first request is compiled and The document is printed, then the other document, and so on…

Limitations of Simple queues.

There are some drawbacks of simple queues, like after some insertion and deletion operations when the Rear reaches to the end, We cannot add more elements now because the elements are inserted at the rear end and rear seems to be max size given to the arrays, Although now the queue may be empty or maybe it has the only element in it will show us the queue is full.

So there is a wastage of memory and resources which is not acceptable. There are some techniques which can overcome this but it is only worthwhile If the queue is small not a big one containing a big amount of data so that we can shift the elements whenever necessary.

Types of Queues.

Circular Queue.
Double-ended Queue ( de-queue ).
Priority Queue.

1. Circular Queue

The Circular Queue is implemented by visualizing or by imagination as the one-dimensional array as a circular queue.

A circular queue overcomes the problem of unutilized space in linear or simple queues implemented by arrays.

In circular queue the insertion of a new element is done at the very first location of the queue if the last location is full.

Suppose we have a queue Q with n elements, then after inserting the last element ( at n-1 th) location of the array we can insert next element

At the very first location ( i.e., location with subscript 0 ) of the array.

So Circular Queue can be logically thought of as a Mesh or loop of wire, in which the ends of the wire are connected together. It also have a Front and Rear to keep track of the elements to be deleted and inserted.

Some Assumptions of Circular Queue.

The front will always be pointing to the first element.
If Front = Rear, then Queue is empty.
After each Insertion, Rear = Rear + 1 .
After each Deletion, Front = Front + 1 .

2. Double-ended Queue ( or de-queue ).

It is also the similar list of elements in which insertion and deletion operations are performed from both the ends.

That is, we can insert elements from the Rear as well as at the Front end, and we can delete from both Front and Rear end.

There are two types of deque.

Input-Restricted Queue. b. Output- Restricted Queue.

These restrictions are put to restrict the insertion and deletion from only on the one end.

For any input restricted queue, given below operations 1 ,2 , 3 and 4 are valid. And for any Output restricted deque , Only 1 , 2, 3 are valid only.

Operations on Double ended queues.

Insert at Rear end of queue.
Insert at Front end of queue.
Delete at Rear end of queue.
Delete at Front end of queue.

3. Priority Queues.

In some Situations, the items added into the queue have a priority associated with them, so this priority determines the order in which they are served or the highest priority items are removed or analyzed first.

This situation arises often in Process Control Systems. In a large Automated Factory, dangerous industrial process, nuclear reactors, Flight control system, the operator’s console receives many routine messages from all parts of the machinery in the whole system or in a factory.

Normal messages have low priority in compared to Emergency alerts. For example, if something breaks or fire emerges in plant or if something happens Then those Alerts and Alarms have the highest priority to be analysed and corrected first.

Suggested Read: