Stacks in Data Structures

Stacks in Data Structures: Push & Pop with Undo/Redo Example

Push & Pop with Undo/Redo Example

In the world of computer science and programming, data structures form the foundation of efficient algorithm design. Among these fundamental structures, the stack stands out as one of the most elegant and widely-used concepts. Whether you’re browsing web pages, writing code in an editor, or executing function calls in a program, stacks are working behind the scenes to make it all possible.

This comprehensive guide will take you through everything you need to know about stacks, from basic concepts to real-world applications, with a special focus on the popular undo/redo functionality that we use every day.

What is a Stack?

A stack is a linear data structure that follows a specific order for its operations. Imagine a stack of plates in your kitchen—you can only add a new plate on top, and when you need a plate, you take one from the top. You cannot remove a plate from the middle or bottom without first removing all the plates above it. This is precisely how a stack data structure works in computer science.

            Key Principle: Stacks follow the LIFO (Last In, First Out) principle, meaning the last element added to the stack will be the first one to be removed. Think of it as a “first in, last out” mechanism.
        

Visual Representation of a Stack

Element 4 (Top)

Element 3

Element 2

Element 1 (Bottom)

↑ Push (Add) | Pop (Remove) ↓

Core Operations of a Stack

A stack supports several fundamental operations that define its behavior. Understanding these operations is crucial for implementing and using stacks effectively.

1. Push Operation

The push operation adds an element to the top of the stack. When you push an element, it becomes the new top element, and the stack size increases by one. This operation has a time complexity of O(1), making it extremely efficient.

2. Pop Operation

The pop operation removes and returns the top element from the stack. After a pop operation, the element below becomes the new top. If you try to pop from an empty stack, it results in a stack underflow error. Like push, pop also operates in O(1) time.

3. Peek (or Top) Operation

The peek operation returns the top element without removing it from the stack. This allows you to inspect what’s at the top without modifying the stack structure.

4. isEmpty Operation

The isEmpty operation checks whether the stack contains any elements. It returns true if the stack is empty and false otherwise.

5. Size Operation

The size operation returns the number of elements currently in the stack.

Operation	Description	Time Complexity
Push	Add element to top	O(1)
Pop	Remove element from top	O(1)
Peek	View top element	O(1)
isEmpty	Check if stack is empty	O(1)
Size	Get number of elements	O(1)

Implementation of a Stack

Stacks can be implemented using arrays or linked lists. Here’s a simple implementation using JavaScript that demonstrates the core concepts:

class Stack {
    constructor() {
        this.items = [];
    }
    
    // Push element to stack
    push(element) {
        this.items.push(element);
    }
    
    // Pop element from stack
    pop() {
        if (this.isEmpty()) {
            return “Stack is empty”;
        }
        return this.items.pop();
    }
    
    // Peek at top element
    peek() {
        if (this.isEmpty()) {
            return “Stack is empty”;
        }
        return this.items[this.items.length – 1];
    }
    
    // Check if stack is empty
    isEmpty() {
        return this.items.length === 0;
    }
    
    // Get stack size
    size() {
        return this.items.length;
    }
}
        

Interactive Stack Demo

Try Push and Pop Operations

Stack is empty

Status: Stack is empty | Size: 0

Real-World Application: Undo/Redo Functionality

One of the most practical and widely-used applications of stacks is implementing undo and redo functionality in text editors, graphics programs, and various software applications. This feature allows users to reverse their recent actions and restore previous states, significantly improving user experience and productivity.

How Undo/Redo Works with Stacks

The undo/redo mechanism uses two stacks:

Undo Stack: Stores the history of actions performed by the user
Redo Stack: Stores actions that have been undone and can be reapplied

When a user performs an action (like typing text), that action is pushed onto the undo stack. When the user clicks undo, the most recent action is popped from the undo stack and pushed onto the redo stack. If the user then clicks redo, the action is popped from the redo stack and pushed back onto the undo stack.

            Important: When a new action is performed after an undo, the redo stack is cleared. This prevents inconsistent states where redone actions might conflict with new actions.
        

Interactive Undo/Redo Demo

Text Editor with Undo/Redo

Undo Stack: Empty
Redo Stack: Empty

Undo/Redo Implementation

class UndoRedoManager {
    constructor() {
        this.undoStack = [];
        this.redoStack = [];
    }
    
    // Perform new action
    executeAction(action) {
        this.undoStack.push(action);
        this.redoStack = []; // Clear redo stack
    }
    
    // Undo last action
    undo() {
        if (this.undoStack.length > 0) {
            let action = this.undoStack.pop();
            this.redoStack.push(action);
            return action;
        }
        return null;
    }
    
    // Redo last undone action
    redo() {
        if (this.redoStack.length > 0) {
            let action = this.redoStack.pop();
            this.undoStack.push(action);
            return action;
        }
        return null;
    }
}
        

Other Real-World Applications of Stacks

Beyond undo/redo functionality, stacks are used in numerous other applications:

1. Function Call Stack

When a program executes functions, the system uses a call stack to keep track of function calls. Each time a function is called, its execution context is pushed onto the stack. When the function completes, its context is popped off.

2. Expression Evaluation

Stacks are essential for evaluating mathematical expressions and converting between infix, prefix, and postfix notations. Compilers use stacks to parse and evaluate expressions in code.

3. Browser History

Web browsers use stacks to implement the back button functionality. Each visited page is pushed onto the stack, and clicking back pops the most recent page.

4. Backtracking Algorithms

Many algorithms, such as maze solving, game state exploration, and puzzle solving, use stacks to keep track of paths and enable backtracking to previous states.

5. Syntax Checking

Compilers and text editors use stacks to check for balanced parentheses, brackets, and braces in code. Opening symbols are pushed onto the stack, and closing symbols pop them off.

Advantages and Limitations

Advantages of Stacks

Simple and easy to implement
Efficient O(1) time complexity for push and pop operations
Useful for managing function calls and recursion
Natural fit for problems requiring LIFO order
Memory efficient when implemented properly

Limitations of Stacks

Limited access—only the top element is directly accessible
Fixed size in array-based implementations (can cause overflow)
Not suitable for searching or accessing middle elements
Requires careful management to avoid stack overflow or underflow

Best Practices for Using Stacks

To effectively use stacks in your programs, consider these best practices:

Always check for empty stacks: Before popping or peeking, verify the stack isn’t empty to prevent errors
Choose the right implementation: Use arrays for simple cases and linked lists when dynamic sizing is important
Consider memory constraints: Be mindful of stack size limits, especially in recursive algorithms
Document stack usage: Clearly document what each stack stores and its purpose in your code
Handle edge cases: Plan for empty stacks, full stacks, and invalid operations

Conclusion

Stacks are fundamental data structures that power countless applications we use daily. From the undo button in your text editor to the function calls in every program you run, stacks work silently behind the scenes to make computing efficient and intuitive. Understanding how stacks work—particularly the push and pop operations—is essential for any programmer or computer science student.

The undo/redo example demonstrates how a simple data structure can enable powerful user experiences. By maintaining two stacks and carefully managing state transitions, we can create robust systems that allow users to explore, experiment, and correct their actions without fear.

As you continue your journey in programming and data structures, you’ll find stacks appearing in unexpected places. Whether you’re implementing a compiler, designing an algorithm, or building a user interface, the stack’s elegant simplicity and powerful capabilities make it an indispensable tool in your programming toolkit.

            Key Takeaway: Master the stack, and you master a fundamental building block of computer science. Its LIFO principle, combined with efficient O(1) operations, makes it perfect for managing sequential operations, tracking history, and enabling reversible actions in software applications.
        

Also check: Arrays Explained with Real-Life Examples