Stacks in DSA: LIFO Principles & Applications

1. Stack Fundamentals

Stack (LIFO Data Structure)

Definition

Stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements are added (pushed) and removed (popped) from the same end called the top. Stacks are used extensively in function call management, expression evaluation, and backtracking algorithms.

How It Works

1

Push Operation

Add element to the top of stack
Update top pointer/reference
O(1) time complexity

2

Pop Operation

Remove and return top element
Check for underflow (empty stack)
O(1) time complexity

3

Peek/Top Operation

Return top element without removing
Useful for inspection
O(1) time complexity

Array-based Stack Implementation

class ArrayStack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        return self.items.pop()
    
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

class ArrayStack {
    constructor() {
        this.items = [];
    }
    
    push(item) {
        this.items.push(item);
    }
    
    pop() {
        if (this.isEmpty()) {
            throw new Error("Stack underflow");
        }
        return this.items.pop();
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
    
    size() {
        return this.items.length;
    }
}

import java.util.ArrayList;
import java.util.List;

public class ArrayStack<T> {
    private List<T> items;
    
    public ArrayStack() {
        items = new ArrayList<>();
    }
    
    public void push(T item) {
        items.add(item);
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return items.remove(items.size() - 1);
    }
    
    public T peek() {
        if (isEmpty()) return null;
        return items.get(items.size() - 1);
    }
    
    public boolean isEmpty() {
        return items.isEmpty();
    }
    
    public int size() {
        return items.size();
    }
}

#include <vector>
#include <stdexcept>
using namespace std;

template<typename T>
class ArrayStack {
private:
    vector<T> items;
    
public:
    void push(const T& item) {
        items.push_back(item);
    }
    
    T pop() {
        if (isEmpty()) {
            throw runtime_error("Stack underflow");
        }
        T item = items.back();
        items.pop_back();
        return item;
    }
    
    T peek() {
        if (isEmpty()) throw runtime_error("Stack empty");
        return items.back();
    }
    
    bool isEmpty() {
        return items.empty();
    }
    
    int size() {
        return items.size();
    }
};

Linked List-based Stack Implementation

class ListNode:
    def __init__(self, val, next_node=None):
        self.val = val
        self.next = next_node

class LinkedListStack:
    def __init__(self):
        self.top = None
    
    def push(self, val):
        self.top = ListNode(val, self.top)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        val = self.top.val
        self.top = self.top.next
        return val
    
    def peek(self):
        if self.is_empty():
            return None
        return self.top.val
    
    def is_empty(self):
        return self.top is None

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class LinkedListStack {
    constructor() {
        this.head = null;
    }
    
    push(val) {
        this.head = new ListNode(val, this.head);
    }
    
    pop() {
        if (this.isEmpty()) {
            throw new Error("Stack underflow");
        }
        const val = this.head.val;
        this.head = this.head.next;
        return val;
    }
    
    peek() {
        return this.head?.val;
    }
    
    isEmpty() {
        return this.head === null;
    }
}

class ListNode<T> {
    T val;
    ListNode<T> next;
    
    ListNode(T val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedListStack<T> {
    private ListNode<T> top;
    
    public void push(T val) {
        ListNode<T> newNode = new ListNode<>(val);
        newNode.next = top;
        top = newNode;
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        T val = top.val;
        top = top.next;
        return val;
    }
    
    public T peek() {
        return top != null ? top.val : null;
    }
    
    public boolean isEmpty() {
        return top == null;
    }
}

#include <stdexcept>
using namespace std;

template<typename T>
struct ListNode {
    T val;
    ListNode* next;
    ListNode(T v) : val(v), next(nullptr) {}
};

template<typename T>
class LinkedListStack {
private:
    ListNode<T>* top;
    
public:
    LinkedListStack() : top(nullptr) {}
    
    void push(T val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        newNode->next = top;
        top = newNode;
    }
    
    T pop() {
        if (isEmpty()) {
            throw runtime_error("Stack underflow");
        }
        T val = top->val;
        ListNode<T>* temp = top;
        top = top->next;
        delete temp;
        return val;
    }
    
    T peek() {
        if (isEmpty()) throw runtime_error("Stack empty");
        return top->val;
    }
    
    bool isEmpty() {
        return top == nullptr;
    }
};

Complexity: Push O(1), Pop O(1), Peek O(1)
Space: O(n) for n elements
Use When: LIFO access pattern needed

2. Valid Parentheses

Parentheses Matching

Definition

Valid Parentheses checks if a string of brackets is properly matched and nested. Each opening bracket must have a corresponding closing bracket of the same type in the correct order.

How It Works

1

Initialize stack

Create empty stack
Define matching pairs

2

Process each character

If opening bracket, push to stack
If closing bracket, check if matches top
If mismatch or stack empty → invalid

3

Verify complete matching

After processing all characters
Stack must be empty for valid string

def is_valid_parentheses(s: str) -> bool:
    stack = []
    pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    
    for char in s:
        if char in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

# Test cases
print(is_valid_parentheses("()"))      # True
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses("{[]}"))    # True

function isValidParentheses(s) {
    const stack = [];
    const pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    };
    
    for (const char of s) {
        if (pairs[char]) {
            // Opening bracket
            stack.push(char);
        } else {
            // Closing bracket
            if (stack.length === 0 || pairs[stack.pop()] !== char) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
}

// Test cases
console.log(isValidParentheses("()"));      // true
console.log(isValidParentheses("()[]{}"));  // true
console.log(isValidParentheses("(]"));      // false
console.log(isValidParentheses("([)]"));    // false
console.log(isValidParentheses("{[]}"));    // true

import java.util.*;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put('(', ')');
        pairs.put('[', ']');
        pairs.put('{', '}');
        
        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                stack.push(c);
            } else {
                if (stack.isEmpty() || pairs.get(stack.pop()) != c) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isValid("()"));      // true
        System.out.println(isValid("()[]{}"));  // true
        System.out.println(isValid("(]"));      // false
    }
}

#include <stack>
#include <unordered_map>
#include <string>
using namespace std;

bool isValidParentheses(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'}
    };
    
    for (char c : s) {
        if (pairs.count(c)) {
            st.push(c);
        } else {
            if (st.empty() || pairs[st.top()] != c) {
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}

Complexity: O(n) time, O(n) space
Use When: Validating expressions, code parsing

3. Postfix Expression Evaluation

Postfix (Reverse Polish Notation) Evaluation

Definition

Postfix Evaluation computes the result of an expression where operators follow their operands (e.g., "3 4 +" = 7). Stacks naturally evaluate RPN without needing parentheses.

How It Works

1

Initialize stack

Create empty stack for operands
Split expression into tokens

2

Process each token

If number, push to stack
If operator, pop two operands
Apply operation, push result

3

Return final result

Stack contains single value
That value is the expression result

def evaluate_postfix(expression):
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),  # Integer division
        '^': lambda a, b: a ** b
    }
    
    for token in expression.split():
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.append(result)
        else:
            stack.append(int(token))
    
    return stack.pop()

# Example
expr = "3 4 + 2 * 7 /"  # (3+4)*2/7 = 2
print(evaluate_postfix(expr))  # 2

expr2 = "5 1 2 + 4 * + 3 -"  # 5+((1+2)*4)-3 = 14
print(evaluate_postfix(expr2))  # 14

function evaluatePostfix(expression) {
    const stack = [];
    const operators = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => Math.floor(a / b),
        '^': (a, b) => Math.pow(a, b)
    };
    
    for (const token of expression.split(/\s+/)) {
        if (operators[token]) {
            const b = stack.pop();
            const a = stack.pop();
            stack.push(operators[token](a, b));
        } else {
            stack.push(Number(token));
        }
    }
    
    return stack.pop();
}

// Example
console.log(evaluatePostfix("3 4 + 2 * 7 /"));  // 2
console.log(evaluatePostfix("5 1 2 + 4 * + 3 -"));  // 14

import java.util.*;

public class PostfixEvaluator {
    public static int evaluate(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split("\\s+");
        
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    int dividend = stack.pop();
                    stack.push(dividend / divisor);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
    
    public static void main(String[] args) {
        System.out.println(evaluate("3 4 + 2 * 7 /"));  // 2
    }
}

#include <stack>
#include <sstream>
#include <string>
#include <cmath>
using namespace std;

int evaluatePostfix(string expression) {
    stack<int> st;
    stringstream ss(expression);
    string token;
    
    while (ss >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(token));
        }
    }
    
    return st.top();
}

Complexity: O(n) time, O(n) space
Use When: Calculator implementation, expression evaluation

4. Min Stack (Constant Time Minimum)

Min Stack with O(1) Get Minimum

Definition

Min Stack is a stack that supports push, pop, top, and getMin operations all in O(1) time. It uses an auxiliary stack to track minimum values at each state.

How It Works

1

Maintain two stacks

Main stack stores all elements
Min stack stores current minimums

2

Push operation

Push value to main stack
If min stack empty or value ≤ current min, push to min stack

3

Pop operation

Pop from main stack
If popped value equals min stack top, pop from min stack

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self):
        if not self.stack:
            return None
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val
    
    def top(self):
        return self.stack[-1] if self.stack else None
    
    def get_min(self):
        return self.min_stack[-1] if self.min_stack else None

# Example usage
min_stack = MinStack()
min_stack.push(5)
min_stack.push(2)
min_stack.push(7)
min_stack.push(1)
print(min_stack.get_min())  # 1
min_stack.pop()  # removes 1
print(min_stack.get_min())  # 2

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }
    
    push(val) {
        this.stack.push(val);
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }
    
    pop() {
        if (this.stack.length === 0) return null;
        const val = this.stack.pop();
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
        return val;
    }
    
    top() {
        return this.stack[this.stack.length - 1];
    }
    
    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

import java.util.*;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        if (stack.isEmpty()) return;
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

#include <stack>
using namespace std;

class MinStack {
private:
    stack<int> st;
    stack<int> minSt;
    
public:
    void push(int val) {
        st.push(val);
        if (minSt.empty() || val <= minSt.top()) {
            minSt.push(val);
        }
    }
    
    void pop() {
        if (st.empty()) return;
        if (st.top() == minSt.top()) {
            minSt.pop();
        }
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};

Complexity: All operations O(1) time, O(n) space
Use When: Need constant time minimum retrieval

5. Monotonic Stack (Next Greater Element)

Next Greater Element Using Monotonic Stack

Definition

Monotonic Stack maintains elements in increasing or decreasing order. It's useful for finding next greater/smaller elements efficiently in O(n) time.

How It Works

1

Initialize empty stack

Stack stores indices of elements
Results array initialized with -1

2

Process each element

While stack not empty and current > element at stack top
Pop index and record current as next greater

3

Push current index to stack

Remaining indices have no greater element
Result holds -1 for those

def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []
    
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

def next_smaller_elements(nums):
    result = [-1] * len(nums)
    stack = []
    
    for i in range(len(nums)):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

# Example
nums = [4, 2, 9, 7, 5, 3, 6]
print(next_greater_elements(nums))  # [9, 9, -1, -1, 6, 6, -1]
print(next_smaller_elements(nums))  # [2, -1, 7, 5, 3, -1, -1]

function nextGreaterElements(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];
    
    for (let i = 0; i < nums.length; i++) {
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

function nextSmallerElements(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];
    
    for (let i = 0; i < nums.length; i++) {
        while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

import java.util.*;

public class MonotonicStack {
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int idx = stack.pop();
                result[idx] = nums[i];
            }
            stack.push(i);
        }
        
        return result;
    }
}

#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            int idx = st.top();
            st.pop();
            result[idx] = nums[i];
        }
        st.push(i);
    }
    
    return result;
}

Complexity: O(n) time, O(n) space
Use When: Next greater/smaller element problems

6. Queue Using Two Stacks

Implement Queue with Stacks

Definition

Queue Using Stacks implements First In First Out (FIFO) behavior using two LIFO stacks. One stack handles enqueue operations, the other handles dequeue operations.

How It Works

1

Maintain two stacks

inputStack: handles push/enqueue
outputStack: handles pop/dequeue

2

Enqueue operation

Simply push to inputStack
O(1) time

3

Dequeue operation

If outputStack empty, transfer all from inputStack
Pop from outputStack
Amortized O(1) time

class QueueUsingStacks:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def enqueue(self, val):
        self.input_stack.append(val)
    
    def dequeue(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        
        if not self.output_stack:
            raise IndexError("Queue is empty")
        
        return self.output_stack.pop()
    
    def peek(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        
        if not self.output_stack:
            return None
        
        return self.output_stack[-1]
    
    def is_empty(self):
        return len(self.input_stack) == 0 and len(self.output_stack) == 0

# Example usage
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.dequeue())  # 2
q.enqueue(4)
print(q.dequeue())  # 3
print(q.dequeue())  # 4

class QueueUsingStacks {
    constructor() {
        this.inputStack = [];
        this.outputStack = [];
    }
    
    enqueue(val) {
        this.inputStack.push(val);
    }
    
    dequeue() {
        if (this.outputStack.length === 0) {
            while (this.inputStack.length > 0) {
                this.outputStack.push(this.inputStack.pop());
            }
        }
        
        if (this.outputStack.length === 0) {
            throw new Error("Queue is empty");
        }
        
        return this.outputStack.pop();
    }
    
    peek() {
        if (this.outputStack.length === 0) {
            while (this.inputStack.length > 0) {
                this.outputStack.push(this.inputStack.pop());
            }
        }
        
        return this.outputStack[this.outputStack.length - 1];
    }
    
    isEmpty() {
        return this.inputStack.length === 0 && this.outputStack.length === 0;
    }
}

import java.util.*;

class QueueUsingStacks<T> {
    private Stack<T> inputStack;
    private Stack<T> outputStack;
    
    public QueueUsingStacks() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    public void enqueue(T val) {
        inputStack.push(val);
    }
    
    public T dequeue() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        
        if (outputStack.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        
        return outputStack.pop();
    }
    
    public T peek() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        
        return outputStack.peek();
    }
    
    public boolean isEmpty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

#include <stack>
#include <stdexcept>
using namespace std;

template<typename T>
class QueueUsingStacks {
private:
    stack<T> inputStack;
    stack<T> outputStack;
    
public:
    void enqueue(T val) {
        inputStack.push(val);
    }
    
    T dequeue() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        
        if (outputStack.empty()) {
            throw runtime_error("Queue is empty");
        }
        
        T val = outputStack.top();
        outputStack.pop();
        return val;
    }
    
    T peek() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        
        return outputStack.top();
    }
    
    bool isEmpty() {
        return inputStack.empty() && outputStack.empty();
    }
};

Complexity: Enqueue O(1), Dequeue amortized O(1)
Use When: Need queue behavior with limited stack implementations

Problem Type	Approach	Time Complexity
Parentheses Validation	Push opens, pop on closes	O(n)
Next Greater Element	Monotonic decreasing stack	O(n)
Largest Rectangle in Histogram	Monotonic stack with indices	O(n)
Infix to Postfix Conversion	Operator precedence stack	O(n)
Validating Stack Sequences	Simulate with single stack	O(n)
Min Stack (constant time minimum)	Auxiliary min stack	O(1) per op

7. Real-World Applications

Browser History (Back/Forward)

Two-stack approach: Manage navigation history

class BrowserHistory:
    def __init__(self, homepage):
        self.back_stack = [homepage]
        self.forward_stack = []
    
    def visit(self, url):
        self.back_stack.append(url)
        self.forward_stack.clear()
    
    def back(self, steps):
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]
    
    def forward(self, steps):
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

class BrowserHistory {
    constructor(homepage) {
        this.backStack = [homepage];
        this.forwardStack = [];
    }
    
    visit(url) {
        this.backStack.push(url);
        this.forwardStack = [];
    }
    
    back(steps) {
        while (steps-- > 0 && this.backStack.length > 1) {
            this.forwardStack.push(this.backStack.pop());
        }
        return this.backStack[this.backStack.length - 1];
    }
    
    forward(steps) {
        while (steps-- > 0 && this.forwardStack.length > 0) {
            this.backStack.push(this.forwardStack.pop());
        }
        return this.backStack[this.backStack.length - 1];
    }
}

class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    
    public BrowserHistory(String homepage) {
        backStack = new Stack<>();
        forwardStack = new Stack<>();
        backStack.push(homepage);
    }
    
    public void visit(String url) {
        backStack.push(url);
        forwardStack.clear();
    }
    
    public String back(int steps) {
        while (steps-- > 0 && backStack.size() > 1) {
            forwardStack.push(backStack.pop());
        }
        return backStack.peek();
    }
}

class BrowserHistory {
private:
    stack<string> backStack;
    stack<string> forwardStack;
    
public:
    BrowserHistory(string homepage) {
        backStack.push(homepage);
    }
    
    void visit(string url) {
        backStack.push(url);
        while (!forwardStack.empty()) forwardStack.pop();
    }
    
    string back(int steps) {
        while (steps-- > 0 && backStack.size() > 1) {
            forwardStack.push(backStack.top());
            backStack.pop();
        }
        return backStack.top();
    }
};

Text Editor Undo/Redo

Two-stack pattern: Track edit history

class TextEditor:
    def __init__(self):
        self.undo_stack = []
        self.redo_stack = []
    
    def type(self, text):
        self.undo_stack.append(('type', text))
        self.redo_stack.clear()
    
    def delete(self, count):
        self.undo_stack.append(('delete', count))
        self.redo_stack.clear()
    
    def undo(self):
        if self.undo_stack:
            action = self.undo_stack.pop()
            self.redo_stack.append(action)
    
    def redo(self):
        if self.redo_stack:
            action = self.redo_stack.pop()
            self.undo_stack.append(action)

class TextEditor {
    constructor() {
        this.undoStack = [];
        this.redoStack = [];
    }
    
    type(text) {
        this.undoStack.push({action: 'type', text});
        this.redoStack = [];
    }
    
    delete(count) {
        this.undoStack.push({action: 'delete', count});
        this.redoStack = [];
    }
    
    undo() {
        if (this.undoStack.length > 0) {
            const action = this.undoStack.pop();
            this.redoStack.push(action);
        }
    }
    
    redo() {
        if (this.redoStack.length > 0) {
            const action = this.redoStack.pop();
            this.undoStack.push(action);
        }
    }
}

class TextEditor {
    private Stack<String> undoStack;
    private Stack<String> redoStack;
    
    public TextEditor() {
        undoStack = new Stack<>();
        redoStack = new Stack<>();
    }
    
    public void type(String text) {
        undoStack.push("type:" + text);
        redoStack.clear();
    }
    
    public void undo() {
        if (!undoStack.isEmpty()) {
            redoStack.push(undoStack.pop());
        }
    }
    
    public void redo() {
        if (!redoStack.isEmpty()) {
            undoStack.push(redoStack.pop());
        }
    }
}

class TextEditor {
private:
    stack<string> undoStack;
    stack<string> redoStack;
    
public:
    void type(string text) {
        undoStack.push("type:" + text);
        while (!redoStack.empty()) redoStack.pop();
    }
    
    void undo() {
        if (!undoStack.empty()) {
            redoStack.push(undoStack.top());
            undoStack.pop();
        }
    }
    
    void redo() {
        if (!redoStack.empty()) {
            undoStack.push(redoStack.top());
            redoStack.pop();
        }
    }
};

Report Content

Stacks in DSA: LIFO Principles & Applications

Stack Usage in Systems (2023)

1. Stack Fundamentals

Stack (LIFO Data Structure)

Definition

How It Works

Push Operation

Pop Operation

Peek/Top Operation

Array-based Stack Implementation

Linked List-based Stack Implementation

2. Valid Parentheses

Parentheses Matching

Definition

How It Works

Initialize stack

Process each character

Verify complete matching

3. Postfix Expression Evaluation

Postfix (Reverse Polish Notation) Evaluation

Definition

How It Works

Initialize stack

Process each token

Return final result

4. Min Stack (Constant Time Minimum)

Min Stack with O(1) Get Minimum

Definition

How It Works

Maintain two stacks

Push operation

Pop operation

5. Monotonic Stack (Next Greater Element)

Next Greater Element Using Monotonic Stack

Definition

How It Works

Initialize empty stack

Process each element

Push current index to stack

6. Queue Using Two Stacks

Implement Queue with Stacks

Definition

How It Works

Maintain two stacks

Enqueue operation

Dequeue operation

Stack Problem-Solving Cheat Sheet

Stack Implementation Checklist

7. Real-World Applications

Browser History (Back/Forward)

Text Editor Undo/Redo

Share and Join the Discussion