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 queueis empty, it returns the value true; otherwise, it returns the value false.• isFullQueue—Determines whether the queue is full. If the queue isfull, it returns the value true; otherwise, it returns the value false.• front—Returns the front, that is, the first element of the queue. Priorto this operation, the queue must exist and must not be empty.• back—Returns the last element of the queue. Prior to this operation, thequeue must exist and must not be empty.• addQueue—Adds a new element to the rear of the queue. Prior to thisoperation, the queue must exist and must not be full.• deleteQueue—Removes the front element from the queue. Prior tothis 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;

}