Prefer the Linked List for Stack implementation in order to operate with dynamic data. Firstly, define a node structure for Linked List and initialize a Top pointer with NULL. Then, implement the push, pop, and peek operations.
1. Stack Representation using Linked List
See an example for the Linked list implementation of Stack. This consists of 3 nodes while the Top points to the node (30)
/**
* Stack Node Representation
*/
struct Node {
int element;
Node* next;
};
// Stack
Node* top = NULL;
2. Implementation of Stack using Linked List in C++
Here is a C++ example program of how Stack is implemented using Linked list. This is an object-oriented implementation that encapsulates the stack using class.
/**
* C++ example to demonstrate Stack implementation using Linked List
*/
#include <iostream>
using namespace std;
/**
* Stack Node Representation
*/
struct Node {
int element;
Node* next;
};
/**
* Stack implementation using Linked List
*/
class Stack
{
private:
// Stack
Node* top;
public:
// Constructor
Stack() : top(NULL) {}
// Check if the Stack is empty
bool isEmpty();
// Returns the top element without deleting
int peek();
// Push the new element to Stack
void push(int element);
// Pop the element from Stack
int pop();
// Print the Stack
void print(string msg);
};
bool Stack::isEmpty() {
if (top == NULL) {
cout << "Stack is Empty" << endl;
return true;
}
return false;
}
int Stack::peek() {
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
return top->element;
}
void Stack::push(int element) {
// Step 1. Create the new node
Node* node = new Node();
if (node == NULL) {
cout << "System out of memory" << endl;
throw std::runtime_error("system out of memory");
}
node->element = element;
// Step 2. Link the top node after this new node
node->next = top;
// Step 3. Change the Top to point the new node
top = node;
}
int Stack::pop() {
// Step 1. Return if the Stack is empty, proceed otherwise
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
// Step 2. Retrieve the element on Top
int element = top->element;
// Step 3. Remember the Top node in a temporary pointer
Node* tmp = top;
// Step 4. Change the Top to point the next Node
top = top->next;
// Step 5. Delete the node stored in temporary pointer
delete tmp;
return element;
}
void Stack::print(string msg) {
cout << msg << endl;
if (isEmpty()) {
return;
}
cout << top->element << " <-- top" << endl;
for (Node* node=top->next; node != NULL; node = node->next) {
cout << node->element << endl;
}
}
// The main function to begin the execution
int main()
{
// Create a Stack
Stack stack;
// Push the elements (10, 20, 30, 40 and 50)
try {
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.print("Stack after inserting 10 20 30 and 40");
stack.push(50);
stack.print("Stack after pushing 50");
} catch (const std::exception& e) {
cout << "Push: exception received: " << e.what() << endl;
}
// Get the peek element
try {
int element = stack.peek();
cout << "Peek element returned " << element << endl;
} catch (const std::exception& e) {
cout << "Peek: exception received: " << e.what() << endl;
}
// Pop the elements from Stack
try {
int element = stack.pop(); // 50
cout << "Pop element returned " << element << endl;
element = stack.pop(); // 40
cout << "Pop element returned " << element << endl;
stack.print("Stack after poping two elements");
// Now try poping elements until we get stack underflow
stack.pop(); // 30
stack.pop(); // 20
stack.pop(); // 10
stack.pop(); // expecting exception "stack underflow"
} catch (const std::exception& e) {
cout << "Pop: exception received: " << e.what() << endl;
}
}
Output
Stack after inserting 10 20 30 and 40
40 <-- top
30
20
10
Stack after pushing 50
50 <-- top
40
30
20
10
Peek element returned 50
Pop element returned 50
Pop element returned 40
Stack after poping two elements
30 <-- top
20
10
Stack is Empty
Pop: exception received: stack underflow
Also, read the Stack Implementation using Array
In addition, you can look at the C program to implement the Stack using Linked List
3. Stack Operations
The key operations in the Stack are push and pop.
3.1. Stack push with Linked List
Push operation inserts a new element into the top of the Stack. Also, change the Top to point to the new element.
Algorithm for Stack push()
- Create the new node
- Link the top node after this new node
- Change the Top to point to the new node
Code snippet
void Stack::push(int element) {
// Step 1. Create the new node
Node* node = new Node();
if (node == NULL) {
cout << "System out of memory" << endl;
throw std::runtime_error("system out of memory");
}
node->element = element;
// Step 2. Link the top node after this new node
node->next = top;
// Step 3. Change the Top to point the new node
top = node;
}
Example for Stack push operation
Firstly, make sure that the stack is not full. The initial stack is empty and the Top is set to NULL. However, the push operation follows the common procedure irrespective of whether the stack is empty or not. Link the Top node next to the new node and then change the Top pointer to the new node.
3.2. Stack pop with Linked List
Pop operation removes an element from the top of the Stack. Also, change the Top to point to the next element.
Algorithm for Stack pop()
- Return if the Stack is empty, proceed otherwise
- Retrieve the element on the Top
- Remember the Top node in a temporary pointer
- Change the Top to point the next Node
- Delete the node stored in the temporary pointer
Code snippet
int Stack::pop() {
// Step 1. Return if the Stack is empty, proceed otherwise
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
// Step 2. Retrieve the element on the Top
int element = top->element;
// Step 3. Remember the Top node in a temporary pointer
Node* tmp = top;
// Step 4. Change the Top to point the next Node
top = top->next;
// Step 5. Delete the node stored in temporary pointer
delete tmp;
return element;
}
Example for Stack pop operation
Firstly, ensure that the Stack is not empty to perform the pop operation. Then, retrieve the element on the Top and change the Top to point to the next node. The Top points to NULL as soon as the last element is removed.
4. When to implement Stack by using Linked List
Implementing stacks using a linked list is the preferred choice when the data is dynamic and not limited. In addition, all the pros and cons of Linked List also apply to the Stack.
4.1. Advantages and Disadvantages
Pros
- Linked list based Stack implementation is useful to operate with dynamic data.
- Effective use of memory since the linked list grows and shrinks based on the data.
Cons
- However, it requires additional memory to store the links.
- Also, it works slower than Array implementation. Unlike the array, a linked list uses non-continuous memory locations. So, it is not cache-friendly for the CPU.
Furthermore, see the comparison of Linked List Stack vs Array Stack
5. Frequently Asked Questions (FAQ)
5.1. Is stack a linked list?
No. Stack mimics the real-life stacks and follows the LIFO (Last In First Out) principle. In contrast, Linked List is a linear structure that allows insertion and deletion at any position. However, Stack can be built using the linked list by including the LIFO principles.
5.2. Can stack be implemented using linked List?
Yes. Stack follows the LIFO (Last In First Out) principle whereas the Linked List allows insertion and deletion at any position. So, the insert and delete operations must be restricted to one end of the linked list. For example, look at the above program to implement the stack using the linked list.
5.3. Linked List and Stack Difference
The key difference between the stack and linked list is the order of insertions and deletions. A stack follows the Last In First Out (LIFO) order whereas the linked list allows insertion and deletion anywhere.
| Stack | Linked List |
| A stack is an abstract data type restricted to follow the LIFO order for insertion and deletion. | In contrast, a Linked List is a linear data structure and does not follow any order for insertion/deletion. |
| Specifically used for processing nested structures such as recursive operations. | Broadly used for linear structures and helps to build other data structures. In fact, a stack can be built using the linked list. |
| Mimics real-life stacks such as a stack of physical disks. So, the topmost disk must be removed first. | A linked list is like a chain where we can place or remove an item anywhere in the chain |
| So, a stack supports limited operations which include push, pop, and peek. | Whereas, the linked list supports many operations such as insert, update, delete, search, sort, traverse, etc., |