Queue is a linear data structure in which data can be added to one end and
retrieved from the other. Just like the queue of the real world, the data that
goes first into the queue is the first one to be retrieved. That is why queues
are sometimes called as First-In-First-Out data structure.
In case of queues, we saw that data is inserted both from one end but in case
of Queues; data is added to one end (known as REAR) and retrieved from the other
end (known as FRONT).
The data first added is the first one to be retrieved while in case of queues
the data last added is the first one to be retrieved.
A few points regarding Queues:
Queues: It is a linear data structure; linked lists and
arrays can represent it. Although representing queues with arrays have its
shortcomings but due to simplicity, we will be representing queues with
arrays in this article.Rear: A variable stores the index number in the array
at which the new data will be added (in the queue).Front: It is a variable storing the index number in the
array where the data will be retrieved.
Let us have look at the process of adding and retrieving data in the queue
with the help of an example.
Suppose we have a queue represented by an array queue [10], which is empty
to start with. The values of front and rear variable upon different actions
are mentioned in {}.
queue [10]=EMPTY {front=-1, rear=0}
add (5)
Now, queue [10] = 5 {front=0, rear=1}
add (10)
Now, queue [10] = 5, 10 {front=0, rear=2}
retrieve () [It returns 5]
Now, queue [10] = 10 {front=1, rear=2}
retrieve () [now it returns 10]
Now, queue [10] is again empty {front=-1, rear=-1}
In this way, a queue like a stack, can grow and shrink over time.
Now have a look at the following example program that illustrates all this
stuff:
// -- A Queue Class in C++ --
// example program in C++ to
// illustrate queues represented
// by arrays
#include<iostream.h>
// macro to hold the max
// number of elements
// in the queue
#define MAX 10
// queue class
class queue
{
int arr[MAX];
int front, rear;
public:
void add(int);
int retrieve(void);
queue();
};
// queue class ends
// member functions
queue::queue()
{
// initialize index
// variables
front=-1;
rear=0;
}
void queue::add(int data)
{
if(rear==MAX-1)
{
cout<<"QUEUE FULL!";
return;
}
arr[rear]=data;
// increase index
// variable
rear++;
if(front=-1)
front=0;
}
int queue::retrieve()
{
int data;
if(front==-1)
{
cout<<"QUEUE EMPTY!";
return NULL;
}
data=arr[front];
arr[front]=0;
// if both index variables
// point to the same location
// then start afresh
if(front==rear-1)
{
front=-1;
rear=0;
}
else
front++;
return data;
}
// member functions ends
void main(void)
{
queue obj;
int ch;
int num;
while(ch!=3)
{
cout<<"1> ADD";
cout<<"\n2> RETRIVE";
cout<<"\n3> QUIT\n";
cin>>ch;
switch(ch)
{
case 1:
cout<<"enter element:";
cin>>num;
obj.add(num);
break;
case 2:
cout<<"\n\nRetrieved: ";
cout<<obj.retrieve();
cout<<"\n\n";
break;
}
}
}Good-Bye
Please do check back for updates!
Related Articles: