Queue is a linear data structure and it works on the principle of First In, Last Out (FILO). One of the common ways to implement a queue is using arrays. The elements are inserted at the front of the queue and removed from the rear of the queue.
Before you learn about how to implement a queue, be familiar with the concept of arrays and queue. If you are familiar with the basics, continue reading.
Problem Definition
This program implements a simple queue in which elements are inserted from the front and removed from the rear of the queue as mentioned earlier. So we maintain two variables to keep track of queue status.
You can perform three operations on a queue.
- Insert a Queue Element
- Delete Queue Element
- Display Queue Elements
But, remeber that the queue operations are limited by the status of the queue at given time.If queue is full, then there is no insertion, or if queue is empty then there is not deletion.
Therefore, queue states are following.
Queue Initial State
front = rear = 0
Queue is Empty
front == rear
Queue is Full
front = = 0
rear = = Queue size
In any case, the rear will not exceed the size of the queue.
Flowchart
From the following flowchart, it is clear that when user input their choice, the Queue object calls specific functions like Insert_Q() or Delete_Q() and display results immediately using Display_Q() function. The function definition is given in the program code section. The queue operations continue until user decides to quit with choice ‘q’.
Program Code
//Queue using Arrays
#include <cstdlib>
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#include <process.h>
#define size 5
// class queue definition
class Queue
{
public:
int rear, front;
int ele;
int q[size];
Queue()
{
rear = front = 0;
}
void Insert_Q();
void Delete_Q();
void Display_Q();
};
// Function definition Insert_Q()
void Queue::Insert_Q()
{
cout << "Input Queue Element:";
cin>> ele;
// rear must never be greater than size
if(rear < size)
{
rear++; //increment the rear
q[rear] = ele; // insert the new element
if(front == 0)
{
front=1;
}
else
{
cout << "Queue is Full\n";
}
}
}
// Function Definition for Delete_Q()
void Queue::Delete_Q()
{
// Find out if queue is empty
if(front == 0)
{
cout << "Queuy is Empty. Nothing to Delete!" << endl;
return;
}
else
{
ele = q[front]; // delete the element that front is pointing to
cout << "Element Deleted :" << ele << endl;
}
if(front == rear)
{
front = 0;
rear = 0;
}
else
{
front = front + 1;
}
}
//Function Definition for Display_Q()
void Queue::Display_Q()
{
if(front == 0)
return;
for(int i=front;i<=rear;i++)
{
cout << " " << q[i];
}
cout << "\n\n";
}
using namespace std;
int main()
{
Queue Q;
int k = 0;
char choice;
do
{
cout <<"Insert -> I Delete -> D Quit -> Q " << endl;
cout <<"Input the choice:"<< endl;
do
{
cin >> choice;
choice = tolower(choice);
}while(strchr("idq",choice)==NULL);
cout << "Your choice is -> " << choice << endl;
switch(choice)
{
case 'i':
Q.Insert_Q();
cout <<"Queue after Insertion:";
Q.Display_Q();
break;
case 'd':
Q.Delete_Q();
cout <<"Queue after Deletion"<< endl;
Q.Display_Q();
break;
case 'q':
k=1;
}
}while(!k);
system("PAUSE");
return EXIT_SUCCESS;
}Output
We input two numbers first using the choice ‘i’ and then deleted 56 from the front of the queue.
