Stack

A stack is a fundamental linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates - you can only add or remove plates from the top, and the last plate you put on is the first one you'll take off.

Interactive Stack Visualization

Experience the LIFO principle in action! Watch how elements are pushed onto and popped off the stack, and see how the top indicator always points to the most recently added element.

Stack Operations (LIFO - Last In, First Out)

Push (Add to Top)

Add element to top of stack

Pop (Remove from Top)

Remove element from top

Top value: 30

Peek (View Top)

Highlight top element

Stack Visualization

TOP

stack[0]

stack[1]

stack[2]

Stack Height: 3 / 8

Status: 3 elements in stack

Stack Contents (bottom to top): [10, 20, 30]

How Stack Operations Work:

Push (O(1)):

Add a new element to the top of the stack. The last element added becomes the new top.

Pop (O(1)):

Remove and return the top element from the stack. Follows Last-In-First-Out (LIFO) principle.

Peek (O(1)):

View the top element without removing it. Useful for checking what's on top without modifying the stack.

LIFO Principle:

Stacks follow the Last-In-First-Out principle, meaning the last element added (pushed) is the first one to be removed (popped). Think of a stack of plates - you add and remove plates from the top, not the bottom.

Understanding LIFO (Last-In-First-Out)

The Plate Stack Analogy

Imagine a stack of dinner plates in your kitchen:

• Adding plates: You place new plates on top of the stack
• Taking plates: You remove plates from the top, one at a time
• Last plate in: The most recently added plate
• First plate out: That same recent plate is removed first
• Bottom plates: Can't be accessed until top plates are removed

LIFO in Programming

This principle applies to many programming scenarios:

• Function calls: Most recent call executes first
• Undo operations: Last action undone first
• Expression evaluation: Nested operations resolved inside-out
• Browser history: Back button follows LIFO order
• Memory management: Local variables in nested scopes

Common Use Cases

Function Call Stack

When your program calls functions, each call is pushed onto a call stack:

main() → calls funcA() → calls funcB()
Stack: [main, funcA, funcB] ← top

Functions complete in reverse order: funcB finishes first, then funcA, then main.

Undo/Redo Functionality

Text editors and applications use stacks to track user actions:

Actions: Type "Hello" → Delete "o" → Type "p"
Undo Stack: [Type "Hello", Delete "o", Type "p"] ← top

Pressing Undo reverses the most recent action first.

Complexity Analysis

Operation	Time Complexity	Space Complexity	Explanation
Push	O(1)	O(1)	Add element to top in constant time
Pop	O(1)	O(1)	Remove top element in constant time
Peek	O(1)	O(1)	Access top element without removal

Why O(1)? All stack operations only interact with the top element, regardless of how many elements are in the stack. No iteration or searching required!

Stack Class Implementation

Complete stack implementations with push, pop, and peek methods. Each example includes the plate stack analogy in comments and demonstrates both basic operations and practical applications.

 class Stack:
    """
    A Stack implementation using Python list
    Demonstrates LIFO (Last-In-First-Out) principle
    """
    
    def __init__(self):
        """Initialize an empty stack"""
        self.items = []
    
    def push(self, item):
        """
        Add an item to the top of the stack
        Like placing a plate on top of a stack of plates
        
        Time Complexity: O(1)
        Space Complexity: O(1)
        """
        self.items.append(item)
        print(f"Pushed {item} onto stack")
    
    def pop(self):
        """
        Remove and return the top item from the stack
        Like taking the top plate from a stack of plates
        
        Time Complexity: O(1)
        Space Complexity: O(1)
        
        Raises:
            IndexError: If stack is empty
        """
        if self.is_empty():
            raise IndexError("Cannot pop from empty stack")
        
        item = self.items.pop()
        print(f"Popped {item} from stack")
        return item
    
    def peek(self):
        """
        Return the top item without removing it
        Like looking at the top plate without taking it
        
        Time Complexity: O(1)
        Space Complexity: O(1)
        
        Raises:
            IndexError: If stack is empty
        """
        if self.is_empty():
            raise IndexError("Cannot peek at empty stack")
        
        return self.items[-1]
    
    def is_empty(self):
        """Check if the stack is empty"""
        return len(self.items) == 0
    
    def size(self):
        """Return the number of items in the stack"""
        return len(self.items)
    
    def display(self):
        """Display stack contents from top to bottom"""
        if self.is_empty():
            return "Empty Stack"
        
        print("Stack (top to bottom):")
        for i in range(len(self.items) - 1, -1, -1):
            print(f"  [{i}] {self.items[i]}")

# Example usage demonstrating LIFO principle
def demonstrate_lifo():
    """Demonstrate how stack follows LIFO principle"""
    stack = Stack()
    
    print("=== Demonstrating LIFO Principle ===")
    print("Think of this like stacking plates...")
    
    # Push items (like stacking plates)
    print("\nStacking plates:")
    stack.push("Plate 1 (first)")
    stack.push("Plate 2 (second)")  
    stack.push("Plate 3 (third)")
    
    print(f"\nTop plate is: {stack.peek()}")
    print(f"Stack size: {stack.size()}")
    
    # Pop items (like taking plates off)
    print("\nTaking plates off (LIFO order):")
    while not stack.is_empty():
        plate = stack.pop()
        print(f"Took: {plate}")
    
    print(f"\nStack is now empty: {stack.is_empty()}")

# Function call stack simulation
def recursive_function_demo(n):
    """Demonstrate how function calls use a stack"""
    print(f"Calling function with n = {n}")
    
    if n <= 1:
        print(f"Base case reached with n = {n}")
        return 1
    else:
        result = n * recursive_function_demo(n - 1)
        print(f"Returning {result} for n = {n}")
        return result

if __name__ == "__main__":
    # Basic stack operations
    demonstrate_lifo()
    
    print("\n" + "="*50 + "\n")
    
    # Function call stack example
    print("=== Function Call Stack Example ===")
    print("Computing factorial of 4:")
    factorial_4 = recursive_function_demo(4)
    print(f"\nFinal result: {factorial_4}") 
 import java.util.ArrayList;
import java.util.EmptyStackException;

/**
 * A Stack implementation using ArrayList
 * Demonstrates LIFO (Last-In-First-Out) principle
 */
public class Stack<T> {
    private ArrayList<T> items;
    
    /**
     * Initialize an empty stack
     */
    public Stack() {
        this.items = new ArrayList<>();
    }
    
    /**
     * Add an item to the top of the stack
     * Like placing a plate on top of a stack of plates
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     */
    public void push(T item) {
        items.add(item);
        System.out.println("Pushed " + item + " onto stack");
    }
    
    /**
     * Remove and return the top item from the stack
     * Like taking the top plate from a stack of plates
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws EmptyStackException if stack is empty
     */
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        
        T item = items.remove(items.size() - 1);
        System.out.println("Popped " + item + " from stack");
        return item;
    }
    
    /**
     * Return the top item without removing it
     * Like looking at the top plate without taking it
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws EmptyStackException if stack is empty
     */
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        
        return items.get(items.size() - 1);
    }
    
    /**
     * Check if the stack is empty
     */
    public boolean isEmpty() {
        return items.isEmpty();
    }
    
    /**
     * Return the number of items in the stack
     */
    public int size() {
        return items.size();
    }
    
    /**
     * Display stack contents from top to bottom
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("Empty Stack");
            return;
        }
        
        System.out.println("Stack (top to bottom):");
        for (int i = items.size() - 1; i >= 0; i--) {
            System.out.println("  [" + i + "] " + items.get(i));
        }
    }
    
    /**
     * Demonstrate how stack follows LIFO principle
     */
    public static void demonstrateLIFO() {
        System.out.println("=== Demonstrating LIFO Principle ===");
        System.out.println("Think of this like stacking plates...");
        
        Stack<String> stack = new Stack<>();
        
        // Push items (like stacking plates)
        System.out.println("\nStacking plates:");
        stack.push("Plate 1 (first)");
        stack.push("Plate 2 (second)");
        stack.push("Plate 3 (third)");
        
        System.out.println("\nTop plate is: " + stack.peek());
        System.out.println("Stack size: " + stack.size());
        
        // Pop items (like taking plates off)
        System.out.println("\nTaking plates off (LIFO order):");
        while (!stack.isEmpty()) {
            String plate = stack.pop();
            System.out.println("Took: " + plate);
        }
        
        System.out.println("\nStack is now empty: " + stack.isEmpty());
    }
    
    /**
     * Recursive function to demonstrate function call stack
     */
    public static int recursiveFunctionDemo(int n) {
        System.out.println("Calling function with n = " + n);
        
        if (n <= 1) {
            System.out.println("Base case reached with n = " + n);
            return 1;
        } else {
            int result = n * recursiveFunctionDemo(n - 1);
            System.out.println("Returning " + result + " for n = " + n);
            return result;
        }
    }
    
    public static void main(String[] args) {
        // Basic stack operations
        demonstrateLIFO();
        
        System.out.println("\n" + "=".repeat(50) + "\n");
        
        // Function call stack example
        System.out.println("=== Function Call Stack Example ===");
        System.out.println("Computing factorial of 4:");
        int factorial4 = recursiveFunctionDemo(4);
        System.out.println("\nFinal result: " + factorial4);
    }
} 
 #include <iostream>
#include <vector>
#include <stdexcept>
#include <string>

/**
 * A Stack implementation using std::vector
 * Demonstrates LIFO (Last-In-First-Out) principle
 */
template<typename T>
class Stack {
private:
    std::vector<T> items;
    
public:
    /**
     * Add an item to the top of the stack
     * Like placing a plate on top of a stack of plates
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     */
    void push(const T& item) {
        items.push_back(item);
        std::cout << "Pushed " << item << " onto stack" << std::endl;
    }
    
    /**
     * Remove and return the top item from the stack
     * Like taking the top plate from a stack of plates
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws std::runtime_error if stack is empty
     */
    T pop() {
        if (isEmpty()) {
            throw std::runtime_error("Cannot pop from empty stack");
        }
        
        T item = items.back();
        items.pop_back();
        std::cout << "Popped " << item << " from stack" << std::endl;
        return item;
    }
    
    /**
     * Return the top item without removing it
     * Like looking at the top plate without taking it
     * 
     * Time Complexity: O(1)
     * Space Complexity: O(1)
     * 
     * @throws std::runtime_error if stack is empty
     */
    T peek() const {
        if (isEmpty()) {
            throw std::runtime_error("Cannot peek at empty stack");
        }
        
        return items.back();
    }
    
    /**
     * Check if the stack is empty
     */
    bool isEmpty() const {
        return items.empty();
    }
    
    /**
     * Return the number of items in the stack
     */
    size_t size() const {
        return items.size();
    }
    
    /**
     * Display stack contents from top to bottom
     */
    void display() const {
        if (isEmpty()) {
            std::cout << "Empty Stack" << std::endl;
            return;
        }
        
        std::cout << "Stack (top to bottom):" << std::endl;
        for (int i = items.size() - 1; i >= 0; i--) {
            std::cout << "  [" << i << "] " << items[i] << std::endl;
        }
    }
};

/**
 * Demonstrate how stack follows LIFO principle
 */
void demonstrateLIFO() {
    std::cout << "=== Demonstrating LIFO Principle ===" << std::endl;
    std::cout << "Think of this like stacking plates..." << std::endl;
    
    Stack<std::string> stack;
    
    // Push items (like stacking plates)
    std::cout << "\nStacking plates:" << std::endl;
    stack.push("Plate 1 (first)");
    stack.push("Plate 2 (second)");
    stack.push("Plate 3 (third)");
    
    std::cout << "\nTop plate is: " << stack.peek() << std::endl;
    std::cout << "Stack size: " << stack.size() << std::endl;
    
    // Pop items (like taking plates off)
    std::cout << "\nTaking plates off (LIFO order):" << std::endl;
    while (!stack.isEmpty()) {
        std::string plate = stack.pop();
        std::cout << "Took: " << plate << std::endl;
    }
    
    std::cout << "\nStack is now empty: " << 
                 (stack.isEmpty() ? "true" : "false") << std::endl;
}

/**
 * Recursive function to demonstrate function call stack
 */
int recursiveFunctionDemo(int n) {
    std::cout << "Calling function with n = " << n << std::endl;
    
    if (n <= 1) {
        std::cout << "Base case reached with n = " << n << std::endl;
        return 1;
    } else {
        int result = n * recursiveFunctionDemo(n - 1);
        std::cout << "Returning " << result << " for n = " << n << std::endl;
        return result;
    }
}

int main() {
    // Basic stack operations
    demonstrateLIFO();
    
    std::cout << "\n" << std::string(50, '=') << "\n" << std::endl;
    
    // Function call stack example
    std::cout << "=== Function Call Stack Example ===" << std::endl;
    std::cout << "Computing factorial of 4:" << std::endl;
    int factorial4 = recursiveFunctionDemo(4);
    std::cout << "\nFinal result: " << factorial4 << std::endl;
    
    return 0;
} 

Key Takeaways

Stack Advantages

• Simple & Efficient: All operations are O(1)
• Memory Efficient: No complex pointer management
• Natural LIFO: Perfect for recursive and nested scenarios
• Easy to Implement: Can use arrays or linked lists
• Safe Access: Only top element is accessible

When to Use Stacks

• Function Call Management: Automatic by programming languages
• Expression Parsing: Mathematical expressions, parentheses matching
• Undo Operations: Text editors, drawing applications
• Backtracking Algorithms: Maze solving, depth-first search
• Memory Management: Local variable scoping