C++ Queues

What is a queue? How to implement queues using C++?

This article explains the queue data structure and demonstrates sample implementation using C++.
  • Queue is a first-in, first-out (FIFO) data structure. i.e. the element added first to the queue will be the one to be removed first.
  • Elements are always added to the back of the queue and removed from the front of the queue.
  • Typical use cases of queues include:- (1) In Inter-Process Communication (IPC) message queues is a common mechanism for communication between processes.
  • Some of the common terminology associated with queues inlcude ADD/ PUSH and DELETE/ POP of elements to the queue.
  • ADD/ PUSH refers to adding an element to the queue.
  • DELETE/ POP refers to removing an element from the queue.
  • Diagram below explains the queue.

C++ Queues

Demonstrate the implementation of a simple queue using arrays

#include <iostream>#include <cstdlib>using namespace std;const int MAX_SIZE = 100;class QueueOverFlowException{public:QueueOverFlowException(){cout << "Queue overflow" << endl;}};class QueueEmptyException{public:QueueEmptyException(){cout << "Queue empty" << endl;}};class ArrayQueue{private:int data[MAX_SIZE];int front;int rear;public:ArrayQueue(){front = -1;rear = -1;}void Enqueue(int element){// Don't allow the queue to grow more// than MAX_SIZE - 1if ( Size() == MAX_SIZE - 1 )throw new QueueOverFlowException();data[rear] = element;// MOD is used so that rear indicator// can wrap aroundrear = ++rear % MAX_SIZE;}int Dequeue(){if ( isEmpty() )throw new QueueEmptyException();int ret = data[front];// MOD is used so that front indicator// can wrap aroundfront = ++front % MAX_SIZE;return ret;}int Front(){if ( isEmpty() )throw new QueueEmptyException();return data[front];}int Size(){return abs(rear - front);}bool isEmpty(){return ( front == rear ) ? true : false;}};int main(){ArrayQueue q;try {if ( q.isEmpty() ){cout << "Queue is empty" << endl;}// Enqueue elementsq.Enqueue(100);q.Enqueue(200);q.Enqueue(300);// Size of queuecout << "Size of queue = " << q.Size() << endl;// Front elementcout << q.Front() << endl;// Dequeue elementscout << q.Dequeue() << endl;cout << q.Dequeue() << endl;cout << q.Dequeue() << endl;}catch (...) {cout << "Some exception occured" << endl;}}

OUTPUT:-

Queue is emptySize of queue = 3100100200300

Demonstrate the implementation of a simple queue using linked lists

#include <iostream>using namespace std;class QueueEmptyException{public:QueueEmptyException(){cout << "Queue empty" << endl;}};class Node{public:int data;Node* next;};class ListQueue{private:Node* front;Node* rear;int count;public:ListQueue(){front = NULL;rear = NULL;count = 0;}void Enqueue(int element){// Create a new nodeNode* tmp = new Node();tmp->data = element;tmp->next = NULL;if ( isEmpty() ) {// Add the first elementfront = rear = tmp;}else {// Append to the listrear->next = tmp;rear = tmp;}count++;}int Dequeue(){if ( isEmpty() )throw new QueueEmptyException();int ret = front->data;Node* tmp = front;// Move the front pointer to next nodefront = front->next;count--;delete tmp;return ret;}int Front(){if ( isEmpty() )throw new QueueEmptyException();return front->data;}int Size(){return count;}bool isEmpty(){return count == 0 ? true : false;}};int main(){ListQueue q;try {if ( q.isEmpty() ){cout << "Queue is empty" << endl;}// Enqueue elementsq.Enqueue(100);q.Enqueue(200);q.Enqueue(300);// Size of queuecout << "Size of queue = " << q.Size() << endl;// Front elementcout << q.Front() << endl;// Dequeue elementscout << q.Dequeue() << endl;cout << q.Dequeue() << endl;cout << q.Dequeue() << endl;}catch (...) {cout << "Some exception occured" << endl;}}

OUTPUT:-

Queue is emptySize of queue = 3100100200300

Demonstrate the queue library usage in standard template library (STL)

#include <iostream>#include <queue>using namespace std;int main(){queue<int> q;q.push(100);q.push(200);q.push(300);q.push(400);cout << "Size of the queue: " << q.size() << endl;cout << q.front() << endl;q.pop();cout << q.front() << endl;q.pop();cout << q.front() << endl;q.pop();cout << q.front() << endl;q.pop();if ( q.empty() ) {cout << "Queue is empty" << endl;}}

OUTPUT:-

Size of the queue: 4100200300400Queue is empty