Stack and queue

Two ways to line things up. A stack is a pile of plates: you take the one you put on last. A queue is a line at a shop: the first to arrive is the first served.

	Add	Remove	Look at next	Order
Stack	push \(O(1)\)	pop \(O(1)\)	peek \(O(1)\)	last in, first out (LIFO)
Queue	enqueue \(O(1)\)	dequeue \(O(1)\)	front \(O(1)\)	first in, first out (FIFO)

The idea

A stack remembers what is still open. Reading a[b(c)d]e left to right, every opening bracket is pushed; every closing bracket must match the bracket on top, which is the most recently opened one still unclosed. If the stack is empty at the end, the text is balanced. Your computer runs every program on a stack, too: each function call pushes a frame, and returning pops it (see Recursion).

A queue keeps arrival order. It is the heart of breadth-first search, of printers, of web servers handling requests, and of anything "first come, first served".

How to build them so every operation is \(O(1)\). A stack is just a growing array, used only at its end. A queue cannot simply remove from the front of an array (everything would shift), so it uses a ring buffer: an array whose end wraps around to the start, with a head index for the front. When it fills up, copy into an array twice as large.

How it works (bracket check)

1. For each character: if it opens a bracket, push it.
2. If it closes one: the stack must not be empty, and the popped opener must be the matching kind.
3. At the end, the stack must be empty.

Code

PythonJavaC++

class Stack:
    """Last in, first out, on a growing list: push and pop at the end are O(1)."""
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def empty(self):
        return not self.items


class Queue:
    """First in, first out, in a ring buffer that doubles when full: every operation is O(1) amortized."""
    def __init__(self):
        self.buf = [None] * 4
        self.head = 0                        # index of the front item
        self.size = 0

    def enqueue(self, x):
        if self.size == len(self.buf):       # full: copy into a buffer twice as big
            self.buf = [self.buf[(self.head + i) % len(self.buf)] for i in range(self.size)] + [None] * self.size
            self.head = 0
        self.buf[(self.head + self.size) % len(self.buf)] = x
        self.size += 1

    def dequeue(self):
        x = self.buf[self.head]
        self.buf[self.head] = None
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return x

    def empty(self):
        return self.size == 0


def balanced(s):
    """True if every bracket in s is closed by the right kind, in the right order."""
    pairs = {")": "(", "]": "[", "}": "{"}
    st = Stack()
    for ch in s:
        if ch in "([{":
            st.push(ch)                      # remember the opener
        elif ch in pairs:
            if st.empty() or st.pop() != pairs[ch]:
                return False                 # nothing to close, or the wrong kind
    return st.empty()                        # every opener was closed


if __name__ == "__main__":
    for s in ["([]{})", "([)]", "((", "a[b(c)d]e", ""]:
        print(repr(s), balanced(s))
    q = Queue()
    for x in range(1, 7):
        q.enqueue(x)
    out = [q.dequeue(), q.dequeue()]
    q.enqueue(7)
    while not q.empty():
        out.append(q.dequeue())
    print(out)

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class StackQueue {
    /** Last in, first out, on a growing array: push and pop at the end are O(1) amortized. */
    static class Stack<T> {
        private final ArrayList<T> items = new ArrayList<>();
        void push(T x) { items.add(x); }
        T pop() { return items.remove(items.size() - 1); }
        T peek() { return items.get(items.size() - 1); }
        boolean empty() { return items.isEmpty(); }
    }

    /** First in, first out, in a ring buffer that doubles when full: every operation is O(1) amortized. */
    static class Queue<T> {
        private Object[] buf = new Object[4];
        private int head = 0, size = 0;               // head: index of the front item

        void enqueue(T x) {
            if (size == buf.length) {                 // full: copy into a buffer twice as big
                Object[] bigger = new Object[2 * buf.length];
                for (int i = 0; i < size; i++) bigger[i] = buf[(head + i) % buf.length];
                buf = bigger;
                head = 0;
            }
            buf[(head + size) % buf.length] = x;
            size++;
        }

        @SuppressWarnings("unchecked")
        T dequeue() {
            T x = (T) buf[head];
            buf[head] = null;
            head = (head + 1) % buf.length;
            size--;
            return x;
        }

        boolean empty() { return size == 0; }
    }

    /** True if every bracket in s is closed by the right kind, in the right order. */
    static boolean balanced(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Stack<Character> st = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') st.push(ch);       // remember the opener
            else if (pairs.containsKey(ch)) {
                if (st.empty() || st.pop() != pairs.get(ch)) return false;   // nothing to close, or wrong kind
            }
        }
        return st.empty();                            // every opener was closed
    }

    public static void main(String[] args) {
        for (String s : new String[]{"([]{})", "([)]", "((", "a[b(c)d]e", ""})
            System.out.println("'" + s + "' " + (balanced(s) ? "True" : "False"));
        Queue<Integer> q = new Queue<>();
        for (int x = 1; x <= 6; x++) q.enqueue(x);
        List<Integer> out = new ArrayList<>(List.of(q.dequeue(), q.dequeue()));
        q.enqueue(7);
        while (!q.empty()) out.add(q.dequeue());
        System.out.println(out);
    }
}

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

// Last in, first out, on a growing array: push and pop at the end are O(1) amortized.
template <typename T>
struct Stack {
    vector<T> items;
    void push(const T& x) { items.push_back(x); }
    T pop() { T x = items.back(); items.pop_back(); return x; }
    T peek() const { return items.back(); }
    bool empty() const { return items.empty(); }
};

// First in, first out, in a ring buffer that doubles when full: every operation is O(1) amortized.
template <typename T>
struct Queue {
    vector<T> buf = vector<T>(4);
    size_t head = 0, size = 0;                       // head: index of the front item

    void enqueue(const T& x) {
        if (size == buf.size()) {                    // full: copy into a buffer twice as big
            vector<T> bigger(2 * buf.size());
            for (size_t i = 0; i < size; i++) bigger[i] = buf[(head + i) % buf.size()];
            buf.swap(bigger);
            head = 0;
        }
        buf[(head + size) % buf.size()] = x;
        size++;
    }

    T dequeue() {
        T x = buf[head];
        head = (head + 1) % buf.size();
        size--;
        return x;
    }

    bool empty() const { return size == 0; }
};

// True if every bracket in s is closed by the right kind, in the right order.
bool balanced(const string& s) {
    map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    Stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') st.push(ch);          // remember the opener
        else if (pairs.count(ch)) {
            if (st.empty() || st.pop() != pairs[ch]) return false;      // nothing to close, or wrong kind
        }
    }
    return st.empty();                               // every opener was closed
}

int main() {
    for (string s : {"([]{})", "([)]", "((", "a[b(c)d]e", ""})
        cout << "'" << s << "' " << (balanced(s) ? "True" : "False") << "\n";
    Queue<int> q;
    for (int x = 1; x <= 6; x++) q.enqueue(x);
    vector<int> out = {q.dequeue(), q.dequeue()};
    q.enqueue(7);
    while (!q.empty()) out.push_back(q.dequeue());
    cout << "[";
    for (size_t i = 0; i < out.size(); i++) cout << (i ? ", " : "") << out[i];
    cout << "]\n";
}

Output: the five texts are balanced, not, not, balanced, balanced; then the queue gives [1, 2, 3, 4, 5, 6, 7], in arrival order, although it had to grow from 4 slots while wrapped around.

When to use them

Stack: undo, the back button, matching brackets and tags, evaluating expressions (3 4 + 2 *), turning recursion into a loop, depth-first search, and the "next greater element" family of problems (a monotonic stack).

Queue: breadth-first search and shortest paths in unweighted graphs, task scheduling, buffers between a fast producer and a slow consumer, simulations. A deque (double-ended queue) allows both ends and gives the sliding-window maximum.

Common mistakes

• Popping an empty stack (check first, as balanced does).
• Using a Python list as a queue with pop(0): each removal shifts every value, \(O(n)\). Use collections.deque.
• Using Java's old Stack class: it is synchronized and slow; ArrayDeque is the modern choice.
• Forgetting the wrap-around (% capacity) in a ring buffer, or copying it in the wrong order when growing.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: \"a[b(c)d]e\"

Character	Action	Stack after (bottom → top)
a	not a bracket	(empty)
[	push	[
b	not a bracket	[
(	push	[ (
c	not a bracket	[ (
)	pop "(", it matches	[
d	not a bracket	[
]	pop "[", it matches	(empty)
e	not a bracket	(empty)

Empty at the end: balanced. For ([)], the ) pops [: a mismatch, so not balanced.

The math: amortized O(1) for a growing array

One push that finds the array full must copy all \(n\) items, which is \(O(n)\). But that is rare. If the capacity doubles each time, then over \(n\) pushes starting from capacity 1 the copies cost

\[ 1 + 2 + 4 + \cdots + 2^{\lfloor \log_2 n \rfloor} < 2n, \]

so all \(n\) pushes cost less than \(n + 2n = 3n\) steps: \(O(1)\) amortized per push.

Potential method. Define \(\Phi = 2\cdot\text{size} - \text{capacity}\) (never negative after the first doubling). A normal push costs 1 and raises \(\Phi\) by 2: amortized cost 3. A push that doubles from capacity \(c\) (with size \(c\)) costs \(c + 1\) and changes \(\Phi\) from \(c\) to \(2(c+1) - 2c = 2\): amortized cost \(c + 1 + 2 - c = 3\). Every push has amortized cost 3.

Growing by a fixed amount (say 10 slots) instead of doubling makes the copies \(10 + 20 + 30 + \cdots\), which is \(\Theta(n^2)\) in total: always grow by a factor.

Balanced brackets and Catalan numbers. The number of balanced strings of \(n\) pairs of one bracket type is the Catalan number \(C_n = \frac{1}{n+1}\binom{2n}{n}\): 1, 1, 2, 5, 14, 42, ...

Watch it step by step

The stack is drawn left (bottom) to right (top). Then a queue: values join on the right and leave from the left.

Variations and related ideas

• Monotonic stack: keep the stack increasing; each value pops everything bigger than itself. Solves "next smaller element", "largest rectangle in a histogram" and the stock-span problem in \(O(n)\).
• Two stacks make a queue: push to an "in" stack; when the "out" stack is empty, pour "in" into it. \(O(1)\) amortized per operation.
• Deque: both ends. Priority queue: removes the smallest, not the oldest: see binary heap.
• Shunting-yard (Dijkstra, 1961) uses a stack to turn 3 + 4 * 2 into postfix 3 4 2 * +.

See also

• Breadth-first search (queue) and depth-first search (stack)
• Binary heap: the priority queue
• Big-O: amortized cost

References

• T. H. Cormen et al., Introduction to Algorithms, 4th ed., §10.1 (stacks and queues) and Chapter 16 (amortized analysis, dynamic tables).
• R. Sedgewick, K. Wayne, Algorithms, 4th ed., §1.3 (bags, queues and stacks).