Data Structures

Stack Implementation Using Linked List with C++ Example

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 Implementation using Linked List
Stack Implementation using Linked List
/**
 * 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()

  1. Create the new node
  2. Link the top node after this new node
  3. 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.

Empty stack using linked list
Initial Stack
Stack after push(10)
Stack after push(10)
Stack after push(20)
After push(20)
Stack after push(30)
After push(30)

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

  1. Return if the Stack is empty, proceed otherwise
  2. Retrieve the element on the Top
  3. Remember the Top node in a temporary pointer
  4. Change the Top to point the next Node
  5. 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.

Example stack using linked list
Initial Stack
Stack after the pop() of element 30
Stack after the pop() of element 30
Stack after the pop() of element 20
After the pop() of element 20
Stack after the pop() of element 10
After the pop() of element 10

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.

StackLinked 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.,
Difference between Stack and Linked List
Copyright copyright 2024 Simplerize