Queue Implementation in C++

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.

Practice this problem

Queue Implementation using an array:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#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();

if (q.isEmpty()) {

cout << "The queue is empty\n";

}

else {

cout << "The queue is not empty\n";

}

return 0;

}

Download Run Code

Output:

Inserting 1
Inserting 2
Inserting 3
The front element is 1
Removing 1
Inserting 4
The queue size is 3
Removing 2
Removing 3
Removing 4
The queue is empty

The time complexity of all the above queue operations is O(1).

Using std::queue:

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.

std::queue

#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;

}

Download Run Code

std::list

#include <iostream>

#include <list>

using namespace std;

// Queue implementation in C++ using `std::list`

int main()

{

list<string> q;

q.push_back("A"); // Insert `A` into the queue

q.push_back("B"); // Insert `B` into the queue

q.push_back("C"); // Insert `C` into the queue

q.push_back("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_front(); // removing the front element (`A`)

q.pop_front(); // 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;

}

Download Run Code

Output:

The queue size is 4
The front element is A
The rear element is D
The queue size is 2
The queue is not empty

Also See:

Queue Implementation in Java

Queue Implementation in Python

Queue Implementation in C++

std::queue

std::list

Share this: