Stack

Q: How do I implement a stack in JavaScript?

Use a plain array: push() adds to the top, pop() removes from the top, and arr.at(-1) peeks at the top item. Both push() and pop() run in O(1) time.

In Turkish: Yığın

Updated September 30, 20262 min read

In short

A stack is a data structure that stores items in last in, first out (LIFO) order, so the most recently added item is always the first one removed.

What is a stack data structure?

A stack is a collection where items are added and removed at the same end, called the top. Adding an item is called a push, removing the top item is a pop, and looking at the top item without removing it is a peek. This rule is known as LIFO: last in, first out.

The classic analogy is a stack of plates. You put clean plates on top and take plates from the top, so the plate you added last is the first one you use. A stack is usually built on a dynamic array or a linked list, and push, pop, and peek all take O(1) time. With a dynamic array, push is amortized O(1), meaning O(1) on average even though the array occasionally has to grow.

Stacks show up all over programming. An editor's undo feature keeps a stack of recent changes, parsers use a stack to check that brackets are balanced, and depth-first search uses a stack to remember where to backtrack. The call stack, which tracks which function called which, is a stack too: each function call pushes a frame and each return pops it, and runaway recursion ends in a stack overflow when that space runs out.

A stack is often contrasted with a queue. A stack removes the newest item first (LIFO), while a queue removes the oldest item first (FIFO, first in, first out). Stack memory, the region where the call stack lives, is named after this data structure because it grows and shrinks in the same last in, first out way.

At a glance

Last in, first out: only the top of the stack can be added to or removed.

Key takeaways

A stack follows LIFO order: last in, first out.
The core operations are push, pop, and peek, and each takes O(1) time.
In Python, a list with append() and pop() works as a stack; in JavaScript, an array with push() and pop() does.
The call stack that tracks function calls is a real stack, which is why deep recursion can cause a stack overflow.
A stack removes the newest item first; a queue removes the oldest.

Example

Checking balanced brackets with a stackpython

def is_balanced(text):
    # Push every opening bracket; each closing bracket must match the top
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)  # push: O(1)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:  # pop: O(1)
                return False
    return not stack  # balanced only if nothing is left open

print(is_balanced("{[()]}"))  # True
print(is_balanced("([)]"))    # False

Readers ask

What is the difference between a stack and a queue?

A stack removes the most recently added item first (LIFO), like a pile of plates. A queue removes the item that has waited longest (FIFO), like a line at a ticket counter.

What is a stack overflow?

A stack overflow happens when the call stack runs out of space, usually because a recursive function keeps calling itself without reaching a base case. The program then crashes or raises an error, such as RecursionError in Python or RangeError: Maximum call stack size exceeded in JavaScript.

How do I implement a stack in JavaScript?

Use a plain array: push() adds to the top, pop() removes from the top, and arr.at(-1) peeks at the top item. Both push() and pop() run in O(1) time.

Often compared

Stack vs QueueA stack removes the newest item first (last in, first out, LIFO), while a queue removes the oldest first (first in, first out, FIFO), like plates versus a line.