Stack

#How does it work?

A stack is a data structure where elements are placed on top of each other, like a stack of plates. A new element always goes on top, and only the top element is accessible.

This rule is called LIFO (Last In, First Out): the element added last is the first one removed.

Stacks are easy to implement with an array or a linked list. With an array, a single counter called "top" is enough.

#Try it yourself

#Basic operations

push(x)

Adds x on top.

pop()

Removes and returns the top element. Fails if the stack is empty (underflow).

peek() / top()

Reads the top element without removing it.

isEmpty()

Tells whether the stack has any elements.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class Stack:
    def __init__(self) -> None:
        self._items: list[int] = []  # the top of the stack is the end of the list

    def push(self, value: int) -> None:
        self._items.append(value)

    def pop(self) -> int:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items.pop()

    def peek(self) -> int:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items[-1]

    def __len__(self) -> int:
        return len(self._items)


s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())   # 3: last in, first out
print(s.peek())  # 2
print(len(s))    # 2

#Complexity

Every basic operation only touches the top element, so it runs in constant time. To reach an element in the middle you would have to pop everything above it; a stack isn't meant for that.

#When to use it?

Function calls (the call stack), undo, the browser's back button, bracket matching, expression evaluation and depth-first search (DFS) all use stacks. Whenever you need "undo the most recent thing first", think of a stack.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Depth-First Search (DFS)
• Deque
• Graph