Stack

A stack is a linear data structure that follows a specific order for adding and removing elements. It’s one of the most fundamental data structures in computer science, characterized by its restricted access pattern where elements can only be added or removed from one end, called the “top” of the stack.

Think of a stack like a pile of plates in a cafeteria – you can only add new plates to the top of the pile, and you can only take plates from the top. This simple concept forms the foundation of many computing operations.

LIFO Concept (Last In, First Out) #

Understanding LIFO #

LIFO stands for “Last In, First Out,” which means:

• The last element added to the stack is the first one to be removed
• Elements are processed in reverse order of their insertion
• Only the topmost element is accessible at any given time

Visual Representation #

Stack Operations:
Push 1 → [1]
Push 2 → [1, 2]
Push 3 → [1, 2, 3]
Pop    → [1, 2]     (3 is removed)
Pop    → [1]        (2 is removed)

Key Stack Operations #

1. Push: Add an element to the top of the stack
2. Pop: Remove and return the top element from the stack
3. Peek/Top: View the top element without removing it
4. isEmpty: Check if the stack is empty
5. Size: Get the number of elements in the stack

Implementation with Lists #

Python Implementation #

class Stack:
    def __init__(self):
        """Initialize an empty stack using a list"""
        self.items = []
    
    def push(self, item):
        """Add an item to the top of the stack"""
        self.items.append(item)
        print(f"Pushed {item} to stack")
    
    def pop(self):
        """Remove and return the top item from the stack"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.items.pop()
        print(f"Popped {item} from stack")
        return item
    
    def peek(self):
        """Return the top item without removing it"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        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 the current stack contents"""
        if self.is_empty():
            print("Stack is empty")
        else:
            print(f"Stack contents (top to bottom): {self.items[::-1]}")

# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display()

print(f"Top element: {stack.peek()}")
stack.pop()
stack.display()

Java Implementation #

import java.util.*;

public class Stack<T> {
    private List<T> items;
    
    public Stack() {
        items = new ArrayList<>();
    }
    
    public void push(T item) {
        items.add(item);
        System.out.println("Pushed " + item + " to stack");
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = items.remove(items.size() - 1);
        System.out.println("Popped " + item + " from stack");
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return items.get(items.size() - 1);
    }
    
    public boolean isEmpty() {
        return items.size() == 0;
    }
    
    public int size() {
        return items.size();
    }
    
    public void display() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
        } else {
            System.out.print("Stack contents (top to bottom): ");
            for (int i = items.size() - 1; i >= 0; i--) {
                System.out.print(items.get(i) + " ");
            }
            System.out.println();
        }
    }
}

Time and Space Complexity #

Time Complexity:

• Push: O(1) – Adding to the end of a list
• Pop: O(1) – Removing from the end of a list
• Peek: O(1) – Accessing the last element
• isEmpty: O(1) – Checking list length
• Size: O(1) – Getting list length

Space Complexity: O(n) where n is the number of elements in the stack

Real-World Use Cases #

1. Function Call Management #

Stacks are fundamental to how programming languages manage function calls through the “call stack”:

def function_a():
    print("Start A")
    function_b()
    print("End A")

def function_b():
    print("Start B")
    function_c()
    print("End B")

def function_c():
    print("Function C")

# Call stack progression:
# 1. function_a() pushed
# 2. function_b() pushed
# 3. function_c() pushed
# 4. function_c() popped (completes)
# 5. function_b() popped (completes)
# 6. function_a() popped (completes)

2. Expression Evaluation and Parsing #

Infix to Postfix Conversion:

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = Stack()
    result = []
    
    for char in expression:
        if char.isalnum():
            result.append(char)
        elif char == '(':
            stack.push(char)
        elif char == ')':
            while not stack.is_empty() and stack.peek() != '(':
                result.append(stack.pop())
            stack.pop()  # Remove '('
        else:  # Operator
            while (not stack.is_empty() and 
                   stack.peek() != '(' and
                   precedence.get(stack.peek(), 0) >= precedence[char]):
                result.append(stack.pop())
            stack.push(char)
    
    while not stack.is_empty():
        result.append(stack.pop())
    
    return ''.join(result)

# Example: "A+B*C" becomes "ABC*+"

3. Parentheses Matching #

def is_balanced(expression):
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:  # Opening bracket
            stack.push(char)
        elif char in pairs.values():  # Closing bracket
            if stack.is_empty():
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return stack.is_empty()

# Examples:
# is_balanced("()[]{}") → True
# is_balanced("([)]") → False

4. Undo Operations #

Many applications use stacks to implement undo functionality:

class TextEditor:
    def __init__(self):
        self.content = ""
        self.history = Stack()
    
    def type_text(self, text):
        self.history.push(self.content)  # Save current state
        self.content += text
    
    def delete_characters(self, count):
        self.history.push(self.content)  # Save current state
        self.content = self.content[:-count]
    
    def undo(self):
        if not self.history.is_empty():
            self.content = self.history.pop()
        else:
            print("Nothing to undo")

5. Browser History Navigation #

Web browsers use stacks to manage back button functionality:

class BrowserHistory:
    def __init__(self):
        self.back_stack = Stack()
        self.forward_stack = Stack()
        self.current_page = None
    
    def visit_page(self, url):
        if self.current_page:
            self.back_stack.push(self.current_page)
        self.current_page = url
        # Clear forward history when visiting new page
        self.forward_stack = Stack()
    
    def go_back(self):
        if not self.back_stack.is_empty():
            self.forward_stack.push(self.current_page)
            self.current_page = self.back_stack.pop()
        else:
            print("Cannot go back")
    
    def go_forward(self):
        if not self.forward_stack.is_empty():
            self.back_stack.push(self.current_page)
            self.current_page = self.forward_stack.pop()
        else:
            print("Cannot go forward")

6. Memory Management #

Operating systems use stacks for:

• Stack memory allocation: Local variables and function parameters
• Stack frames: Managing function call context
• Exception handling: Managing try-catch blocks

7. Algorithm Applications #

Depth-First Search (DFS):

def dfs_iterative(graph, start):
    visited = set()
    stack = Stack()
    stack.push(start)
    
    while not stack.is_empty():
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Process vertex
            
            # Add neighbors to stack
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.push(neighbor)

Backtracking Problems:

• N-Queens problem
• Sudoku solver
• Maze solving
• Permutation generation

Advantages and Disadvantages #

Advantages #

• Simplicity: Easy to understand and implement
• Efficiency: O(1) operations for push, pop, and peek
• Memory efficient: Only stores necessary elements
• Natural recursion support: Mirrors recursive function calls

Disadvantages #

• Limited access: Can only access the top element
• No random access: Cannot access middle elements directly
• Fixed access pattern: Must follow LIFO strictly
• Potential overflow: Limited by available memory

Stack vs Other Data Structures #

Best Practices #

1. Always check for empty stack before popping or peeking
2. Handle exceptions gracefully in production code
3. Consider memory limits for large datasets
4. Use built-in implementations when available (e.g., collections.deque in Python)
5. Document stack usage clearly in complex algorithms
6. Test edge cases like empty stacks and single-element stacks

Conclusion #

Stacks are fundamental data structures that power many core computing concepts. Their LIFO nature makes them perfect for managing temporary data, tracking state changes, and implementing recursive algorithms. While simple in concept, stacks enable complex functionality in everything from programming language interpreters to web browsers to mathematical expression evaluators.

Understanding stacks deeply provides a foundation for more advanced data structures and algorithms, making them essential knowledge for any programmer or computer scientist.