How to Implement a Queue Data Structure Using Linked List in C++
This article will explain how to implement a queue data structure using a linked list in C++.
Implement Queue Data Structure Using Singly Linked List in C++
A queue is a data structure that manages its elements in FIFO (first-in-first-out) manner, so the first element added will be the first to be removed from the queue.
Generally, the insertion and removal operations for the queue data structure are referred to as enqueue and dequeue, respectively. An abstract queue can be implemented using different methods and data structures. Usually, the side at which new elements are added is called - front, while the side from which the elements are removed - a back of the queue.
In the following examples, we implement the queue using the singly linked list, which consists of nodes storing the data object and the pointer to the next node. In this case, we chose to represent a data object with a single string object for simplicity, but it’s up to the programmer to design the most optimal node structure.
Next, we can define a class called Queue, which includes three data members: front, back, and size. The former two are self-explanatory, while the latter one denotes the current element count of the queue. There can be two main variants of the queue data structure unbounded and bounded, the former of which can add elements until there’s available memory. On the other hand, a bounded queue is designed to store only a fixed number of elements.
In this article, we design an unbounded queue, but the reader can intuitively develop the bounded one with small modifications in the given code samples. Since we are implementing an unbounded queue from scratch, we need to manage the dynamic memory allocations as the queue grows. Thus, enQueue and deQueue member functions will include new and delete operators. Note that this implementation of the queue is not intended to be an efficient one but rather demonstrates the basic working mechanisms of this data structure in general.
Our Queue has two constructors, one of which takes initializer_list of string values and invokes the enQueue function multiple times to construct a Queue object. Each enQueue invocation increments size member, and if needed, the user of the class can retrieve its value using the getSize function. We also implemented a helper function printNodes to inspect the contents of the given Queue object. This function does not need to be defined in a real-world scenario, but it can be useful for testing and debugging.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
q1.enQueue("Xenial");
q1.enQueue("Bionic");
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Output:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
queue size = 4
/ ------------------------------ /
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Xenial
node 5 - data: Bionic
queue size = 6
The previous Queue class lacks the destructor implementation and the function to remove elements from the queue. These two are defined in the following code snippet, and the corresponding driver code is included in the main function of the program.
The deQueue function is designed to return a string value specific to our implementation. Consequently, this function returns an empty string to denote the queue is empty, and the user is responsible for checking the return value. Meanwhile, the destructor function makes sure all allocated memory is freed before the object goes out of scope.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
string Queue::deQueue() {
if (front == nullptr)
return "";
else {
auto tmp = front->next;
auto data = front->data;
delete front;
front = tmp;
size--;
return data;
}
}
Queue::~Queue() {
struct ListNode *tmp = nullptr;
while (front) {
tmp = front->next;
delete front;
front = tmp;
}
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
auto ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
while (!q1.deQueue().empty())
;
cout << "queue size = " << q1.getSize() << endl;
ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
for (int i = 0; i < 100; ++i) {
q1.enQueue("hello");
}
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Precise
queue size = 3
/ ------------------------------ /
queue size = 0
Queue is empty!
queue size = 100
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook