A queue is a linear data structure that serves as a container of objects that are inserted and removed according to the FIFO (First–In, First–Out) principle.
Queue has three main operations: enqueue, dequeue, and peek. We have already covered these operations and C implementation of queue data structure using an array and linked list. In this post, we will cover queue implementation in C++ using class and STL.
The following queue implementation in C++ covers the following operations:
- Enqueue: Inserts a new element at the rear of the queue.
- Dequeue: Removes the front element of the queue and returns it.
- Peek: Returns the front element present in the queue without dequeuing it.
- IsEmpty: Checks if the queue is empty.
- IsFull: Checks if the queue is full.
- Size: Returns the total number of elements present in the queue.
Queue Implementation using an array (github):
#include <iostream>
#include <cstdlib>
using namespace std;
// Define the default capacity of a queue
#define SIZE 1000
// A class to store a queue
class Queue
{
int *arr; // array to store queue elements
int capacity; // maximum capacity of the queue
int front; // front points to the front element in the queue (if any)
int rear; // rear points to the last element in the queue
int count; // current size of the queue
public:
Queue(int size = SIZE); // constructor
~Queue(); // destructor
int dequeue();
void enqueue(int x);
int peek();
int size();
bool isEmpty();
bool isFull();
};
// Constructor to initialize a queue
Queue::Queue(int size)
{
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
// Destructor to free memory allocated to the queue
Queue::~Queue() {
delete[] arr;
}
// Utility function to dequeue the front element
int Queue::dequeue()
{
// check for queue underflow
if (isEmpty())
{
cout << "Underflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
int x = arr[front];
cout << "Removing " << x << endl;
front = (front + 1) % capacity;
count--;
return x;
}
// Utility function to add an item to the queue
void Queue::enqueue(int item)
{
// check for queue overflow
if (isFull())
{
cout << "Overflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
cout << "Inserting " << item << endl;
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
// Utility function to return the front element of the queue
int Queue::peek()
{
if (isEmpty())
{
cout << "Underflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}
return arr[front];
}
// Utility function to return the size of the queue
int Queue::size() {
return count;
}
// Utility function to check if the queue is empty or not
bool Queue::isEmpty() {
return (size() == 0);
}
// Utility function to check if the queue is full or not
bool Queue::isFull() {
return (size() == capacity);
}
int main()
{
// create a queue of capacity 5
Queue q(5);
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
cout << "The front element is " << q.peek() << endl;
q.dequeue();
q.enqueue(4);
cout << "The queue size is " << q.size() << endl;
q.dequeue();
q.dequeue();
q.dequeue();
if (q.isEmpty()) {
cout << "The queue is empty\n";
}
else {
cout << "The queue is not empty\n";
}
return 0;
}The time complexity of all the above queue operations is O(1).
Queue using Singly Linked List Implementation
Next we will implement a queue data structure using singly linked list data structure.
Linked List Implementation for int Queue (github):
#include <iostream>
using namespace std;
class Queue {
private:
// Node structure to represent each element in the queue
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {} // Constructor to initialize node
};
Node* front; // Pointer to the front of the queue
Node* rear; // Pointer to the rear of the queue
public:
// Constructor to initialize an empty queue
Queue() : front(nullptr), rear(nullptr) {}
// Destructor to clean up memory
~Queue() {
while (front) {
Node* temp = front;
front = front->next;
delete temp;
}
}
// Enqueue method to insert an element at the rear of the queue
void enqueue(int val) {
Node* temp = new Node(val); // Create a new node with the value
if (rear == nullptr) { // Queue is empty
front = rear = temp;
} else {
rear->next = temp;
rear = temp;
}
}
// Dequeue method to remove an element from the front of the queue
void dequeue() {
if (front == nullptr) { // Queue is empty
cout << "Queue is empty!" << endl;
return;
}
Node* temp = front;
cout << "Element deleted from queue: " << front->data << endl;
front = front->next;
if (front == nullptr) { // If queue becomes empty after dequeue
rear = nullptr;
}
delete temp;
}
// Display method to show all elements in the queue
void display() const {
if (front == nullptr) { // Queue is empty
cout << "Queue is empty" << endl;
return;
}
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Queue q;
cout << "Queue Created:" << endl;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.display();
q.dequeue();
cout << "Queue after one deletion:" << endl;
q.display();
return 0;
}Linked List Implementation for template class Queue (github):
#include <iostream>
using namespace std;
template <typename T>
class Queue {
private:
// Node structure to represent each element in the queue
struct Node {
T data;
Node* next;
Node(T val) : data(val), next(nullptr) {} // Constructor to initialize node with data
};
Node* front; // Pointer to the front of the queue
Node* rear; // Pointer to the rear of the queue
public:
// Constructor to initialize an empty queue
Queue() : front(nullptr), rear(nullptr) {}
// Destructor to clean up memory
~Queue() {
while (front) {
Node* temp = front;
front = front->next;
delete temp;
}
}
// Enqueue method to insert an element at the rear of the queue
void enqueue(T val) {
Node* temp = new Node(val); // Create a new node with the value
if (rear == nullptr) { // Queue is empty
front = rear = temp;
} else {
rear->next = temp;
rear = temp;
}
}
// Dequeue method to remove an element from the front of the queue
void dequeue() {
if (front == nullptr) { // Queue is empty
cout << "Queue is empty!" << endl;
return;
}
Node* temp = front;
cout << "Element deleted from queue: " << front->data << endl;
front = front->next;
if (front == nullptr) { // If queue becomes empty after dequeue
rear = nullptr;
}
delete temp;
}
// Display method to show all elements in the queue
void display() const {
if (front == nullptr) { // Queue is empty
cout << "Queue is empty" << endl;
return;
}
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
// Queue of integers
Queue<int> intQueue;
cout << "Integer Queue Created:" << endl;
intQueue.enqueue(10);
intQueue.enqueue(20);
intQueue.enqueue(30);
intQueue.enqueue(40);
intQueue.enqueue(50);
intQueue.display();
intQueue.dequeue();
cout << "Integer Queue after one deletion:" << endl;
intQueue.display();
// Queue of strings
Queue<string> stringQueue;
cout << "\nString Queue Created:" << endl;
stringQueue.enqueue("Hello");
stringQueue.enqueue("World");
stringQueue.enqueue("Queue");
stringQueue.display();
stringQueue.dequeue();
cout << "String Queue after one deletion:" << endl;
stringQueue.display();
return 0;
}
Queue: Using std::queue (github):
C++’s STL provides a std::queue template class which is restricted to only enqueue/dequeue operations. It also provides std::list which has push_back and pop_front operations with LIFO semantics. Java’s library contains Queue interface that specifies queue operations.
Approach: To solve the problem follow the below idea:
we maintain two pointers, front, and rear. The front points to the first item of the queue and rear points to the last item.
- enQueue(): This operation adds a new node after the rear and moves the rear to the next node.
- deQueue(): This operation removes the front node and moves the front to the next node.
Follow the below steps to solve the problem:
- Create a class QNode with data members integer data and QNode* next
- A parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as NULL
- Create a class Queue with data members QNode front and rear
- Enqueue Operation with parameter x:
- Initialize QNode* temp with data = x
- If the rear is set to NULL then set the front and rear to temp and return(Base Case)
- Else set rear next to temp and then move rear to temp
- Dequeue Operation:
- If the front is set to NULL return(Base Case)
- Initialize QNode temp with front and set front to its next
- If the front is equal to NULL then set the rear to NULL
- Delete temp from the memory
Below is the Implementation of the above approach:
#include <iostream>
#include <queue>
using namespace std;
// Queue implementation in C++ using `std::queue`
int main()
{
queue<string> q;
q.push("A"); // Insert `A` into the queue
q.push("B"); // Insert `B` into the queue
q.push("C"); // Insert `C` into the queue
q.push("D"); // Insert `D` into the queue
// Returns the total number of elements present in the queue
cout << "The queue size is " << q.size() << endl;
// Prints the front of the queue (`A`)
cout << "The front element is " << q.front() << endl;
// Prints the rear of the queue (`D`)
cout << "The rear element is " << q.back() << endl;
q.pop(); // removing the front element (`A`)
q.pop(); // removing the next front element (`B`)
cout << "The queue size is " << q.size() << endl;
// check if the queue is empty
if (q.empty()) {
cout << "The queue is empty\n";
}
else {
cout << "The queue is not empty\n";
}
return 0;
}