A stack is a LIFO (Last In, First Out) data structure. The last element added is the first one removed.
const stack = [];
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.pop(); // 3, stack = [1, 2]
stack[stack.length - 1]; // peek => 2
Array-based stack: Use push/pop at the end of the array. Simple and cache-friendly.
Linked-list-based stack: Push/pop at the head. No capacity limits and always O(1).
// Linked List Stack
class Stack {
constructor() { this.top = null; this.size = 0; }
push(val) {
const node = { val, next: this.top };
this.top = node;
this.size++;
}
pop() {
if (!this.top) return null;
const val = this.top.val;
this.top = this.top.next;
this.size--;
return val;
}
peek() { return this.top ? this.top.val : null; }
}
Array is usually preferred in practice for its simplicity and better cache locality.
Push opening brackets onto the stack. For each closing bracket, check that the stack's top has the matching opening bracket.
function isBalanced(str) {
const stack = [];
const map = { ')': '(', ']': '[', '}': '{' };
for (const ch of str) {
if ('([{'.includes(ch)) {
stack.push(ch);
} else if (')]}'.includes(ch)) {
if (stack.pop() !== map[ch]) return false;
}
}
return stack.length === 0;
}
// isBalanced("({[]})") => true
// isBalanced("([)]") => false
Time: O(n) | Space: O(n)
Maintain a parallel stack that tracks the minimum at each level. Every push/pop keeps the min stack in sync.
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
const min = this.minStack.length === 0
? val
: Math.min(val, this.getMin());
this.minStack.push(min);
}
pop() {
this.stack.pop();
this.minStack.pop();
}
top() { return this.stack[this.stack.length - 1]; }
getMin() { return this.minStack[this.minStack.length - 1]; }
}
All operations are O(1) time. Space is O(n) for the auxiliary min stack.
Use a stack: push operands, and when you encounter an operator, pop two operands, apply the operator, and push the result.
function evalPostfix(tokens) {
const stack = [];
for (const token of tokens) {
if ('+-*/'.includes(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 stack.push(Math.trunc(a / b));
} else {
stack.push(Number(token));
}
}
return stack.pop();
}
// evalPostfix(["2","1","+","3","*"]) => 9
// Explanation: ((2+1)*3) = 9
Time: O(n) | Space: O(n)
Traverse from right to left. Use a stack to keep track of elements. For each element, pop smaller values off the stack — the top is the next greater element.
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) result[i] = stack[stack.length - 1];
stack.push(arr[i]);
}
return result;
}
// nextGreaterElement([4, 5, 2, 25]) => [5, 25, 25, -1]
Time: O(n) — each element is pushed/popped at most once | Space: O(n)
The stock span on day i is the number of consecutive previous days where the price was ≤ price[i]. Use a stack of indices.
function stockSpan(prices) {
const span = [];
const stack = []; // stores indices
for (let i = 0; i < prices.length; i++) {
while (stack.length && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}
span.push(stack.length === 0 ? i + 1 : i - stack[stack.length - 1]);
stack.push(i);
}
return span;
}
// stockSpan([100, 80, 60, 70, 60, 75, 85])
// => [1, 1, 1, 2, 1, 4, 6]
Time: O(n) | Space: O(n)
Use a temporary stack. Pop from the input stack and insert into the temp stack in sorted order.
function sortStack(stack) {
const temp = [];
while (stack.length) {
const curr = stack.pop();
while (temp.length && temp[temp.length - 1] > curr) {
stack.push(temp.pop());
}
temp.push(curr);
}
return temp;
}
// sortStack([34, 3, 31, 98, 92, 23])
// => [3, 23, 31, 34, 92, 98]
Time: O(n²) worst case | Space: O(n)
Use one stack growing from the start and the other from the end of the array.
class TwoStacks {
constructor(size) {
this.arr = new Array(size);
this.top1 = -1;
this.top2 = size;
}
push1(val) {
if (this.top1 + 1 < this.top2) this.arr[++this.top1] = val;
}
push2(val) {
if (this.top1 + 1 < this.top2) this.arr[--this.top2] = val;
}
pop1() {
return this.top1 >= 0 ? this.arr[this.top1--] : null;
}
pop2() {
return this.top2 < this.arr.length ? this.arr[this.top2++] : null;
}
}
This efficiently shares space between both stacks. Overflow only occurs when the total elements exceed the array size.
Each action is pushed onto the stack. Undo pops the last action and reverts it. A redo stack can store undone actions.
class UndoManager {
constructor() {
this.undoStack = [];
this.redoStack = [];
this.state = '';
}
execute(action) {
this.undoStack.push(this.state);
this.state = action(this.state);
this.redoStack = []; // clear redo on new action
}
undo() {
if (!this.undoStack.length) return;
this.redoStack.push(this.state);
this.state = this.undoStack.pop();
}
redo() {
if (!this.redoStack.length) return;
this.undoStack.push(this.state);
this.state = this.redoStack.pop();
}
}
This pattern is used in text editors, drawing apps, and many software applications.
Use a stack. Push numbers; on an operator, pop two numbers, apply the operator, push the result.
function evalRPN(tokens) {
const stack = [];
for (const token of tokens) {
if (['+','-','*','/'].includes(token)) {
const b = stack.pop(), a = stack.pop();
if (token === '+') stack.push(a + b);
else if (token === '-') stack.push(a - b);
else if (token === '*') stack.push(a * b);
else stack.push(Math.trunc(a / b)); // truncate toward zero
} else {
stack.push(Number(token));
}
}
return stack[0];
}
// Input: ["2","1","+","3","*"] => Output: 9 ((2+1)*3)
// Input: ["4","13","5","/","+"] => Output: 6 (4+(13/5))
// Input: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
// => Output: 22
Time: O(n) | Space: O(n)
Use a monotonic increasing stack. Push indices; when a shorter bar is found, pop and compute areas using the popped bar as the shortest. Track running max.
function largestRectangleArea(heights) {
const stack = [];
heights.push(0); // sentinel to flush stack
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[stack[stack.length-1]] > heights[i]) {
const h = heights[stack.pop()];
const w = stack.length ? i - stack[stack.length-1] - 1 : i;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
}
// Input: [2,1,5,6,2,3] => Output: 10 (bars 5 and 6, width 2)
// Input: [2,4] => Output: 4
Time: O(n) | Space: O(n)
Use two stacks: a main stack and a min stack. The min stack always tracks the minimum at each level.
class MinStack {
constructor() { this.stack = []; this.minStack = []; }
push(val) {
this.stack.push(val);
const min = this.minStack.length
? Math.min(val, this.minStack[this.minStack.length-1])
: val;
this.minStack.push(min);
}
pop() { this.stack.pop(); this.minStack.pop(); }
top() { return this.stack[this.stack.length-1]; }
getMin() { return this.minStack[this.minStack.length-1]; }
}
// After push(-2), push(0), push(-3): getMin() => -3
// After pop(): getMin() => -2
Time: O(1) for all ops | Space: O(n)
Use backtracking: track open and close counts. Add ( if open < n, add ) if close < open.
function generateParenthesis(n) {
const result = [];
function backtrack(s, open, close) {
if (s.length === 2 * n) { result.push(s); return; }
if (open < n) backtrack(s + '(', open + 1, close);
if (close < open) backtrack(s + ')', open, close + 1);
}
backtrack('', 0, 0);
return result;
}
// Input: n=1 => Output: ["()"]
// Input: n=2 => Output: ["(())","()()"]
// Input: n=3 => Output: ["((()))","(()())","(())()","()(())","()()()"]
Time: O(4ⁿ / √n) Catalan number | Space: O(n) recursion depth
Use a stack to save the current string and multiplier before each [. On ], pop and repeat the inner string.
function decodeString(s) {
const numStack = [], strStack = [];
let currStr = '', currNum = 0;
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
currNum = currNum * 10 + Number(ch);
} else if (ch === '[') {
numStack.push(currNum); strStack.push(currStr);
currNum = 0; currStr = '';
} else if (ch === ']') {
const times = numStack.pop();
currStr = strStack.pop() + currStr.repeat(times);
} else {
currStr += ch;
}
}
return currStr;
}
// Input: "3[a]2[bc]" => Output: "aaabcbc"
// Input: "3[a2[c]]" => Output: "accaccacc"
// Input: "2[abc]3[cd]ef" => Output: "abcabccdcdcdef"
Time: O(n × max_k) | Space: O(n)
Use a monotonic decreasing stack. Iterate the array; when a larger element is found, it becomes the "next greater" for all smaller elements waiting in the stack.
function nextGreaterElement(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;
}
// Input: [2,1,2,4,3] => Output: [4,2,4,-1,-1]
// Input: [1,3,2,4] => Output: [3,4,4,-1]
Time: O(n) — each element is pushed/popped at most once | Space: O(n)
For each push, enqueue to queue2, then drain queue1 into queue2, then swap q1 and q2. This ensures the newest element is always at the front of q1.
class MyStack {
constructor() { this.q1 = []; this.q2 = []; }
push(x) {
this.q2.push(x);
while (this.q1.length) this.q2.push(this.q1.shift());
[this.q1, this.q2] = [this.q2, this.q1];
}
pop() { return this.q1.shift(); }
top() { return this.q1[0]; }
empty() { return this.q1.length === 0; }
}
// push(1), push(2): top() => 2 (LIFO order)
// pop() => 2; top() => 1
Time: push O(n), pop O(1) | Space: O(n)
Use a stack. For each character, if it matches the top of the stack, pop (cancel both); otherwise push. The stack contains the result when done.
function removeDuplicates(s) {
const stack = [];
for (const ch of s) {
if (stack.length && stack[stack.length-1] === ch) {
stack.pop(); // cancel pair
} else {
stack.push(ch);
}
}
return stack.join('');
}
// Input: "abbaca" => Output: "ca" (ab -> a, bb -> "", ac -> ac, aa -> c)
// Input: "azxxzy" => Output: "ay"
// Input: "aaa" => Output: "a"
Time: O(n) | Space: O(n)
Use a monotonic decreasing stack of indices. When a warmer temperature is found, resolve all waiting days from the stack by computing the gap.
function dailyTemperatures(temperatures) {
const result = new Array(temperatures.length).fill(0);
const stack = []; // monotonic decreasing stack of indices
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[stack[stack.length-1]] < temperatures[i]) {
const idx = stack.pop();
result[idx] = i - idx;
}
stack.push(i);
}
return result;
}
// Input: [73,74,75,71,69,72,76,73] => Output: [1,1,4,2,1,1,0,0]
// Input: [30,40,50,60] => Output: [1,1,1,0]
Time: O(n) | Space: O(n)
Split by / and use a stack. Push directory names; for .., pop; ignore . and empty strings. Join with /.
function simplifyPath(path) {
const stack = [];
for (const part of path.split('/')) {
if (part === '..') { if (stack.length) stack.pop(); }
else if (part && part !== '.') stack.push(part);
}
return '/' + stack.join('/');
}
// Input: "/home/" => Output: "/home"
// Input: "/../" => Output: "/"
// Input: "/a/./b/../../c/" => Output: "/c"
// Input: "/a//b////c/d//././/.." => Output: "/a/b/c"
Time: O(n) | Space: O(n)
Simulate the recursive call stack. Push left children until null, process node, then move right — repeatedly.
function inorderTraversal(root) {
const result = [], stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
result.push(curr.val); // visit
curr = curr.right;
}
return result;
}
// Input tree: 2
// / // 1 3
// Output: [1, 2, 3]
Time: O(n) | Space: O(h) where h is tree height
Use a stack to track bars. When a taller bar is found, water can be trapped between it and the bar at the second-to-top of the stack.
function trap(height) {
const stack = [];
let water = 0;
for (let i = 0; i < height.length; i++) {
while (stack.length && height[stack[stack.length-1]] < height[i]) {
const bottom = stack.pop();
if (!stack.length) break;
const left = stack[stack.length-1];
const h = Math.min(height[left], height[i]) - height[bottom];
water += h * (i - left - 1);
}
stack.push(i);
}
return water;
}
// Input: [0,1,0,2,1,0,1,3,2,1,2,1] => Output: 6
// Input: [4,2,0,3,2,5] => Output: 9
Time: O(n) | Space: O(n)
Simulate: push elements in order and whenever the stack top equals the next expected pop value, pop it. At the end, the stack should be empty.
function validateStackSequences(pushed, popped) {
const stack = [];
let j = 0; // pointer into popped
for (const val of pushed) {
stack.push(val);
while (stack.length && stack[stack.length-1] === popped[j]) {
stack.pop(); j++;
}
}
return stack.length === 0;
}
// Input: pushed=[1,2,3,4,5], popped=[4,5,3,2,1] => Output: true
// Input: pushed=[1,2,3,4,5], popped=[4,3,5,1,2] => Output: false
Time: O(n) | Space: O(n)
Use two stacks: back and forward. Visit clears the forward stack and pushes to back. Back/forward swap between stacks.
class BrowserHistory {
constructor(homepage) {
this.back = [homepage];
this.forward = [];
}
visit(url) {
this.back.push(url);
this.forward = []; // clear forward history
}
goBack(steps) {
while (steps-- > 0 && this.back.length > 1) {
this.forward.push(this.back.pop());
}
return this.back[this.back.length - 1];
}
goForward(steps) {
while (steps-- > 0 && this.forward.length) {
this.back.push(this.forward.pop());
}
return this.back[this.back.length - 1];
}
}
// start("leetcode.com"); visit("google.com"); visit("facebook.com")
// goBack(1) => "google.com"
// goForward(1) => "facebook.com"
Time: O(steps) | Space: O(n)