Stacks in DSA: LIFO Principles & Applications

Master stack operations, implementation variants, and real-world applications. This tutorial covers parentheses matching, expression evaluation, and common interview problems with coding examples.

Stack Usage in Systems (2023)

Function Calls (40%)

Parsers (25%)

Undo Operations (20%)

Other (15%)

1. Stack Fundamentals

Core Principles:

LIFO: Last In First Out principle
Key Operations: Push, Pop, Peek
Dynamic Size: Grows/shrinks as needed

Time Complexities:

Operation	Array-based	Linked List-based
Push	O(1)*	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
Search	O(n)	O(n)

* O(n) when resizing needed

Basic Implementations:

Array-based Stack


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;
  }
}

Linked List Stack


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.head) 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;
  }
}

2. Stack Applications

Classic Problems:

Parentheses Matching


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

Postfix Evaluation


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

Real-world Use Cases:

Browser History: Back/forward navigation
Text Editors: Undo/redo operations
Compiler Design: Syntax parsing
DFS Algorithms: Graph traversal

3. Advanced Stack Techniques

Optimization Patterns:

Min Stack


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() {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
    return val;
  }
  
  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

Stack-Based Queue


class StackQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  
  enqueue(val) {
    this.inStack.push(val);
  }
  
  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}

Stack Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Parentheses Validation	Push opens, pop closes	O(n)
Next Greater Element	Monotonic stack	O(n)
Histogram Area	Stack with indices	O(n)
Infix to Postfix	Operator precedence stack	O(n)

4. Specialized Stack Variants

Monotonic Stack

Maintains sorted order


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

Thread-Safe Stack

Concurrent access handling


class ConcurrentStack {
  constructor() {
    this.stack = [];
    this.lock = new Mutex();
  }
  
  async push(item) {
    await this.lock.acquire();
    try {
      this.stack.push(item);
    } finally {
      this.lock.release();
    }
  }
}

Persistent Stack

Immutable versions


class PersistentStack {
  constructor(head = null, tail = null) {
    this.head = head;
    this.tail = tail;
  }
  
  push(val) {
    return new PersistentStack(val, this);
  }
  
  pop() {
    return this.tail || new PersistentStack();
  }
}

Stack Problem-Solving Checklist

✓ Handle empty stack cases (underflow)

✓ Consider using auxiliary stacks

✓ Verify balanced element pairs

✓ Optimize for space when needed

DSA Expert Insight: Stack problems appear in 20% of technical interviews. Mastering LIFO principles and pattern recognition can help solve complex problems with elegant solutions.

0 Interaction

0 Views

0 Likes