Queue Implementation using Templates in C++

In the previous post, we have discussed the C++ implementation of a queue data structure using class and standard libraries. This article will make the class code generic by using C++ templates to support all data types.

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

#include <iostream>

#include <cstdlib>

using namespace std;

// Define the default capacity of the queue

#define SIZE 10

// A class to represent a queue

template <class X>

class queue

{

X *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

void dequeue();

void enqueue(X x);

X peek();

int size();

bool isEmpty();

bool isFull();

};

// Constructor to initialize a queue

template <class X>

queue<X>::queue(int size)

{

arr = new X[size];

capacity = size;

front = 0;

rear = -1;

count = 0;

}

// Utility function to dequeue the front element

template <class X>

void queue<X>::dequeue()

{

// check for queue underflow

if (isEmpty())

{

cout << "Underflow\nProgram Terminated\n";

exit(EXIT_FAILURE);

}

cout << "Removing " << arr[front] << endl;

front = (front + 1) % capacity;

count--;

}

// Utility function to add an item to the queue

template <class X>

void queue<X>::enqueue(X 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

template <class X>

X queue<X>::peek()

{

if (isEmpty())

{

cout << "UnderFlow\nProgram Terminated\n";

exit(EXIT_FAILURE);

}

return arr[front];

}

// Utility function to return the size of the queue

template <class X>

int queue<X>::size() {

return count;

}

// Utility function to check if the queue is empty or not

template <class X>

bool queue<X>::isEmpty() {

return (size() == 0);

}

// Utility function to check if the queue is full or not

template <class X>

bool queue<X>::isFull() {

return (size() == capacity);

}

int main()

{

// create a queue of capacity 4

queue<string> q(4);

q.enqueue("a");

q.enqueue("b");

q.enqueue("c");

cout << "The front element is " << q.peek() << endl;

q.dequeue();

q.enqueue("d");

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 a
Inserting b
Inserting c
The front element is a
Removing a
Inserting d
The queue size is 3
Removing b
Removing c
Removing d
The queue is empty

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

Queue Implementation using Templates in C++

Share this: