Implementing a Stack Using Linked Lists in C++

When it comes to data structures, a stack is one of the most fundamental concepts you'll encounter in programming. A stack follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. While arrays are commonly used to implement stacks, using linked lists offers some significant advantages, especially in terms of dynamic memory allocation. In this article, we’ll explore how to implement a stack using linked lists in C++, including its definitions, use cases, and actionable insights.

What is a Stack?

A stack is a collection of elements that supports two main operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack.

Additionally, stacks often provide a Peek operation that allows you to view the top element without removing it.

Use Cases for Stacks

Stacks are widely used in various applications, including:

• Function Call Management: In programming, each function call is pushed onto the call stack, which maintains the order of execution.
• Expression Evaluation: Stacks are used to evaluate expressions in programming languages, especially for converting infix expressions to postfix.
• Undo Mechanisms: Many applications use stacks to implement undo features, allowing users to revert to previous states.
• Backtracking Algorithms: Stacks can help in algorithms like depth-first search, where you need to remember the path taken.

Why Use Linked Lists for Stack Implementation?

Implementing a stack using a linked list provides several benefits:

• Dynamic Size: Unlike arrays, linked lists can grow and shrink dynamically, making them more memory efficient.
• No Size Limitations: You won’t have to worry about stack overflow as long as there's available memory.

Key Components of a Linked List Stack

A linked list stack typically consists of nodes, where each node contains:

• A data field to store the value.
• A pointer to the next node in the list.

Implementing a Stack Using Linked Lists in C++

Let’s dive into the actual implementation. Below are the steps to create a stack using linked lists in C++.

Step 1: Define the Node Structure

First, we need to define the structure for our linked list node.

struct Node {
    int data;       // Data field
    Node* next;    // Pointer to the next node

    Node(int val) : data(val), next(nullptr) {} // Constructor
};

Step 2: Create the Stack Class

Next, we’ll create a stack class that manages the linked list.

class Stack {
private:
    Node* top; // Pointer to the top of the stack

public:
    Stack() : top(nullptr) {} // Constructor

    // Push operation
    void push(int value);

    // Pop operation
    int pop();

    // Peek operation
    int peek();

    // Check if stack is empty
    bool isEmpty();

    // Destructor to free memory
    ~Stack();
};

Step 3: Implement the Push Operation

The push operation will insert a new node at the top of the stack.

void Stack::push(int value) {
    Node* newNode = new Node(value); // Create new node
    newNode->next = top; // Link new node to the previous top
    top = newNode; // Update top to the new node
}

Step 4: Implement the Pop Operation

The pop operation will remove and return the top element.

int Stack::pop() {
    if (isEmpty()) {
        throw std::out_of_range("Stack Underflow: Cannot pop from an empty stack.");
    }
    int poppedValue = top->data; // Get the value from the top
    Node* temp = top; // Temporary node to delete
    top = top->next; // Update top
    delete temp; // Free memory
    return poppedValue; // Return popped value
}

Step 5: Implement the Peek Operation

The peek operation allows us to view the top element without removing it.

int Stack::peek() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty: Cannot peek.");
    }
    return top->data; // Return top value
}

Step 6: Implement the isEmpty Method

This method checks if the stack is empty.

bool Stack::isEmpty() {
    return top == nullptr; // Return true if top is null
}

Step 7: Destructor for Memory Management

Lastly, implement the destructor to free memory when the stack is no longer in use.

Stack::~Stack() {
    while (!isEmpty()) {
        pop(); // Pop all elements
    }
}

Complete Code Example

Here’s the complete code for our stack implementation using linked lists:

#include <iostream>
#include <stdexcept>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
    Node* top;

public:
    Stack() : top(nullptr) {}
    void push(int value);
    int pop();
    int peek();
    bool isEmpty();
    ~Stack();
};

void Stack::push(int value) {
    Node* newNode = new Node(value);
    newNode->next = top;
    top = newNode;
}

int Stack::pop() {
    if (isEmpty()) {
        throw std::out_of_range("Stack Underflow: Cannot pop from an empty stack.");
    }
    int poppedValue = top->data;
    Node* temp = top;
    top = top->next;
    delete temp;
    return poppedValue;
}

int Stack::peek() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty: Cannot peek.");
    }
    return top->data;
}

bool Stack::isEmpty() {
    return top == nullptr;
}

Stack::~Stack() {
    while (!isEmpty()) {
        pop();
    }
}

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    std::cout << "Top element: " << s.peek() << std::endl; // Output: 20
    std::cout << "Popped element: " << s.pop() << std::endl; // Output: 20
    std::cout << "Is stack empty? " << (s.isEmpty() ? "Yes" : "No") << std::endl; // Output: No
    return 0;
}

Conclusion

Implementing a stack using linked lists in C++ is a flexible and efficient approach to managing data. This method allows for dynamic memory usage and eliminates the limitations of fixed-size arrays. With a solid understanding of how to create and manipulate stacks, you can leverage this essential data structure in various programming applications. Whether you’re managing function calls, evaluating expressions, or implementing undo features, a linked list stack is a powerful tool in your programming arsenal.

Now that you have a complete implementation, consider experimenting with enhancing functionality, such as adding size tracking or implementing additional error handling. Happy coding!