A queue is a set of elements of the same type in which the elements are added at one end,
called the back or rear, and deleted from the other end, called the front. For example,
consider a line of customers in a bank, wherein the customers are waiting to withdraw/deposit
money or to conduct some other business. Each new customer gets in the line at the rear.
Whenever a teller is ready for a new customer, the customer at the front of the line is served
Queue: A data structure in which the elements are added at one end, called the rear, and deleted from the other end, called the front; a First In First Out (FIFO) data structure.
• initializeQueue—Initializes the queue to an empty state.
• isEmptyQueue—Determines whether the queue is empty. If the queue
is empty, it returns the value true; otherwise, it returns the value false.
• isFullQueue—Determines whether the queue is full. If the queue is
full, it returns the value true; otherwise, it returns the value false.
• front—Returns the front, that is, the first element of the queue. Prior
to this operation, the queue must exist and must not be empty.
• back—Returns the last element of the queue. Prior to this operation, the
queue must exist and must not be empty.
• addQueue—Adds a new element to the rear of the queue. Prior to this
operation, the queue must exist and must not be full.
• deleteQueue—Removes the front element from the queue. Prior to
this operation, the queue must exist and must not be empty.
Empty Queue and Full Queue
As discussed earlier, the queue is empty if count == 0, and the queue is full if count == maxQueueSize. So the functions to implement these operations are as follows:
template <class Type>
bool queueType<Type>::isEmptyQueue() const
{
return (count == 0);
} //end isEmptyQueue
template <class Type>
bool queueType<Type>::isFullQueue() const
{
return (count == maxQueueSize);
} //end isFullQueue
Front:
This operation returns the first element of the queue. If the queue is nonempty, the
element of the queue indicated by the index queueFront is returned; otherwise, the
program terminates.
template <class Type>
Type queueType<Type>::front() const
{
assert(!isEmptyQueue());
return list[queueFront];
} //end front
Back:
This operation returns the last element of the queue. If the queue is nonempty, the
element of the queue indicated by the index queueRear is returned; otherwise, the
program terminates.
template <class Type>
Type queueType<Type>::back() const
{
assert(!isEmptyQueue());
return list[queueRear];
} //end back
Add Queue
Next, we implement the addQueue operation. Because queueRear points to the last
element of the queue, to add a new element to the queue, we first advance queueRear to
the next array position, and then add the new element to the array position indicated by
queueRear. We also increment count by 1. So the function addQueue is as follows:
template <class Type>
void queueType<Type>::addQueue(const Type& newElement)
{
if (!isFullQueue())
{
queueRear = (queueRear + 1) % maxQueueSize; //use the
//mod operator to advance queueRear
//because the array is circular
count++;
list[queueRear] = newElement;
}
else
cout << “Cannot add to a full queue.” << endl;
} //end addQueue
Delete Queue:
To implement the deleteQueue operation, we access the index queueFront. Because
queueFront points to the array position containing the first element of the queue, to
remove the first queue element, we decrement count by 1 and advance queueFront to
the next queue element. So the function deleteQueue is as follows:
template <class Type>
void queueType<Type>::deleteQueue()
{
if (!isEmptyQueue())
{
count–;
queueFront = (queueFront + 1) % maxQueueSize; //use the
//mod operator to advance queueFront
//because the array is circular
}
else
cout << “Cannot remove from an empty queue” << endl;
} //end deleteQueue
Priority Queues
The preceding sections describe how to implement a queue in a program. The use of a
queue structure ensures that the items are processed in the order they are received. For
example, in a banking environment, the customers who arrive first are served first.
However, there are certain situations when this First In First Out rule needs to be relaxed
somewhat. In a hospital environment, patients are, usually, seen in the order they arrive.
Therefore, you could use a queue to ensure that the patients are seen in the order they
arrive. However, if a patient arrives with severe or life-threatening symptoms, they are
treated first. In other words, these patients take priority over the patients who can wait to
be seen, such as those awaiting their routine annual checkup. For another example, in a
shared environment, when print requests are sent to the printer, interactive programs take
priority over batch-processing programs.
There are many other situations where some priority is assigned to the customers. To
implement such a data structure in a program, we use a special type of queue, called priority
queues. In a priority queue, customers or jobs with higher priority are pushed to the front
of the queue.
One way to implement a priority queue is to use an ordinary linked list, which keeps the
items in order from the highest to lowest priority. However, an effective way to implement a priority queue is to use a treelike structure.
QUEUE IMPLEMENTATION USING ARRAY:
/*implemented queue using array*/
#include <iostream>
using namespace std;
int queue[100], n = 100, front = – 1, rear = – 1;
void Insert() { // it inserts an element into the queue
int val;
if (rear == n – 1) // //if rear is equal to n-1, then the queue is full
cout<<“Queue Overflow”<<endl;
else {
if (front == – 1) //if front is -1,
front = 0; //it is incremented by 1.
cout<<“Insert the element in queue : “<<endl;
cin>>val;
rear++; //Then rear is incremented by 1
queue[rear] = val; //and the element is inserted at the index of rear
}
}
void Delete() {
if (front == – 1 || front > rear) { //if there are no elements in the queue
cout<<“Queue Underflow “; //then queue is underflow
return ;
} else {
//Otherwise the element at front is displayed and front is incremented by one
cout<<“Element deleted from queue is : “<< queue[front] <<endl;
front++;;
}
}
void Display() {
if (front == – 1) //if front is -1 then queue is empty
cout<<“Queue is empty”<<endl;
else { //if queue is not empty then
cout<<“Queue elements are : “;
for (int i = front; i <= rear; i++) //display all elements of queue
cout<<queue[i]<<” “;
cout<<endl;
}
}
/* now test it by calling the functions that you made*/
int main() {
Insert();
Insert();
Display();
Delete();
return 0;
}
