Stack Data Structure Using Linked List in C++
This article will explain how to implement a stack data structure using a linked list in C++.
Implement Stack Data Structure Using Singly Linked List in C++
Stack is an abstract data structure frequently utilized in programs, the most familiar use cases of them being the program stack memory.
This abstract data type has two core operations: push and pop. The former conducts the element insertion on top of the other elements, and the latter removes the most recent element from the stack.
A stack is classified as LIFO (last in, first out) data structure. The stack can be implemented with different methods, but we will construct it from a singly linked list in this article.
Notice that a stack only needs to keep track of the topmost element as it’s where the modifications happen. Otherwise, it’s essentially a sequential collection of data that may or may not have a fixed capacity. The latter is dependent on the design decision which the programmer makes.
The following code snippets implement a stack that can grow without predefined capacity limits. At first, we define a node of a singly linked list and typedef it as ListNode. Then we declare a Stack class and include only one data member to track the top of the list.
In this example, we will only implement push and printNodes functions. push member function operates similar to the insertion operation for the singly linked list, except that it adds every new element at the head of the list.
Though our Stack class has the constructor that initializes the first element, this poor design choice is only taken to simplify the example code for this introductory article.
On the other hand, the printNodes member function is not the essential function for the stack data type, but it makes demonstration easier. It helps us verify our implementation works as intended.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void printNodes();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
The previous code lacks the pop operation, which is necessary for a stack data structure to function properly. Since we implement a boundless stack and only care about the simplicity of the examples, the memory allocations are managed on-demand. Every pop operation invokes delete to free up the memory held by the previous element on top. In a real-world scenario, one should prefer to limit the capacity of the stack or allocate some memory in advance for better performance.
Finally, we need to have a destructor that frees the object after it goes out of scope. The destructor function iterates from the top element until nullptr is found, which denotes the end of the stack.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void pop();
void printNodes();
~Stack();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::pop() {
auto tmp = top->next;
delete top;
top = tmp;
}
Stack::~Stack() {
struct ListNode *tmp = nullptr;
while (top) {
tmp = top->next;
delete top;
top = tmp;
}
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
cout << "/ ------------------------------ / " << endl;
s1.pop();
s1.pop();
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
/ ------------------------------ /
node 0 - data: Quantal
node 1 - data: Precise
node 2 - data: Xenial
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