Understanding the Stack Data Structure
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates: you can only add a plate to the top, and you can only remove the plate from the top. The last plate you put on the stack is the first one you take off.
The two fundamental operations on a stack are:
- Push – Add an element to the top of the stack
- Pop – Remove the top element from the stack
Additional helper operations often include:
- Peek / Top – View the top element without removing it
- isEmpty – Check whether the stack has any elements
- Size – Get the current number of elements
Basic Stack Implementation in JavaScript
Before diving into interview problems, let's build a solid stack implementation. Understanding the internals will help you reason about edge cases during interviews.
class Stack {
constructor() {
this.items = [];
this.count = 0;
}
// Push: add element to the top
push(element) {
this.items[this.count] = element;
this.count++;
return this.count;
}
// Pop: remove and return the top element
pop() {
if (this.count === 0) return undefined;
this.count--;
const removed = this.items[this.count];
delete this.items[this.count];
return removed;
}
// Peek: view the top element without removing it
peek() {
if (this.count === 0) return undefined;
return this.items[this.count - 1];
}
// isEmpty: check if stack is empty
isEmpty() {
return this.count === 0;
}
// Size: get number of elements
size() {
return this.count;
}
// Clear the stack
clear() {
this.items = [];
this.count = 0;
}
// Print the stack contents
print() {
if (this.count === 0) {
return 'Stack is empty';
}
let str = '';
for (let i = 0; i < this.count; i++) {
str += this.items[i] + ' ';
}
return str.trim();
}
}
// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 30
console.log(stack.pop()); // 30
console.log(stack.size()); // 2
console.log(stack.isEmpty()); // falseAlternative: Using JavaScript Arrays as Stacks
In many interview settings, you can use JavaScript arrays directly, since they provide O(1) push and pop operations at the end:
const stack = [];
stack.push(10); // push
stack.push(20);
const top = stack[stack.length - 1]; // peek
const popped = stack.pop(); // pop
const empty = stack.length === 0; // isEmptyHowever, building a custom stack class demonstrates deeper understanding and gives you full control over the interface, which interviewers appreciate.
Why Stacks Matter in Technical Interviews
🚀 Deploy your AI agent in 10 minutes
Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.
Try it free →Stack problems are extremely common in coding interviews at companies like Google, Meta, Amazon, and Microsoft for several reasons:
- They test fundamental understanding – Stacks are simple but require precise reasoning about order of operations
- They reveal algorithmic thinking – Many stack solutions require recognizing when LIFO behavior solves a problem elegantly
- They appear in parsing problems – Compilers, expression evaluators, and bracket validators all use stacks
- They scale to harder problems – Monotonic stacks appear in advanced array and histogram problems
- They connect to recursion – Understanding stacks helps you grasp the call stack and recursive algorithms
Interviewers often start with a simple stack problem (like validating parentheses) and then escalate to more complex variants to test how well you can extend a core concept.
Core Problem Category 1: Bracket & Parentheses Validation
Problem 1.1: Valid Parentheses (LeetCode 20)
Problem Statement: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if open brackets are closed by the same type of bracket and in the correct order.
Key Insight: When you encounter a closing bracket, it must match the most recently opened bracket — this is exactly LIFO behavior.
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const stack = [];
const matchingBrackets = {
')': '(',
'}': '{',
']': '['
};
for (let char of s) {
// If it's a closing bracket
if (char in matchingBrackets) {
// Pop the top element; if stack is empty, use a dummy value
const topElement = stack.length === 0 ? '#' : stack.pop();
// Check if the popped element matches the required opening bracket
if (topElement !== matchingBrackets[char]) {
return false;
}
} else {
// It's an opening bracket, push it onto the stack
stack.push(char);
}
}
// If the stack is empty, all brackets were properly closed
return stack.length === 0;
}
// Test cases
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true
console.log(isValid("(({{}}))")); // true
console.log(isValid("(({{}})") ); // falseTime Complexity: O(n) — we scan the string once.
Space Complexity: O(n) — in the worst case, we push all opening brackets onto the stack.
Problem 1.2: Valid Parenthesis with Wildcards / Check if a string with '*' can be valid
Some interviewers extend the problem by introducing a wildcard character '*' that can represent an opening bracket, a closing bracket, or an empty string. This requires a more nuanced two-stack approach or a greedy balance check.
Here's a solution for checking if a string with '(', ')', and '*' can form a valid parentheses sequence:
/**
* @param {string} s
* @return {boolean}
*/
function checkValidString(s) {
let low = 0; // minimum possible open brackets
let high = 0; // maximum possible open brackets
for (let char of s) {
if (char === '(') {
low++;
high++;
} else if (char === ')') {
low = Math.max(0, low - 1);
high--;
if (high < 0) return false; // more closing than possible opening
} else if (char === '*') {
low = Math.max(0, low - 1); // treat as ')'
high++; // treat as '('
}
}
// At the end, low must be 0 (all opens can be closed)
return low === 0;
}
// Test cases
console.log(checkValidString("()")); // true
console.log(checkValidString("(*)")); // true
console.log(checkValidString("(*))")); // true
console.log(checkValidString("((*)")); // true (last * can be ')')
console.log(checkValidString("((*))")); // true
console.log(checkValidString(")(")); // falseCore Problem Category 2: Monotonic Stack Patterns
A monotonic stack maintains elements in either strictly increasing or strictly decreasing order. It's a powerful pattern for problems asking about the "next greater element," "next smaller element," or when you need to find boundaries in arrays.
Problem 2.1: Next Greater Element I (LeetCode 496)
Problem Statement: Given two arrays, find the next greater element for each element of the first array in the second array. The "next greater element" is the first element to the right that is larger.
/**
* @param {number[]} nums1 - subset of nums2
* @param {number[]} nums2 - the full array to search
* @return {number[]}
*/
function nextGreaterElement(nums1, nums2) {
const stack = [];
const nextGreaterMap = new Map();
// Build the next greater element map for nums2
for (let num of nums2) {
// While stack is not empty and current num is greater than top
while (stack.length > 0 && num > stack[stack.length - 1]) {
const smaller = stack.pop();
nextGreaterMap.set(smaller, num);
}
stack.push(num);
}
// Remaining elements in stack have no next greater element
while (stack.length > 0) {
nextGreaterMap.set(stack.pop(), -1);
}
// Map results for nums1
const result = [];
for (let num of nums1) {
result.push(nextGreaterMap.get(num));
}
return result;
}
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1, 3, -1]
console.log(nextGreaterElement([2,4], [1,2,3,4])); // [3, -1]Why the monotonic stack works: We maintain a decreasing stack. When we encounter a number larger than the top, it becomes the "next greater" for everything currently waiting on the stack. This processes each element in O(1) amortized time.
Problem 2.2: Daily Temperatures (LeetCode 739)
Problem Statement: Given an array of daily temperatures, return an array where each element is the number of days you must wait after that day to get a warmer temperature. If no warmer day exists, put 0.
This is essentially "next greater element with distance" — the same monotonic stack pattern.
/**
* @param {number[]} temperatures
* @return {number[]}
*/
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const result = new Array(n).fill(0);
const stack = []; // stores indices of temperatures in decreasing order
for (let i = 0; i < n; i++) {
const currentTemp = temperatures[i];
// While current temperature is warmer than the temperature at stack top index
while (stack.length > 0 && currentTemp > temperatures[stack[stack.length - 1]]) {
const prevDay = stack.pop();
result[prevDay] = i - prevDay; // days to wait
}
stack.push(i);
}
// Remaining indices in stack have no warmer day -> already 0
return result;
}
console.log(dailyTemperatures([73,74,75,71,69,72,76,73]));
// Output: [1, 1, 4, 2, 1, 1, 0, 0]
console.log(dailyTemperatures([30,40,50,60]));
// Output: [1, 1, 1, 0]
console.log(dailyTemperatures([30,25,20]));
// Output: [0, 0, 0]Problem 2.3: Largest Rectangle in Histogram (LeetCode 84)
This is a classic hard problem that uses a monotonic increasing stack to find the boundaries of rectangles efficiently.
/**
* @param {number[]} heights
* @return {number}
*/
function largestRectangleArea(heights) {
const stack = []; // stores indices in increasing height order
let maxArea = 0;
// Append a sentinel height of 0 to flush the stack at the end
const heightsWithSentinel = [...heights, 0];
for (let i = 0; i < heightsWithSentinel.length; i++) {
const currentHeight = heightsWithSentinel[i];
// While current bar is shorter than the bar at stack top index
while (stack.length > 0 && currentHeight < heightsWithSentinel[stack[stack.length - 1]]) {
const height = heightsWithSentinel[stack.pop()];
// Width: from the previous element in stack (or start) to current position
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
const area = height * width;
maxArea = Math.max(maxArea, area);
}
stack.push(i);
}
return maxArea;
}
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10
console.log(largestRectangleArea([2,4])); // 4
console.log(largestRectangleArea([1,1,1,1])); // 4
console.log(largestRectangleArea([])); // 0
console.log(largestRectangleArea([5])); // 5Understanding the algorithm: The stack stores indices of bars in increasing height order. When we encounter a shorter bar, it means the bar at the top of the stack cannot extend further to the right. We pop it, calculate the maximum rectangle using that bar's full height, and the width extends from the next element in the stack (exclusive) to the current index (exclusive). The sentinel 0 at the end ensures all remaining bars get processed.
Core Problem Category 3: Expression Evaluation
Problem 3.1: Evaluate Reverse Polish Notation (LeetCode 150)
Problem Statement: Evaluate an arithmetic expression given in Reverse Polish Notation (postfix). Valid operators are +, -, *, and /. Each operand may be an integer.
/**
* @param {string[]} tokens
* @return {number}
*/
function evalRPN(tokens) {
const stack = [];
for (let token of tokens) {
if (token === '+' || token === '-' || token === '*' || token === '/') {
// Pop the two operands (note the order: second popped is the first operand)
const b = stack.pop();
const a = stack.pop();
let result;
switch (token) {
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
// Integer division truncates toward zero
result = Math.trunc(a / b);
break;
}
stack.push(result);
} else {
// It's a number, push it onto the stack
stack.push(parseInt(token, 10));
}
}
// The final result is the only element left in the stack
return stack[0];
}
console.log(evalRPN(["2","1","+","3","*"])); // 9
console.log(evalRPN(["4","13","5","/","+"])); // 6
console.log(evalRPN(["10","6","9","3","+","-11","*","/","*","17","+","5","+"])); // 22Problem 3.2: Basic Calculator II (LeetCode 227)
Problem Statement: Evaluate a basic arithmetic expression string containing non-negative integers and operators +, -, *, /, and spaces. No parentheses.
/**
* @param {string} s
* @return {number}
*/
function calculate(s) {
const stack = [];
let currentNumber = 0;
let operation = '+'; // track the last operator seen
// Remove spaces for easier processing, or handle in the loop
s = s.replace(/\s/g, '');
for (let i = 0; i < s.length; i++) {
const char = s[i];
// Build the number (could be multiple digits)
if (char >= '0' && char <= '9') {
currentNumber = currentNumber * 10 + parseInt(char, 10);
}
// If we hit an operator or the end of the string, process the last operation
if (char < '0' || char > '9' || i === s.length - 1) {
switch (operation) {
case '+':
stack.push(currentNumber);
break;
case '-':
stack.push(-currentNumber);
break;
case '*':
stack.push(stack.pop() * currentNumber);
break;
case '/':
stack.push(Math.trunc(stack.pop() / currentNumber));
break;
}
operation = char;
currentNumber = 0;
}
}
// Sum all values in the stack
let result = 0;
while (stack.length > 0) {
result += stack.pop();
}
return result;
}
console.log(calculate("3+2*2")); // 7
console.log(calculate(" 3/2 ")); // 1
console.log(calculate(" 3+5 / 2 ")); // 5
console.log(calculate("14-3/2")); // 13Key Insight: By deferring the application of + and - (pushing onto the stack) while immediately applying * and /, we respect operator precedence without needing an explicit precedence table. The stack accumulates values that are ultimately summed.
Problem 3.3: Basic Calculator with Parentheses (LeetCode 224)
This is the full version with parentheses, unary minus, and spaces. It often combines a value stack with an operator stack or uses recursion.
/**
* @param {string} s
* @return {number}
*/
function calculateWithParentheses(s) {
const stack = [];
let result = 0;
let sign = 1; // 1 for positive, -1 for negative
let currentNumber = 0;
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === ' ') {
continue;
}
if (char >= '0' && char <= '9') {
// Build multi-digit number
currentNumber = currentNumber * 10 + parseInt(char, 10);
} else if (char === '+') {
// Apply previous number with its sign
result += sign * currentNumber;
currentNumber = 0;
sign = 1;
} else if (char === '-') {
result += sign * currentNumber;
currentNumber = 0;
sign = -1;
} else if (char === '(') {
// Push current state onto stack to start a new sub-expression
stack.push(result);
stack.push(sign);
// Reset for the sub-expression
result = 0;
sign = 1;
} else if (char === ')') {
// Finish the sub-expression by applying the last pending number
result += sign * currentNumber;
currentNumber = 0;
// Pop the sign that was saved before the parenthesis
result *= stack.pop(); // this is the sign
// Add the result that was saved before the parenthesis
result += stack.pop();
}
}
// Apply any remaining pending number
if (currentNumber !== 0) {
result += sign * currentNumber;
}
return result;
}
console.log(calculateWithParentheses("1 + 1")); // 2
console.log(calculateWithParentheses(" 2-1 + 2 ")); // 3
console.log(calculateWithParentheses("(1+(4+5+2)-3)+(6+8)")); // 23
console.log(calculateWithParentheses("-(2+3)")); // -5
console.log(calculateWithParentheses("2-(5-6)")); // 3Core Problem Category 4: String Manipulation with Stacks
Problem 4.1: Simplify Path (LeetCode 71)
Problem Statement: Given an absolute Unix-style file path, simplify it to the canonical form. Handle ".", "..", multiple slashes, etc.
/**
* @param {string} path
* @return {string}
*/
function simplifyPath(path) {
const components = path.split('/');
const stack = [];
for (let component of components) {
// Skip empty strings (from consecutive slashes) and current directory "."
if (component === '' || component === '.') {
continue;
}
// ".." means go up one directory (pop from stack if not empty)
if (component === '..') {
if (stack.length > 0) {
stack.pop();
}
} else {
// Valid directory name, push it
stack.push(component);
}
}
// Reconstruct the canonical path
return '/' + stack.join('/');
}
console.log(simplifyPath("/home/")); // "/home"
console.log(simplifyPath("/home//foo/")); // "/home/foo"
console.log(simplifyPath("/home/user/Documents/../Pictures")); // "/home/user/Pictures"
console.log(simplifyPath("/../")); // "/"
console.log(simplifyPath("/.../a/../b/c/../d/./")); // "/.../b/d"
console.log(simplifyPath("/a/../../b/../c//.//")); // "/c"Problem 4.2: Remove All Adjacent Duplicates (LeetCode 1047)
Problem Statement: Given a string of lowercase letters, repeatedly remove adjacent duplicate pairs until no such pairs exist.
/**
* @param {string} s
* @return {string}
*/
function removeDuplicates(s) {
const stack = [];
for (let char of s) {
// If the stack is not empty and the top equals current char, they cancel
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
stack.push(char);
}
}
return stack.join('');
}
console.log(removeDuplicates("abbaca")); // "ca"
console.log(removeDuplicates("azxxzy")); // "ay"
console.log(removeDuplicates("abba")); // "" (empty string)
console.log(removeDuplicates("abcddcba")); // "" (everything cancels)Problem 4.3: Remove Duplicate Letters / Smallest Subsequence (LeetCode 316 / 1081)
This is a harder problem: remove duplicate letters so that every letter appears exactly once and the result is the lexicographically smallest possible. It combines a stack with a frequency map and a "seen" set.
/**
* @param {string} s
* @return {string}
*/
function removeDuplicateLetters(s) {
// Count frequency of each character
const count = {};
for (let char of s) {
count[char] = (count[char] || 0) + 1;
}
const stack = [];
const inStack = new Set();
for (let char of s) {
// Decrement the remaining count for this character
count[char]--;
// If character is already in the stack, skip it
if (inStack.has(char)) {
continue;
}
// While we can pop the top of the stack to get a lexicographically smaller result
// Conditions: top char is greater than current char AND top char still appears later
while (stack.length > 0 &&
stack[stack.length - 1] > char &&
count[stack[stack.length - 1]] > 0) {
const removed = stack.pop();
inStack.delete(removed);
}
stack.push(char);
inStack.add(char);
}
return stack.join('');
}
console.log(removeDuplicateLetters("bcabc")); // "abc"
console.log(removeDuplicateLetters("cbacdcbc")); // "acdb"
console.log(removeDuplicateLetters("abacb")); // "abc"
console.log(removeDuplicateLetters("cdadabcc")); // "adbc"Key Insight: You can remove a character from the stack only if it appears again later (checked via the count map). The "inStack" set prevents duplicate additions. This greedy stack approach guarantees the lexicographically smallest unique sequence.
Core Problem Category 5: Stack-Based Data Structure Design
Problem 5.1: Min Stack (LeetCode 155)
Problem Statement: Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time.
class MinStack {
constructor() {
this.stack = []; // main stack
this.minStack = []; // keeps track of minimums
}
/**
* @param {number} val
* @return {void}
*/
push(val) {
this.stack.push(val);
// Push to minStack if it's empty or val is <= current min
if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
}
/**
* @return {void}
*/
pop() {
const popped = this.stack.pop();
// If the popped value equals the current min, pop from minStack too
if (popped === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
}
/**
* @return {number}
*/
top() {
return this.stack[this.stack.length - 1];
}
/**
* @return {number}
*/
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
// Usage
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin()); // -3
minStack.pop();
console.log(minStack.top()); // 0
console.log(minStack.getMin()); // -2
minStack.push(-10);
minStack.push(-10); // push duplicate minimum
console.log(minStack.getMin()); // -10
minStack.pop();
console.log(minStack.getMin()); // -10 (still there because we pushed -10 twice)Design rationale: The auxiliary minStack mirrors the main stack but only pushes when the new value is less than or equal to the current minimum. This handles duplicates correctly. Popping from minStack only when the popped value equals the current min ensures synchronization.
Problem 5.2: Implement Queue using Stacks (LeetCode 232)
This classic problem tests whether you understand how to reverse LIFO to achieve FIFO.
class MyQueue {
constructor() {
this.stackIn = []; // for enqueue (push)
this.stackOut = []; // for dequeue (pop/peek)
}
/**
* @param {number} x
* @return {void}
*/
push(x) {
this.stackIn.push(x);
}
/**
* Transfer elements from stackIn to stackOut if stackOut is empty
* @return {void}
*/
_transfer() {
if (this.stackOut.length === 0) {
while (this.stackIn.length > 0) {
this.stackOut.push(this.stackIn.pop());
}
}
}
/**
* @return {number}
*/
pop() {
this._transfer();
return this.stackOut.pop();
}
/**
* @return {number}
*/
peek() {
this._transfer();
return this.stackOut[this.stackOut.length - 1];
}
/**
* @return {boolean}
*/
empty() {
return this.stackIn.length === 0 && this.stackOut.length === 0;
}
}
// Usage
const queue = new MyQueue();
queue.push(1);
queue.push(2);
console.log(queue.peek()); // 1
console.log(queue.pop()); // 1
console.log(queue.empty()); // false
console.log(queue.pop()); // 2
console.log(queue.empty()); // trueAmortized Analysis: Each element is moved from stackIn to stackOut at most once, giving amortized O(1) per operation.
Core Problem Category 6: Tree and Graph Traversal with Stacks
Problem 6.1: Iterative Inorder Traversal of a Binary Tree
Recursive tree traversals implicitly use the call stack. Interviewers often ask for an explicit stack-based iterative version to test your understanding.
// Definition for a binary tree node
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* @param {TreeNode} root
* @return {number[]}
*/
function inorderTraversal(root) {
const result = [];
const stack = [];
let current = root;
while (current !== null || stack.length > 0) {
// Go as far left as possible
while (current !== null) {
stack.push(current);
current = current.left;
}
// Pop the deepest left node
current = stack.pop();
result.push(current.val);
// Move to the right subtree
current = current.right;
}
return result;
}
// Example tree:
// 1
// \
// 2
// /
// 3
const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderTraversal(root)); // [1, 3, 2]Problem 6.2: Iterative Preorder and Postorder Traversals
/**
* Iterative Preorder Traversal (Root, Left, Right)
* @param {TreeNode} root
* @return {number[]}
*/
function preorderTraversal(root) {
if (root === null) return [];
const result = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push right first so left is processed next (LIFO)
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return result;
}
/**
* Iterative Postorder Traversal (Left, Right, Root)
* Uses two stacks or a modified preorder trick
* @param {TreeNode} root
* @return {number[]}
*/
function postorderTraversal(root) {
if (root === null) return [];
const result = [];
const stack = [root];
// Modified preorder: Root -> Right -> Left, then reverse
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push left first so right is processed next
if (node.left !== null) stack.push(node.left);
if (node.right !== null) stack.push(node.right);
}
// Reverse to get Left, Right, Root
return result.reverse();
}
// Test
const root2 = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3)
);
console.log(preorderTraversal(root2)); // [1, 2, 4, 5, 3]
console.log(postorderTraversal(root2)); // [4, 5, 2, 3, 1]Core Problem Category 7: Decode Strings and Nested Structures
Problem 7.1: Decode String (LeetCode 394)
Problem Statement: Given an encoded string like "3[a2[c]]", decode it to "accaccacc". The pattern is k[encoded_string] where k is a positive integer.
/**
* @param {string} s
* @return {string}
*/
function decodeString(s) {
const stack = [];
let currentString = '';
let currentNum =