Stacks

# ai# programming# productivity# tutorial

Shankar L

Why should you care? A stack is one of the simplest and most useful data structures in...

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:

but doesn't remove it.

pop() removes:

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:

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:

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:

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.

Stacks

Why should you care?

The Problem

The Concept

Push

Pop

Peek

Simple Explanation

Real-world Analogy

Code Example

Java's built-in Stack-like structure

Common Mistakes

Mistake 1: Confusing LIFO with FIFO

Mistake 2: Thinking peek() removes an element

Mistake 3: Popping from an empty stack

Advanced Notes

1. Stack complexity

2. Stack using an array

3. Stack using a linked list

4. The call stack

5. Recursion uses the stack

6. Stack overflow

The Bigger Picture

Depth-First Search

Expression evaluation

The Most Important Mental Model

Summary

Mistake 2: Thinking `peek()` removes an element