Stacks

Why should you care?

A stack is one of the simplest and most useful data structures in computer science. It organizes data according to one fundamental rule:

Last In, First Out (LIFO).

The last item added to the stack is the first item removed.

Stacks appear everywhere in programming:

• Function calls and the call stack
• Undo/redo operations
• Browser history
• Expression evaluation
• Parentheses matching
• Depth-first search
• Backtracking algorithms
• Memory management

If you've learned about the call stack, you're already using the idea of a stack—you just haven't necessarily implemented one yourself.

---

The Problem

Suppose you have several tasks that need to be processed, but the most recently added task should be handled first.

For example:

Task A
Task B
Task C  ← added last

You want:

C → B → A

An ordinary array doesn't automatically enforce this behavior.

We need a data structure that restricts how elements are added and removed so that:

The newest element always comes out first.

That's the problem a stack solves.

---

The Concept

A stack is a linear data structure that follows the LIFO principle:

Last In
   ↓
First Out

Imagine:

        ┌─────┐
        │ 30  │ ← TOP
        ├─────┤
        │ 20  │
        ├─────┤
        │ 10  │
        └─────┘

If we remove an element, 30 comes out first.

Then:

        ┌─────┐
        │ 20  │ ← TOP
        ├─────┤
        │ 10  │
        └─────┘

The two fundamental operations are:

Push

Add an element to the top.

Before:

10 → 20

Push(30)

After:

10 → 20 → 30
          ↑
         TOP

Pop

Remove the element from the top.

Before:

10 → 20 → 30
          ↑
         TOP

Pop()

After:

10 → 20
      ↑
     TOP

There is also another important operation:

Peek

Look at the top element without removing it.

10 → 20 → 30
          ↑
         TOP

Peek() → 30

---

Simple Explanation

Think of a stack of plates.

You put plates on top:

   Add
    ↓
  ┌───┐
  │ 3 │
  ├───┤
  │ 2 │
  ├───┤
  │ 1 │
  └───┘

If you want to take a plate, you naturally take the top plate.

You can't conveniently remove the bottom plate without first removing the plates above it.

So:

Push:  1 → 2 → 3
                    ↑
                   TOP

Pop:   3 comes out first

That's Last In, First Out.

---

Real-world Analogy

Imagine a pile of documents on your desk.

You place them one on top of another:

Document A
Document B
Document C
Document D ← newest

If you always pick up the top document first:

D → C → B → A

The last document you placed down is the first one you pick up.

That's exactly how a stack behaves.

---

Code Example

A stack can be implemented using an array.

Here's a simple Java implementation:

class Stack {
    int[] data;
    int top = -1;

    Stack(int size) {
        data = new int[size];
    }

    void push(int value) {
        data[++top] = value;
    }

    int pop() {
        return data[top--];
    }

    int peek() {
        return data[top];
    }
}

We can use it like this:

Stack stack = new Stack(5);

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());

Output:

30
30
20

Let's follow what happened:

push(10)

[10]
 ↑
TOP

Then:

push(20)

[20] ← TOP
[10]

Then:

push(30)

[30] ← TOP
[20]
[10]

peek() gives:

30

but doesn't remove it.

pop() removes:

30

leaving:

[20] ← TOP
[10]

Java's built-in Stack-like structure

In modern Java, Deque is generally preferred for stack behavior:

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.pop());

Output:

30

---

Common Mistakes

Mistake 1: Confusing LIFO with FIFO

A stack uses:

LIFO
Last In → First Out

A queue uses:

FIFO
First In → First Out

For example:

Stack:

10 → 20 → 30

pop() → 30

Whereas a queue would remove:

10

The difference is which end elements leave from.

---

Mistake 2: Thinking peek() removes an element

These operations are different:

push() → add
pop()  → remove
peek() → inspect

For example:

Stack:

10
20
30 ← TOP

After:

peek()

the stack remains:

10
20
30 ← TOP

After:

pop()

it becomes:

10
20 ← TOP

---

Mistake 3: Popping from an empty stack

Consider:

Stack:

(empty)

Calling:

stack.pop();

is invalid.

This situation is called stack underflow.

Similarly, if you're implementing a fixed-size stack using an array and try to push when it is already full, you have stack overflow at the data-structure level.

Don't confuse this with the call-stack overflow that occurs when a program exhausts its call-stack memory, often because of excessive recursion.

---

Advanced Notes

1. Stack complexity

A properly implemented stack provides:

Operation	Time Complexity
Push	O(1)
Pop	O(1)
Peek	O(1)
Search	O(n)

The key advantage is that stack operations happen at the top, so no shifting of elements is normally required.

---

2. Stack using an array

An array implementation can track the top using an integer:

data:
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │    │    │
└────┴────┴────┴────┴────┘
          ↑
         TOP

Here:

top = 2

A push increments top:

top = top + 1

A pop decrements it:

top = top - 1

This makes both operations constant time.

---

3. Stack using a linked list

Stacks can also be implemented using linked lists.

TOP
 ↓
[30] → [20] → [10] → null

Push:

new node
   ↓
[40] → [30] → [20] → [10]
 ↑
TOP

Pop simply removes the first node.

This is efficient because inserting and removing from the beginning of a linked list are both O(1).

---

4. The call stack

One of the most important uses of stacks is the function call stack.

Consider:

void main() {
    functionA();
}

void functionA() {
    functionB();
}

void functionB() {
    System.out.println("Hello");
}

When the program runs:

main()
  ↓
functionA()
  ↓
functionB()

The calls are placed onto the call stack:

┌──────────────┐
│ functionB()  │ ← TOP
├──────────────┤
│ functionA()  │
├──────────────┤
│ main()       │
└──────────────┘

When functionB() finishes, it is removed first.

Then:

functionA()

finishes.

Then:

main()

finishes.

That's LIFO in action.

---

5. Recursion uses the stack

Consider:

void count(int n) {
    if (n == 0)
        return;

    System.out.println(n);
    count(n - 1);
}

Calling:

count(3);

creates:

count(3)
   ↓
count(2)
   ↓
count(1)
   ↓
count(0)

The calls are placed onto the call stack.

When the base case is reached, the functions return in reverse order:

count(0)
   ↑
count(1)
   ↑
count(2)
   ↑
count(3)

This is why understanding stacks is essential for understanding recursion.

---

6. Stack overflow

Every function call requires some amount of call-stack memory.

If recursion continues without reaching a base case:

void infinite() {
    infinite();
}

the call stack keeps growing:

infinite()
infinite()
infinite()
infinite()
...

Eventually, available call-stack memory is exhausted.

The program can then produce a StackOverflowError in Java.

---

The Bigger Picture

Stacks connect directly to several fundamental programming concepts:

Variables
   ↓
Memory
   ↓
Functions
   ↓
Call Stack
   ↓
Recursion
   ↓
Stacks
   ↓
DFS / Backtracking / Parsing

Stacks are also heavily used by algorithms.

Depth-First Search

A graph traversal can use a stack:

       A
      / \
     B   C
    /
   D

DFS explores deeply before returning:

A → B → D → C

Expression evaluation

Stacks are also useful for evaluating expressions such as:

(10 + 20) × 30

and checking balanced parentheses:

{ [ ( ) ] }

For example:

(
(
( )
 ← matched

A stack can keep track of opening brackets and remove them when matching closing brackets appear.

---

The Most Important Mental Model

A stack is a controlled pile where you can only interact with the top.

Remember these three operations:

             TOP
              ↓
           ┌─────┐
 PUSH  →   │ 30  │
           ├─────┤
           │ 20  │
           ├─────┤
 POP   ←   │ 10  │
           └─────┘

PEEK → Look at 30 without removing it

The single rule to remember is:

              LIFO
       Last In → First Out

Once you understand this, many seemingly unrelated concepts—function calls, recursion, undo operations, DFS, and expression parsing—start looking like variations of the same idea.

---

Summary

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.

The key ideas are:

• Push adds an element to the top.
• Pop removes the top element.
• Peek looks at the top without removing it.
• Push, pop, and peek are typically O(1).
• Stacks can be implemented using arrays or linked lists.
• The call stack manages active function calls.
• Recursion relies heavily on the call stack.
• Stacks are used in DFS, backtracking, parsing, expression evaluation, and undo systems.
• Stack overflow can occur when the call stack exhausts its available memory.

A stack is more than a data structure—it is the fundamental mechanism behind the way programs remember what they are currently doing and how they should return from it.