Skip to main content
Mapagam

Using Stack Patterns

1. Understanding Stack Applications

Application Description Key Operations Use Case
Expression Evaluation Used to evaluate arithmetic expressions in postfix notation push(), pop(), peek() Compilers and calculators
Function Call Management Manages function calls and returns using a call stack push(), pop() Runtime environment in programming languages
Undo Operations Tracks actions for undo functionality in applications push(), pop() Text editors, graphic design tools
Balanced Parentheses Check Determines if parentheses in an expression are balanced push(), pop() Code editors, syntax checkers
Reverse a String Reverses the order of characters in a string using stack push(), pop() Data processing, string manipulation

Example: Expression Evaluation (Postfix)

function evaluatePostfix(expression) {
  const stack = [];
  const tokens = expression.split(" ");

  for (const token of tokens) {
    if (!isNaN(token)) {
      stack.push(Number(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        case "/": stack.push(Math.floor(a / b)); break;
      }
    }
  }

  return stack.pop();
}

// Example usage:
console.log(evaluatePostfix("3 4 + 2 * 7 /")); // Output: 2

Example: Balanced Parentheses Check

function isBalanced(expression) {
  const stack = [];
  const pairs = { ")": "(", "}": "{", "]": "[" };

  for (const char of expression) {
    if (char === "(" || char === "{" || char === "[") {
      stack.push(char);
    } else if (char === ")" || char === "}" || char === "]") {
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

// Example usage:
console.log(isBalanced("{[()]}")); // Output: true
console.log(isBalanced("([)]"));   // Output: false

2. Validating Parentheses

Stacks are commonly used to validate if parentheses in an expression are properly matched and nested.

Expression Valid? Notes
(()()) true Each opening parenthesis has a matching closing one
(())) false Extra closing parenthesis
((()) false Missing closing parenthesis

Example: Algorithm Implementation

function isValidParentheses(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (let char of s) {
    if (char in pairs) {
      if (stack.pop() !== pairs[char]) return false;
    } else if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    }
  }

  return stack.length === 0;
}
Note: The algorithm uses a stack to track opening brackets and ensures each closing bracket matches the most recent unmatched opening bracket.

3. Implementing Min Stack

Operation Description Time Complexity Space Complexity
push(value) Pushes an element onto the stack O(1) O(1)
pop() Removes and returns the top element O(1) O(1)
top() Returns the top element without removing it O(1) O(1)
getMin() Returns the minimum element in the stack O(1) O(1)

Example: Min Stack Implementation

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

  top() {
    if (this.stack.length === 0) return null;
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    if (this.minStack.length === 0) return null;
    return this.minStack[this.minStack.length - 1];
  }
}

// Example usage:
const minStack = new MinStack();
minStack.push(5);
minStack.push(2);
minStack.push(8);
console.log(minStack.getMin()); // 2
minStack.pop();
console.log(minStack.getMin()); // 5
Note: The getMin() operation ensures that the minimum element is always accessible in O(1) time by maintaining a separate stack of minimum values.

4. Evaluating Reverse Polish Notation

Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands. It's commonly used in calculators and stack-based programming languages.

Operation Description Example
Operand Pushes a number onto the stack 3
Operator Pops two operands, applies operator, pushes result back +

Example: Evaluate RPN Expression

function evalRPN(tokens) {
  const stack = [];
  
  for (const token of tokens) {
    if (token === '+' || token === '-' || token === '*' || token === '/') {
      const b = stack.pop();
      const a = stack.pop();
      
      if (token === '+') stack.push(a + b);
      else if (token === '-') stack.push(a - b);
      else if (token === '*') stack.push(a * b);
      else if (token === '/') stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(token));
    }
  }
  
  return stack[0];
}

// Example usage:
const tokens = ['2', '1', '+', '3', '*'];
console.log(evalRPN(tokens)); // Output: 9
Note: Division truncates towards zero, as per the problem constraints.

Key Points

  • RPN uses a stack to evaluate expressions
  • Operands are pushed onto the stack
  • Operators pop operands, compute result, and push back
  • Valid input ensures proper stack operations

5. Implementing Basic Calculator

Operation Description Stack Operations Example
Addition (+) Push operands, pop two values, add them, push result Push 3, Push 5, Pop 5, Pop 3, Add 3+5=8, Push 8 Example: Addition 
const stack = [];
stack.push(3);
stack.push(5);
const b = stack.pop();
const a = stack.pop();
const result = a + b;
stack.push(result); // Result: 8
Subtraction (-) Push operands, pop two values, subtract them, push result Push 10, Push 4, Pop 4, Pop 10, Subtract 10-4=6, Push 6 Example: Subtraction 
const stack = [];
stack.push(10);
stack.push(4);
const b = stack.pop();
const a = stack.pop();
const result = a - b;
stack.push(result); // Result: 6
Multiplication (*) Push operands, pop two values, multiply them, push result Push 2, Push 6, Pop 6, Pop 2, Multiply 2*6=12, Push 12 Example: Multiplication 
const stack = [];
stack.push(2);
stack.push(6);
const b = stack.pop();
const a = stack.pop();
const result = a * b;
stack.push(result); // Result: 12
Division (/) Push operands, pop two values, divide them, push result Push 15, Push 3, Pop 3, Pop 15, Divide 15/3=5, Push 5 Example: Division 
const stack = [];
stack.push(15);
stack.push(3);
const b = stack.pop();
const a = stack.pop();
const result = a / b;
stack.push(result); // Result: 5
Note: The calculator assumes postfix notation (Reverse Polish Notation) where operators come after their operands.

Example: Full Calculator Implementation

function evaluatePostfix(expression) {
  const stack = [];
  const tokens = expression.split(' ');

  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      stack.push(Number(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.floor(a / b)); break;
      }
    }
  }

  return stack.pop();
}

// Example usage:
console.log(evaluatePostfix("3 4 +")); // Output: 7
console.log(evaluatePostfix("15 7 - 1 1 + /")); // Output: 5

6. Finding Next Greater Element

The "Next Greater Element" problem involves finding the first greater element to the right of each element in an array. This is commonly solved using a stack-based approach.

Element Next Greater Element Explanation
Array [4, 5, 2, 10, 8] Input array to process
Result [5, 10, 10, -1, -1] For each element, the next greater element or -1 if none exists

Example: Stack-based Solution

function nextGreaterElement(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];

  for (let i = arr.length - 1; i >= 0; i--) {
    while (stack.length && stack[stack.length - 1] <= arr[i]) {
      stack.pop();
    }

    if (stack.length > 0) {
      result[i] = stack[stack.length - 1];
    }

    stack.push(arr[i]);
  }

  return result;
}

// Example usage:
const input = [4, 5, 2, 10, 8];
console.log(nextGreaterElement(input)); // [5, 10, 10, -1, -1]
Note: The stack maintains elements in decreasing order. For each element, we pop smaller elements from the stack until we find one greater than the current element.

7. Finding Daily Temperatures

Given an array of daily temperatures, return an array where each element represents the number of days you must wait after the current day to get a warmer temperature. If there is no warmer day, return 0 for that position.

Input Output Description
temperatures [75, 71, 69, 72, 76, 73] Array of daily temperatures

Example:

const temperatures = [75, 71, 69, 72, 76, 73];
const result = dailyTemperatures(temperatures);
console.log(result); // [1, 1, 1, 4, 0, 0]
Note: The stack stores indices of the temperatures array. For each temperature, we pop elements from the stack while the current temperature is greater than the temperature at the top of the stack.

Algorithm Steps:

  1. Initialize an empty stack to store indices.
  2. Initialize a result array with zeros of the same length as temperatures.
  3. Iterate through each temperature in the array:
  4. If the stack is empty or current temp is less than or equal to temp at top of stack, push index.
  5. Else, while current temp is greater than temp at top of stack:
  6. Pop index from stack.
  7. Set result[index] = current index - popped index.
  8. Continue until stack is empty or condition fails.
  9. Push current index to stack.

Time & Space Complexity:

  • Time: O(n) — Each element is pushed and popped at most once.
  • Space: O(n) — For the stack and result array.

8. Finding Largest Rectangle in Histogram

The "Largest Rectangle in Histogram" problem involves finding the largest rectangular area in a histogram, where each bar has a given height.

Approach Description Time Complexity Space Complexity
Stack-based Uses a stack to keep track of indices of histogram bars in increasing order of their heights. When a bar with smaller height is encountered, we calculate the area for the popped bar. O(n) O(n)

Example: Calculate Largest Rectangle in Histogram

function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        while (stack.length > 0 && (i === heights.length || heights[stack[stack.length - 1]] > heights[i])) {
            const height = heights[stack.pop()];
            const width = i - (stack.length === 0 ? 0 : stack[stack.length - 1] + 1);
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }

    return maxArea;
}

// Example usage:
const heights = [2, 1, 5, 6, 2, 3];
console.log(largestRectangleArea(heights)); // Output: 10
Note: The stack stores indices of the histogram bars in increasing order of their heights. When a bar with a smaller height is encountered, we calculate the area for the popped bar using its height and the width between the current index and the new top of the stack.

9. Implementing Stack with Queues

Implementing a stack using queues involves simulating LIFO (Last In, First Out) behavior with FIFO (First In, First Out) queue operations. This is typically done by using two queues or by rotating elements during push operations.

Operation Description Time Complexity Space Complexity
push(value) Inserts an element to the top of the stack O(n) O(n)
pop() Removes and returns the top element of the stack O(1) O(1)
top() Returns the top element without removing it O(1) O(1)
isEmpty() Checks if the stack is empty O(1) O(1)

Example: Stack Implementation Using Two Queues

class StackWithQueues {
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }

  push(value) {
    // Add new element to queue2
    this.queue2.push(value);

    // Move all elements from queue1 to queue2
    while (this.queue1.length > 0) {
      this.queue2.push(this.queue1.shift());
    }

    // Swap queues
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
  }

  pop() {
    if (this.queue1.length === 0) return null;
    return this.queue1.shift();
  }

  top() {
    if (this.queue1.length === 0) return null;
    return this.queue1[0];
  }

  isEmpty() {
    return this.queue1.length === 0;
  }
}

// Example usage:
const stack = new StackWithQueues();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.top()); // 2

Example: Stack Implementation Using One Queue

class StackWithOneQueue {
  constructor() {
    this.queue = [];
  }

  push(value) {
    const size = this.queue.length;
    this.queue.push(value);

    // Rotate all elements to the back
    for (let i = 0; i < size; i++) {
      this.queue.push(this.queue.shift());
    }
  }

  pop() {
    if (this.queue.length === 0) return null;
    return this.queue.shift();
  }

  top() {
    if (this.queue.length === 0) return null;
    return this.queue[0];
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

// Example usage:
const stack = new StackWithOneQueue();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.top()); // 2

10. Decoding Strings

Method Description Example
decodeString(s) Decodes an encoded string using a stack-based approach. 
function decodeString(s) {
  const stack = [];
  let currentStr = '';
  let currentNum = 0;

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char >= '0' && char <= '9') {
      currentNum = currentNum * 10 + parseInt(char);
    } else if (char === '[') {
      stack.push({ str: currentStr, num: currentNum });
      currentStr = '';
      currentNum = 0;
    } else if (char === ']') {
      const { str, num } = stack.pop();
      currentStr = str + currentStr.repeat(num);
    } else {
      currentStr += char;
    }
  }

  return currentStr;
}
Note: The stack stores the previous string and number before entering a nested bracket.

Decoding String Algorithm Summary

  • Uses a stack to handle nested encodings.
  • Processes digits to build repetition counts.
  • Handles brackets with string and number pairs.

11. Simplifying Unix Paths

Input Output Description
"/home/" "/home" Remove trailing slash
"/a/./b/../../c/" "/c" Handle "." (current directory) and ".." (parent directory)
"/../" "/" Root directory when navigating up from root

Example: Simplifying Unix Paths

function simplifyPath(path) {
  const stack = [];
  const components = path.split('/').filter(c => c !== '' && c !== '.');

  for (const component of components) {
    if (component === '..') {
      if (stack.length > 0) {
        stack.pop();
      }
    } else {
      stack.push(component);
    }
  }

  return '/' + stack.join('/');
}

console.log(simplifyPath("/home/")); // "/home"
console.log(simplifyPath("/a/./b/../../c/")); // "/c"

12. Removing K Digits

Given a non-negative integer represented as a string num, remove k digits to make the resulting number the smallest possible.

Property Description Example
Input Non-negative integer as string "1432219"
k Number of digits to remove 3
Output Smallest possible number after removing k digits "1221"

Example: Removing K Digits

function removeKdigits(num, k) {
    const stack = [];
    const toRemove = k;
    
    for (let i = 0; i < num.length; i++) {
        const digit = num[i];
        
        while (stack.length > 0 && stack[stack.length - 1] > digit && toRemove > 0) {
            stack.pop();
            toRemove--;
        }
        
        if (stack.length > 0 || digit !== '0') {
            stack.push(digit);
        }
    }
    
    while (toRemove > 0) {
        stack.pop();
        toRemove--;
    }
    
    return stack.length === 0 ? "0" : stack.join("");
}

// Example usage:
console.log(removeKdigits("1432219", 3)); // Output: "1221"
Note: The algorithm uses a stack to maintain the smallest digits in order. It removes larger digits when a smaller one is found, ensuring minimal result.

Was this article helpful?

Related Cheat Sheets