Stack

A stack follows LIFO — Last In, First Out. The last element added is the first one to be removed, like a stack of plates.

Two Core Operations

• Push (Put / Append) — add an element to the top
• Pop — remove the element from the top

Both are always O(1) — you only ever touch the top of the stack.

Push 1:  [1]
Push 2:  [1] → [2]   ← top is 2

Pop:     [1]          ← returns 2, top is now 1
Pop:     []           ← returns 1, stack is empty

Visual

Elements are chained like a linked list, where each node points to the previous one:

bottom          top
  [1]    ←    [2]
              ↑
           always here (push/pop)

Adding node 2 makes it point back to node 1. Popping removes node 2 and the top becomes node 1 again.

In Python

Python lists work as a stack out of the box:

stack = []

stack.append(1)   # push → [1]
stack.append(2)   # push → [1, 2]
stack.append(3)   # push → [1, 2, 3]

stack.pop()       # → 3  (last in, first out)
stack.pop()       # → 2

For thread-safe usage:

from queue import LifoQueue

stack = LifoQueue()
stack.put(1)
stack.put(2)
stack.get()  # → 2

Real-World Uses

• Call stack — your program uses a stack to track function calls. Each function call is pushed; when it returns, it is popped.
• Undo/redo — every action is pushed onto a stack. Undo pops the last action.
• Browser history — the back button pops the last visited page.
• Balanced parentheses — a classic interview problem solved with a stack.

Big O Summary

Stack vs Queue

Key Takeaways

• Stack = LIFO: the last element in is the first one out.
• Only two operations matter: push and pop, both O(1).
• In Python, a plain list with .append() and .pop() is all you need.