Stacks & Queues

1. Stacks (LIFO - Last In, First Out)

A stack is a linear data structure that follows the LIFO principle: the last element added is the first one removed. Think of a stack of plates -- you can only add or remove plates from the top.

Every stack supports these core operations, and they all run in O(1) time:

2. Stack Implementations

Python: Using a List

Python lists support append() and pop() at the end in amortized O(1). This is the simplest stack implementation.

Python
# Stack using a Python list
stack = []

stack.append(1)   # push 1
stack.append(2)   # push 2
stack.append(3)   # push 3

print(stack[-1])   # peek: 3
print(stack.pop()) # pop: 3
print(stack)        # [1, 2]
print(len(stack))   # size: 2
print(not stack)    # isEmpty: False

Python: Using collections.deque

A deque (double-ended queue) gives guaranteed O(1) for both ends. Slightly more robust than a plain list.

Python
from collections import deque

stack = deque()

stack.append(1)     # push
stack.append(2)
stack.append(3)

print(stack[-1])     # peek: 3
print(stack.pop())   # pop: 3
print(len(stack))     # size: 2

JavaScript: Using an Array

JavaScript arrays have built-in push() and pop() methods that work in O(1).

JavaScript
// Stack using a JavaScript array
const stack = [];

stack.push(1);    // push 1
stack.push(2);    // push 2
stack.push(3);    // push 3

console.log(stack[stack.length - 1]); // peek: 3
console.log(stack.pop());             // pop: 3
console.log(stack);                   // [1, 2]
console.log(stack.length);            // size: 2
console.log(stack.length === 0);      // isEmpty: false

Full Stack Class: Python

Python
class Stack:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

    def __repr__(self):
        return f"Stack({self._data})"


# Usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())      # 30
print(s.pop())       # 30
print(s.size())      # 2
print(s.is_empty())  # False

Full Stack Class: JavaScript

JavaScript
class Stack {
    constructor() {
        this._data = [];
    }

    push(val) {
        this._data.push(val);
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error("pop from empty stack");
        }
        return this._data.pop();
    }

    peek() {
        if (this.isEmpty()) {
            throw new Error("peek from empty stack");
        }
        return this._data[this._data.length - 1];
    }

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

    size() {
        return this._data.length;
    }
}

// Usage
const s = new Stack();
s.push(10);
s.push(20);
s.push(30);
console.log(s.peek());     // 30
console.log(s.pop());      // 30
console.log(s.size());     // 2
console.log(s.isEmpty());  // false

3. Common Stack Problems

Problem 1: Valid Parentheses

Given a string containing just the characters (, ), {, }, [, and ], determine if the input string is valid. An input string is valid if every open bracket is closed by the same type, and in the correct order.

Python
def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in pairs:
            # Closing bracket -- check the top of stack
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            # Opening bracket -- push onto stack
            stack.append(char)

    return len(stack) == 0

# Examples
print(isValid("()"))       # True
print(isValid("()[]{}"))   # True
print(isValid("(]"))       # False
print(isValid("([)]"))     # False
print(isValid("{[]}"))     # True

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

    for (const char of s) {
        if (pairs[char]) {
            // Closing bracket -- check the top of stack
            if (!stack.length || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        } else {
            // Opening bracket -- push onto stack
            stack.push(char);
        }
    }

    return stack.length === 0;
}

// Examples
console.log(isValid("()"));       // true
console.log(isValid("()[]{}"));   // true
console.log(isValid("(]"));       // false
console.log(isValid("([)]"));     // false
console.log(isValid("{[]}"));     // true

Problem 2: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element -- all in O(1) time.

Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push the new minimum onto min_stack
        current_min = min(val, self.min_stack[-1] if self.min_stack else float('inf'))
        self.min_stack.append(current_min)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Usage
ms = MinStack()
ms.push(-2)
ms.push(0)
ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

JavaScript
class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val) {
        this.stack.push(val);
        const currentMin = this.minStack.length
            ? Math.min(val, this.minStack[this.minStack.length - 1])
            : val;
        this.minStack.push(currentMin);
    }

    pop() {
        this.stack.pop();
        this.minStack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

// Usage
const ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
console.log(ms.getMin());  // -3
ms.pop();
console.log(ms.top());     // 0
console.log(ms.getMin());  // -2

Problem 3: Evaluate Reverse Polish Notation

Evaluate an expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand may be an integer or another expression. Division truncates toward zero.

Python
def evalRPN(tokens: list[str]) -> int:
    stack = []

    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b = stack.pop()  # right operand
            a = stack.pop()  # left operand
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:
                # Truncate toward zero (not floor division)
                stack.append(int(a / b))
        else:
            stack.append(int(token))

    return stack[0]

# Example: ["2","1","+","3","*"] = ((2 + 1) * 3) = 9
print(evalRPN(["2","1","+","3","*"]))  # 9

# Example: ["4","13","5","/","+"] = (4 + (13 / 5)) = 6
print(evalRPN(["4","13","5","/","+"]))  # 6

JavaScript
function evalRPN(tokens) {
    const stack = [];

    for (const token of tokens) {
        if (["+", "-", "*", "/"].includes(token)) {
            const b = stack.pop();  // right operand
            const a = stack.pop();  // left operand
            switch (token) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(Math.trunc(a / b)); break;
            }
        } else {
            stack.push(Number(token));
        }
    }

    return stack[0];
}

// Example
console.log(evalRPN(["2","1","+","3","*"]));  // 9

4. Queues (FIFO - First In, First Out)

A queue is a linear data structure that follows the FIFO principle: the first element added is the first one removed. Think of a line at a store -- the first person in line gets served first.

Every queue supports these core operations, all in O(1) time:

5. Queue Implementations

Python: Using collections.deque

Python
from collections import deque

queue = deque()

queue.append(1)        # enqueue 1
queue.append(2)        # enqueue 2
queue.append(3)        # enqueue 3

print(queue[0])        # front/peek: 1
print(queue.popleft()) # dequeue: 1 (O(1)!)
print(queue)            # deque([2, 3])
print(len(queue))       # size: 2

JavaScript: Using an Array

JavaScript arrays do not have a built-in O(1) dequeue. shift() is O(n) but works fine for small inputs. For performance-critical code, use a linked-list based queue.

JavaScript
// Simple queue with array (shift is O(n) but fine for small sizes)
const queue = [];

queue.push(1);     // enqueue 1
queue.push(2);     // enqueue 2
queue.push(3);     // enqueue 3

console.log(queue[0]);      // front: 1
console.log(queue.shift()); // dequeue: 1 (O(n))
console.log(queue);          // [2, 3]
console.log(queue.length);   // 2

Full Queue Class: Python

Python
from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.popleft()

    def front(self):
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

    def __repr__(self):
        return f"Queue({list(self._data)})"


# Usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.front())      # 10
print(q.dequeue())    # 10
print(q.size())       # 2

Full Queue Class: JavaScript

JavaScript
class Queue {
    constructor() {
        this._data = {};
        this._head = 0;
        this._tail = 0;
    }

    enqueue(val) {
        this._data[this._tail] = val;
        this._tail++;
    }

    dequeue() {
        if (this.isEmpty()) {
            throw new Error("dequeue from empty queue");
        }
        const val = this._data[this._head];
        delete this._data[this._head];
        this._head++;
        return val;
    }

    front() {
        if (this.isEmpty()) {
            throw new Error("front from empty queue");
        }
        return this._data[this._head];
    }

    isEmpty() {
        return this._tail - this._head === 0;
    }

    size() {
        return this._tail - this._head;
    }
}

// Usage -- O(1) enqueue and dequeue using object index trick
const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.front());    // 10
console.log(q.dequeue());  // 10
console.log(q.size());     // 2

6. Common Queue Problems

BFS Traversal (Breadth-First Search)

Queues are the backbone of BFS. You start at a source node, enqueue it, then repeatedly dequeue a node, process it, and enqueue its unvisited neighbors. This guarantees level-by-level exploration.

Python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# Example graph (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

7. Deque (Double-Ended Queue)

A deque (pronounced "deck") allows insertion and removal from both ends in O(1). It combines the powers of a stack and a queue.

Python: collections.deque

Python
from collections import deque

dq = deque()

dq.append(2)        # push_back:  [2]
dq.append(3)        # push_back:  [2, 3]
dq.appendleft(1)    # push_front: [1, 2, 3]

print(dq[0])         # front: 1
print(dq[-1])        # back: 3
print(dq.popleft())  # pop_front: 1 -> [2, 3]
print(dq.pop())      # pop_back:  3 -> [2]

JavaScript: Array or Custom Implementation

JavaScript does not have a built-in deque. You can use an array (with unshift/shift being O(n)) or implement with a doubly linked list for O(1) on both ends.

JavaScript
// Simple deque using array (unshift/shift are O(n))
const dq = [];

dq.push(2);        // push_back:  [2]
dq.push(3);        // push_back:  [2, 3]
dq.unshift(1);     // push_front: [1, 2, 3]  (O(n))

console.log(dq[0]);            // front: 1
console.log(dq[dq.length - 1]); // back: 3
console.log(dq.shift());       // pop_front: 1 (O(n))
console.log(dq.pop());         // pop_back:  3

When to Use a Deque

The classic use case is the Sliding Window Maximum problem. You maintain a monotonic deque where the front always holds the index of the current window's maximum. As the window slides, you pop from both ends to maintain the invariant.

8. Priority Queue / Heap (Brief Intro)

A priority queue is not technically a queue -- it does not follow FIFO. Instead, elements are dequeued in priority order (smallest or largest first). Under the hood, it is typically implemented as a binary heap.

Python: heapq Module

Python's heapq provides a min-heap. To get a max-heap, negate the values.

Python
import heapq

# Min-heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

print(heap[0])               # peek min: 1
print(heapq.heappop(heap))  # extract min: 1
print(heapq.heappop(heap))  # extract min: 2

# Max-heap trick: negate values
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)
print(-heapq.heappop(max_heap))  # extract max: 3

9. Time Complexity Comparison

10. Real-World Applications

Stack Applications

• Undo/Redo -- Text editors push each action onto a stack. Undo pops the last action; redo pops from a separate stack.
• Browser Back Button -- Each page you visit is pushed onto a stack. Clicking back pops the current page and shows the previous one.
• Call Stack -- When a function calls another function, the return address is pushed onto the call stack. When the function returns, the address is popped.
• DFS (Depth-First Search) -- Uses a stack (or recursion, which uses the call stack) to explore as deep as possible before backtracking.
• Expression Parsing -- Compilers use stacks to evaluate arithmetic expressions, convert infix to postfix, and match brackets.

Queue Applications

• BFS (Breadth-First Search) -- Uses a queue to explore nodes level by level, finding shortest paths in unweighted graphs.
• Task Scheduling -- Operating systems use queues to schedule processes (FIFO scheduling, round-robin with time slices).
• Print Queue -- Documents sent to a printer are processed in the order they arrive.
• Message Queues -- Systems like RabbitMQ and Kafka use queues to decouple producers from consumers in distributed systems.
• Web Server Request Handling -- Incoming HTTP requests are queued and processed in order.

Deque Applications

• Sliding Window Problems -- Maintaining a monotonic deque for efficient window maximum/minimum queries.
• Work Stealing -- In parallel computing, threads steal tasks from the back of other threads' deques.
• Palindrome Checking -- Compare characters from both ends simultaneously.

11. LeetCode Problems

Full Solution: Valid Parentheses (LC 20)

Problem: Given a string s containing just the characters ( ) { } [ ], determine if the input string is valid.

Python
def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in pairs:
            # It's a closing bracket
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            # It's an opening bracket
            stack.append(char)

    return len(stack) == 0

# Time: O(n)  |  Space: O(n)

JavaScript
function isValid(s) {
    const stack = [];
    const pairs = { ")": "(", "}": "{", "]": "[" };

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

    return stack.length === 0;
}

// Time: O(n)  |  Space: O(n)

Full Solution: Daily Temperatures (LC 739)

Problem: Given an array of integers temperatures, return an array answer where answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day with a warmer temperature, set answer[i] = 0.

Python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores indices

    for i in range(n):
        # While current temp is warmer than temp at stack top
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)

    return answer

# Example
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]
#
# Day 0 (73): next warmer is day 1 (74) -> 1 day
# Day 1 (74): next warmer is day 2 (75) -> 1 day
# Day 2 (75): next warmer is day 6 (76) -> 4 days
# Day 3 (71): next warmer is day 5 (72) -> 2 days
# Day 4 (69): next warmer is day 5 (72) -> 1 day
# Day 5 (72): next warmer is day 6 (76) -> 1 day
# Day 6 (76): no warmer day -> 0
# Day 7 (73): no warmer day -> 0

# Time: O(n)  |  Space: O(n)

JavaScript
function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack = []; // stores indices

    for (let i = 0; i < n; i++) {
        // While current temp is warmer than temp at stack top
        while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIdx = stack.pop();
            answer[prevIdx] = i - prevIdx;
        }
        stack.push(i);
    }

    return answer;
}

// Example
const temps = [73, 74, 75, 71, 69, 72, 76, 73];
console.log(dailyTemperatures(temps));
// Output: [1, 1, 4, 2, 1, 1, 0, 0]

// Time: O(n)  |  Space: O(n)

12. Practice Quiz