Stacks in C++ with O(1) Time Complexity for Push and Pop Operations

Understanding the Problem

Stacks are a fundamental data structure in computer science, characterized by their Last In, First Out (LIFO) behavior. The core challenge is to implement a stack that supports push and pop operations efficiently, ideally in constant time, O(1).

Stacks are widely used in various applications such as expression evaluation, backtracking algorithms, and function call management in programming languages. A common pitfall is not handling edge cases like popping from an empty stack, which can lead to runtime errors.

Approach

To solve this problem, we need to implement a stack with the following operations:

Push: Add an element to the top of the stack.
Pop: Remove the top element from the stack.
Top: Retrieve the top element without removing it.
IsEmpty: Check if the stack is empty.

We will start with a naive approach using a dynamic array (vector) and then discuss an optimized approach using a linked list.

Naive Approach

The naive approach uses a dynamic array (vector) to store elements. While push and pop operations are generally O(1), resizing the array can lead to O(n) operations. This approach is not optimal for all scenarios.

Optimized Approach

An optimized approach uses a singly linked list, where each node points to the next node. This ensures that push and pop operations are always O(1) since we only need to update pointers.

Algorithm

Here is a step-by-step breakdown of the optimized approach using a linked list:

Create a Node structure to represent each element in the stack.
Maintain a pointer to the top node of the stack.
For the push operation, create a new node and update the top pointer.
For the pop operation, update the top pointer to the next node and delete the old top node.
For the top operation, return the value of the top node.
For the isEmpty operation, check if the top pointer is null.

Code Implementation

#include <iostream>
using namespace std;

// Node structure for the linked list
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

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

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

    // Push operation
    void push(int val) {
        Node* newNode = new Node(val);
        newNode->next = top;
        top = newNode;
    }

    // Pop operation
    void pop() {
        if (isEmpty()) {
            cout << "Stack underflow" << endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    // Top operation
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return top->data;
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }

    // Destructor to clean up memory
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "Top element is " << s.peek() << endl; // Should print 30
    s.pop();
    cout << "Top element is " << s.peek() << endl; // Should print 20
    s.pop();
    s.pop();
    s.pop(); // Should print "Stack underflow"
    return 0;
}

Complexity Analysis

The time complexity for push, pop, and peek operations in the linked list implementation is O(1) because each operation involves a constant number of steps. The space complexity is O(n), where n is the number of elements in the stack.

Edge Cases

Potential edge cases include:

Popping from an empty stack: The implementation handles this by checking if the stack is empty and printing an error message.
Peeking into an empty stack: The implementation handles this by checking if the stack is empty and returning a sentinel value (-1).

Testing

To test the solution comprehensively, consider the following test cases:

Push and pop a single element.
Push multiple elements and pop them in sequence.
Attempt to pop from an empty stack.
Check the top element after various operations.

Using a testing framework like Google Test can help automate and manage these test cases effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the core operations and their requirements.
Think about the data structure that best fits the problem constraints.
Start with a simple solution and iteratively optimize it.
Consider edge cases and how to handle them gracefully.

Practice by solving similar problems and studying different data structures and algorithms to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to implement a stack using a linked list in C++ with O(1) time complexity for push and pop operations. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice, consider the following resources: