Stack

Why we need a Stack

What is a stack

A queue follows the opposite rule, FIFO (First In, First Out), like a line at a ticket counter. If the oldest item should come out first, you need a queue, not a stack.

Only the top is open

This is the part beginners forget, so it is worth stating clearly.

You give up access to the middle. In return, every operation stays very fast and very simple.

The operations

All five take O(1) time. That means the work stays the same whether the stack holds 10 items or 10 million. You are always touching only the top.

Out of these, only push and pop change the stack. The other three just read it.

Press pop() on an empty stack, or push() on a full one, and watch what the stack refuses to do. Both of those refusals have a name, further down the page.

In code

stack = [] stack.append(10)      # pushstack.append(20)      # push print(stack[-1])      # peek  -> 20print(stack.pop())    # pop   -> 20print(stack[-1])      # peek  -> 10print(len(stack))     # size  -> 1print(len(stack) == 0)  # isEmpty -> False

Most languages already give you a ready-made stack, so you rarely build one yourself:

• Python: a normal list with append() and pop()
• C++: std::stack
• Java: ArrayDeque (preferred over the older Stack class)
• JavaScript: a normal array with push() and pop()

Overflow and underflow

Two errors come up in almost every exam and interview.

How a stack is built

There are two common ways, and both keep all operations at O(1).

For most beginner work, the array version is enough.

The stack your program is already using

This is the idea that makes stacks stick.

Every time a function is called, the computer creates a stack frame for it. The frame holds that function's local variables and the address to return to. That frame is pushed onto the call stack. When the function finishes, its frame is popped and control goes back to the caller.

This is why the function called last is always the one that finishes first.

It is also why endless recursion crashes with an error named after this very structure: stack overflow. The program keeps pushing frames and never pops any.

Where stacks are used

• Undo (Ctrl+Z): every action is pushed, undo pops the most recent one
• Browser back button: visited pages are pushed, back pops the last one
• Bracket checking in compilers: making sure { [ ( ) ] } is written correctly
• Expression evaluation: converting infix to postfix, and solving postfix
• DFS (Depth-First Search): using an explicit stack or recursion
• Backtracking: mazes, N-Queens, Sudoku. Push a choice, pop it when it fails

The pattern is easy to spot. A stack fits whenever you need to remember what you were doing just before this, and then step back out of it.

Worked example: balanced brackets

Input: { [ ( ) ] }

Rule: push every opening bracket. On a closing bracket, pop one and check that the pair matches. At the end, the stack must be empty.

The stack is empty at the end, so the input is balanced.

The input is invalid if any of these happen:

• a pop gives a bracket that does not match
• a closing bracket arrives when the stack is empty
• the stack is not empty after reading everything

Try tracing { ( ] ) on paper. You will hit a mismatch at ].

When a stack is the wrong choice

Pick something else if:

• the oldest item should come out first, use a queue
• you need to read or search the middle, use an array or list
• you need the smallest or largest item quickly, use a heap

Ask one question before choosing: which item do I need next, the newest or the oldest? Newest means stack.

Common mistakes

• Popping without checking whether the stack is empty
• Mixing up pop (removes the item) and peek (does not remove it)
• Using a stack where the order should be FIFO
• Expecting to reach the middle items
• In Python, pop() removes from the top and is fast, but pop(0) removes from the front and is slow

Quick recap

• A stack is a pile. Last in, first out.
• Push and pop happen at the top only, and both are O(1).
• Popping an empty stack is underflow. Pushing a full one is overflow.
• Your own function calls run on a stack.
• Used in undo, browser history, bracket checking, DFS and backtracking.