Stacks in DSA: The LIFO Data Structure Explained

A stack is a linear data structure that follows the LIFO rule — Last In, First Out. You add and remove elements from the same end, called the top, so the most recently added item is always the first one out. Think of a stack of plates: you put a clean plate on top and you take the top plate to use. This page explains the LIFO idea, the core operations, and where stacks show up in real software.

The LIFO idea

Only the top of a stack is reachable. You cannot peek at or remove an item in the middle without removing everything above it first. That single constraint is what makes a stack so useful: it naturally remembers things in reverse order of arrival, which is exactly what you want for “undo the last action” or “return to the previous function”.

Core operations

A stack exposes a tiny, fixed set of operations — all O(1):

• push(x) — add x to the top.
• pop() — remove and return the top item.
• peek() / top() — look at the top item without removing it.
• isEmpty() — is the stack empty?
• size() — how many items are stored.

Here is the lifecycle of a stack using each language’s idiomatic built-in (we cover building your own in implementing a stack):

#include <stack>
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);          // stack (top → bottom): 3, 2, 1
int top = s.top();  // 3 — peek
s.pop();            // removes 3
int n = s.size();   // 2
bool empty = s.empty();

Deque<Integer> s = new ArrayDeque<>();
s.push(1);
s.push(2);
s.push(3);            // top → bottom: 3, 2, 1
int top = s.peek();   // 3 — peek
s.pop();              // removes and returns 3
int n = s.size();     // 2
boolean empty = s.isEmpty();

const s = [];
s.push(1);
s.push(2);
s.push(3);                  // top is the last element: 3
const top = s[s.length - 1]; // 3 — peek
s.pop();                    // removes and returns 3
const n = s.length;         // 2
const empty = s.length === 0;

s = []
s.append(1)
s.append(2)
s.append(3)        # top is the last element: 3
top = s[-1]        # 3 — peek
s.pop()            # removes and returns 3
n = len(s)         # 2
empty = not s

For beginners: “push” means add, “pop” means remove the top. The words come from spring-loaded plate dispensers — pushing a plate down loads the next, popping releases the top one.

Why the LIFO order matters

Every operation touches only the top, so there is no shifting or searching — push and pop are always O(1) time. Storage is O(n) for n items. This predictable, constant-time behavior is why stacks underpin so many algorithms.

Where stacks are used

Stacks are everywhere, often hidden:

• The call stack — every function call pushes a frame; returning pops it. Recursion is a stack.
• Undo/redo in editors — each action is pushed; undo pops the latest.
• Browser history — the back button pops the page you came from.
• Expression evaluation and syntax checking — matching brackets, converting infix to postfix.
• Backtracking — DFS on graphs and trees uses an explicit or implicit stack.

Going deeper: A stack is an abstract data type — a contract (LIFO + these operations), not a specific implementation. You can back it with an array or a linked list; both give O(1) push/pop.

When to use a stack

Reach for a stack whenever the most recent unfinished item is the one you need next: reversing a sequence, matching nested structures, tracking “where was I before this step”, or any depth-first exploration. If instead you need first-come-first-served order, you want a queue.

Next: implement a stack from scratch, then explore real stack applications. Ready to practice? See the stacks & queues exercises.