Representation Queues using Arrays

Representation Queues using Arrays

 

• We can represent Queues using arrays. We can perform various operations on queues such as

1) Insertion of element in the queue

2) Deletion of element from the queue

3) Checking Queue Overflow conditioning

4) Checking Queue Underflow condition

 

Following is a structure that represents the Queue data structure using arrays.

'C++' representation of queue.

struct queue

{

   int que [size];

   int front;

   int rear,

}Q

 

1. Insertion of element into the queue

The insertion of any element in the queue will always take place from the rear end.

Before performing insert operation you must check whether the queue is full or not. If the rear pointer is going beyond the maximum size of the queue then the queue overflow occurs.

 

2. Deletion of element from the queue

The deletion of any element in the queue takes place by the front end always.

 Before performing any delete operation one must check whether the Queue is empty or not. If the Queue is empty, you can not perform the deletion. The result of illegal attempt to delete an element from the empty queue is called the Queue Underflow condition.

Let us see the C++ implementation of the queue.

C++ Program

/****************************************************************

Program for implementing the Queue using arrays

****************************************************************/

#include<iostream>

#include<cstdlib>

using namespace std;

#define size 5

class MyQ

{

private:

struct queue

{

int que[size];  //Queue data structure declared with arry que [ ], front and rear

int front,rear;

}Q;

public:

MyQ();

int Qfull();

int insert(int);

int Qempty();

int delet();

void display();    

};

MyQ::MyQ()

{

Q.front = ‒1;

Q. rear = ‒1;

}

int MyQ::Qfull()

{

if(Q.rear >=size‒1)  //If Queue exceeds the maximum size of the array then it returns1 ‒ means queue full is true otherwise 0 means queue full is false

return 1;

else

return 0;

}

int MyQ::insert(int item)

{

if(Q.front = =‒1)

Q.front++;          //This condition will occur initially when queue is empty

Q.quel[++Q.rear] = item;  //Always increment the rear pointer and place the element in the queue.

return Q.rear;

}

int MyQ::Qempty()

if((Q.front = = ‒1) || (Q.front > Q.rear)) 

return 1;

else

return 0;

}

int MyQ::delet()

{

int item;

item Q.que[Q.front];    

Q.front++;

cout<<"\n The deleted item is "<<item;

return Q.front;

}

void MyQ::display()

{

int i;

for(i=Q.front;i<=Q.rear;i++)     <‒‒‒‒‒‒‒printing the queue form front to rear

cout<<" "<<Q.que[i];

}

void main(void)

{

int choice,item;

char ans;

MyQ obj;

clrscr();

do

{

cout<<"\n Main Menu";

cout<<"\n1.Insert\n2.Delete\n3.Display";

cout<<"\n Enter Your Choice: ";

cin>>choice;

switch(choice)

{

case 1:if(obj.Qfull())  //checking for Queue overflow

      cout<<"\n Can not insert the element";

else

{

      cout<<"\n Enter The number to be inserted ";

      cin>>item;

      obj.insert(item);

}

break;

case 2:if(obj.Qempty())

            cout<<"\n Queue Underflow!!";

      else

            obj.delet();

      break;

case 3:if(obj.Qempty())

            cout<<"\nQueue Is Empty!";

      else

            obj.display();

      break;

default:cout<<"\n Wrong choice!";

      break;

}

cout<<"\n Do You Want to continue?";

ans =getche();

}while(ans = =Y'||ans = ='y');

}

/*********** End Of Program ********************/

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1

Enter The number to be inserted 10

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1

Enter The number to be inserted 20

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1

Enter The number to be inserted 30

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1

Enter The number to be inserted 40

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 3

10 20 30 40

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2

The deleted item is 10

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2

The deleted item is 20

Do You Want to continue?y

Main Menu

1.Insert

2.Delete

B.Display

Enter Your Choice: 3

30 40

Do You Want to continue?

 

Review Questions

1. What is queue? With algorithms explain about the various operations performed on queues.

2. Write ADT operations for array implementation of a queue.

OR Explain how queues can be implemented using arrays

3. Write algorithms to insert an element into a stack and a queue. Can stack be used for recursion? Justify your answer.

4. Explain the operations performed on QUEUE in detail. Write a C++ program to implement these QUEUE operations.

5. Write pseudo code for insertion and deletion from queue.

6. Develop an algorithm to implement Queue ADT. Give relevant examples and diagrammatic representation.