Stacks

Stacks Data Structures Mastery

Stacks & Expression Evaluation

Master the LIFO data structure that powers function calls, expression evaluation, and system operations. Learn stack implementations, applications, and notation conversions.

Stack Implementation in Python

# Stack Implementation using List (Array-based)
class Stack:
    def __init__(self, capacity=None):
        self.items = []
        self.capacity = capacity
    
    # Push operation - O(1) amortized
    def push(self, item):
        if self.is_full():
            raise StackOverflowError("Stack is full!")
        self.items.append(item)
    
    # Pop operation - O(1)
    def pop(self):
        if self.is_empty():
            raise StackUnderflowError("Stack is empty!")
        return self.items.pop()
    
    # Peek operation - O(1)
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def is_full(self):
        return self.capacity is not None and len(self.items) >= self.capacity
    
    def size(self):
        return len(self.items)
    
    # String representation
    def __str__(self):
        return f"Stack: {self.items}"

# Postfix expression evaluation
def evaluate_postfix(expression):
    stack = Stack()
    operators = set(['+', '-', '*', '/', '^'])
    
    for token in expression.split():
        if token not in operators:
            # Token is an operand
            stack.push(float(token))
        else:
            # Token is an operator
            operand2 = stack.pop()
            operand1 = stack.pop()
            
            if token == '+':
                result = operand1 + operand2
            elif token == '-':
                result = operand1 - operand2
            elif token == '*':
                result = operand1 * operand2
            elif token == '/':
                result = operand1 / operand2
            elif token == '^':
                result = operand1 ** operand2
            
            stack.push(result)
    
    return stack.pop()

# Example: Evaluate "5 1 2 + 4 * + 3 -"
result = evaluate_postfix("5 1 2 + 4 * + 3 -")
print(f"Result: {result}")  # Output: 14

# Balanced parentheses checker
def is_balanced(parentheses):
    stack = Stack()
    matching = {')': '(', '}': '{', ']': '['}
    
    for char in parentheses:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != matching[char]:
                return False
    
    return stack.is_empty()

1. Stack Implementation

Stack Concepts (LIFO – Last In First Out)
Array-Based Stack Implementation
Linked List-Based Stack Implementation
Push Operation – Adding Elements
Pop Operation – Removing Elements
Peek/Top Operation – View Top Element
Stack Overflow & Underflow Conditions
Time Complexity Analysis
Space Complexity Analysis
Comparison: Array vs Linked List Stacks
Dynamic Stack Resizing
Error Handling in Stack Operations

2. Applications of Stacks

Function Call Stack (Call Stack)
Undo/Redo Operations in Applications
Balanced Parentheses Checking
Expression Evaluation (Postfix/Prefix)
Browser Back/Forward Navigation
Reversing a String using Stack
Tower of Hanoi Problem
Depth-First Search (DFS) in Graphs
Syntax Parsing in Compilers
Memory Management – Stack Memory
Backtracking Algorithms
Maze Solving using Stacks

3. Expression Notations

Infix Notation (A + B)
Prefix Notation (+ A B)
Postfix Notation (A B +)
Operator Precedence & Associativity
Converting Infix → Prefix (Algorithm)
Converting Infix → Postfix (Algorithm)
Evaluating Prefix Expressions
Evaluating Postfix Expressions
Shunting Yard Algorithm
Expression Tree Construction
Parentheses Handling in Conversions
Real-World Compiler Usage

LIFO Principle

Master Last-In-First-Out data structure fundamentals

Real Applications

Learn how stacks power real-world systems and applications

Expression Evaluation

Master infix, prefix, and postfix notations

Algorithm Mastery

Learn essential stack algorithms and their complexities

Stack Operations Visualization

Push Operation

Item 4

Item 3

Item 2

Item 1

↓ Push(Item 5) ↓

→

After Push

Item 5

Item 4

Item 3

Item 2

Item 1

Top Element

→

After Pop

Item 4

Item 3

Item 2

Item 1

Pop returns: Item 5

LIFO Principle: Last element pushed (Item 5) is the first one popped. Peek operation returns Item 4 after pop.

Key Stack Applications

Function Call Stack

Manages function calls, local variables, and return addresses in programming languages.

Undo/Redo Operations

Text editors and software use stacks to implement undo (pop) and redo functionality.

Expression Evaluation

Compilers use stacks to evaluate arithmetic expressions in postfix notation.

Browser Navigation

Back button uses a stack to store visited pages, forward button uses another stack.

Parentheses Checking

Validates balanced parentheses, brackets, and braces in code editors.

DFS Algorithm

Depth-First Search in graphs uses stacks to track traversal paths.

Expression Notation Comparison

Notation Type	Format	Example	Operator Position	Evaluation Method
Infix	Operand Operator Operand	A + B * C	Between operands	Requires parentheses or precedence rules
Prefix (Polish)	Operator Operand Operand	+ A * B C	Before operands	Right-to-left evaluation using stack
Postfix (Reverse Polish)	Operand Operand Operator	A B C * +	After operands	Left-to-right evaluation using stack

Conversion Example: Infix to Postfix

Infix Expression: A + B * C - D / E

Step-by-step conversion using Shunting Yard Algorithm:

1. Initialize empty stack and output list
2. Read tokens left to right:
   - A → Add to output
   - + → Push to stack
   - B → Add to output
   - * → Push to stack (higher precedence than +)
   - C → Add to output
   - - → Pop * and + from stack to output, then push -
   - D → Add to output
   - / → Push to stack
   - E → Add to output
3. Pop remaining operators from stack

Resulting Postfix: A B C * + D E / -

Implementation Examples

Expression Evaluation in Java

// Postfix expression evaluation in Java
import java.util.Stack;

public class ExpressionEvaluator {
    
    public static double evaluatePostfix(String expression) {
        Stack stack = new Stack<>();
        String[] tokens = expression.split("\\s+");
        
        for (String token : tokens) {
            if (isNumber(token)) {
                stack.push(Double.parseDouble(token));
            } else if (isOperator(token)) {
                if (stack.size() < 2) {
                    throw new IllegalArgumentException("Invalid postfix expression");
                }
                double operand2 = stack.pop();
                double operand1 = stack.pop();
                double result = applyOperator(token, operand1, operand2);
                stack.push(result);
            }
        }
        
        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid postfix expression");
        }
        return stack.pop();
    }
    
    private static boolean isNumber(String token) {
        try {
            Double.parseDouble(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
    
    private static boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || 
               token.equals("*") || token.equals("/") || 
               token.equals("^");
    }
    
    private static double applyOperator(String operator, 
                                       double a, double b) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": 
                if (b == 0) throw new ArithmeticException("Division by zero");
                return a / b;
            case "^": return Math.pow(a, b);
            default: throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
    
    // Example usage
    public static void main(String[] args) {
        String postfix = "5 1 2 + 4 * + 3 -";
        double result = evaluatePostfix(postfix);
        System.out.println("Result: " + result); // Output: 14.0
    }
}

// Infix to Postfix conversion
class InfixToPostfix {
    private static int precedence(char operator) {
        switch (operator) {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            default: return -1;
        }
    }
    
    public static String convert(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack stack = new Stack<>();
        
        for (char c : infix.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                postfix.append(c).append(' ');
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop()).append(' ');
                }
                stack.pop(); // Remove '('
            } else { // Operator
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    postfix.append(stack.pop()).append(' ');
                }
                stack.push(c);
            }
        }
        
        while (!stack.isEmpty()) {
            postfix.append(stack.pop()).append(' ');
        }
        
        return postfix.toString().trim();
    }
}

Linked List Stack in C++

// Linked List-based Stack in C++
#include 
#include 
using namespace std;

template
class StackNode {
public:
    T data;
    StackNode* next;
    
    StackNode(T value) {
        data = value;
        next = nullptr;
    }
};

template
class LinkedListStack {
private:
    StackNode* top;
    int count;
    
public:
    LinkedListStack() {
        top = nullptr;
        count = 0;
    }
    
    // Push operation - O(1)
    void push(T value) {
        StackNode* newNode = new StackNode(value);
        newNode->next = top;
        top = newNode;
        count++;
    }
    
    // Pop operation - O(1)
    T pop() {
        if (isEmpty()) {
            throw underflow_error("Stack Underflow: Cannot pop from empty stack");
        }
        
        StackNode* temp = top;
        T poppedValue = top->data;
        top = top->next;
        delete temp;
        count--;
        
        return poppedValue;
    }
    
    // Peek operation - O(1)
    T peek() {
        if (isEmpty()) {
            throw underflow_error("Stack is empty");
        }
        return top->data;
    }
    
    bool isEmpty() {
        return top == nullptr;
    }
    
    int size() {
        return count;
    }
    
    // Display stack contents
    void display() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        
        cout << "Stack (top to bottom): ";
        StackNode* current = top;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
    
    // Destructor to prevent memory leaks
    ~LinkedListStack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

// Example usage
int main() {
    LinkedListStack stack;
    
    // Push operations
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);
    
    cout << "Stack size: " << stack.size() << endl;
    stack.display();
    
    cout << "Top element: " << stack.peek() << endl;
    
    // Pop operations
    cout << "Popped: " << stack.pop() << endl;
    cout << "Popped: " << stack.pop() << endl;
    
    cout << "Stack size after pops: " << stack.size() << endl;
    stack.display();
    
    return 0;
}

Master Stack Data Structures Today

Join thousands of developers who have strengthened their algorithm skills with comprehensive stack training. Essential for system design, compiler construction, and coding interviews.

Start Learning Stacks Now