Stack

Imagine a stack of plates. You place one plate on top of another, and when you want to take a plate, you usually take the one from the top first.

The last plate you put on the stack is the first one you remove.

This is exactly the idea behind a stack data structure.

A stack follows the LIFO principle:

Last In, First Out

In other words, the element added last is the first element that comes out.

How a Stack Works

Suppose we add three numbers:

10
20
30

The stack looks like:

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

If we remove an element, 30 comes out first because it was added last.

After removing 30:

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

Then 20 would come out, followed by 10.

Main Stack Operations

A stack mainly has three important operations:

push()
pop()
peek()

push adds an element to the top.

pop removes the element from the top.

peek looks at the top element without removing it.

For example:

push(10)
push(20)
push(30)

The stack becomes:

30 ← Top
20
10

Then:

pop()

removes 30.

Push Operation

The push operation adds an element to the top of the stack.

Suppose our stack contains:

20
10

If we perform:

push(30)

we get:

30 ← Top
20
10

In Java, we can use the Stack class:

import java.util.Stack;

class Main {
    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();

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

        System.out.println(stack);
    }
}

Output:

[10, 20, 30]

The last element, 30, is the top of the stack.

Pop Operation

The pop operation removes the element from the top.

int value = stack.pop();

System.out.println(value);

Output:

30

The stack now contains:

20
10

The important thing is that pop() both returns and removes the top element.

Peek Operation

Sometimes we want to know what's at the top without removing it.

That's what peek() does.

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

If the stack is:

30
20
10

then:

peek() → 30

But 30 remains in the stack.

Checking Whether the Stack Is Empty

We can use:

stack.isEmpty()

For example:

if (stack.isEmpty()) {
    System.out.println("Stack is empty");
}

This is useful before performing operations that require an element to exist.

Stack Overflow and Underflow

Two common terms associated with stacks are overflow and underflow.

Stack overflow can happen when we try to add more elements than the stack can hold if the stack has a fixed capacity.

Stack underflow happens when we try to remove an element from an empty stack.

For example:

Empty Stack
    ↓
pop()
    ↓
Underflow

In Java's Stack, attempting to pop() an empty stack results in an exception.

Stack Using an Array

We can also implement a stack ourselves using an array.

For example:

class Stack {
    private int[] data;
    private int top;

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

    void push(int value) {

        if (top == data.length - 1) {
            System.out.println("Stack Overflow");
            return;
        }

        data[++top] = value;
    }

    int pop() {

        if (top == -1) {
            System.out.println("Stack Underflow");
            return -1;
        }

        return data[top--];
    }

    int peek() {

        if (top == -1) {
            System.out.println("Stack is empty");
            return -1;
        }

        return data[top];
    }
}

Here, top keeps track of the position of the top element.

Initially:

top = -1

which means the stack is empty.

After:

push(10);

top becomes 0.

After:

push(20);

top becomes 1.

And so on.

Stack Using a Linked List

A stack can also be implemented using a linked list.

For example:

Top
 ↓
30 → 20 → 10 → null

When we push 40:

Top
 ↓
40 → 30 → 20 → 10 → null

When we pop:

Top
 ↓
30 → 20 → 10 → null

The top of the stack can be represented by the head of the linked list.

This makes push and pop operations efficient.

Stack Time Complexity

For a well-designed stack, the main operations are very efficient:

These operations only work with the top element, so they don't need to search through the entire stack.

Real-Life Example

Think about the Undo feature in a text editor.

Suppose John performs these actions:

Type "Hello"
Type " World"
Delete "World"

The application can keep these actions in a stack.

When John presses Undo, the most recent action is reversed first.

Latest action
      ↓
Undo it
      ↓
Previous action
      ↓
Undo it

This follows:

Last action → First action to be undone

which is exactly LIFO.

Stack and Function Calls

Stacks are also used internally by programming languages.

When a method calls another method, Java uses a call stack to keep track of those method calls.

For example:

static void first() {
    second();
}

static void second() {
    third();
}

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

When first() calls second(), and second() calls third(), the call stack roughly looks like:

third()
second()
first()
main()

When third() finishes, it is removed first.

Then second() finishes, followed by first().

Again, this follows:

Last In → First Out

This is also why recursion uses the call stack.

Stack in Parentheses Problems

Stacks are commonly used to check whether brackets are balanced.

For example:

({[]})

is valid because every opening bracket has the correct closing bracket.

But:

({[})

is invalid.

We can use a stack to store opening brackets.

When we encounter a closing bracket, we check the top of the stack.

For example:

(
↓
(
[
↓
[
]
↓
Remove [
)
↓
Remove (

This is one of the classic DSA applications of a stack.

Stack in Expression Evaluation

Stacks are also useful when working with mathematical expressions.

For example:

2 + 3 * 4

Algorithms can use stacks to process operators and operands.

Stacks are also heavily used in problems involving:

• Infix expressions

• Prefix expressions

• Postfix expressions

• Expression evaluation

• Converting between expression formats

These topics become much easier once you understand the basic stack operations.

Stack in Browser History

Think about a browser's back button.

Suppose you visit:

Google
   ↓
YouTube
   ↓
Wikipedia

When you press Back, you return to Wikipedia's previous page first.

Then you go back again.

This can be modeled using stack-like behavior:

Latest page
     ↓
Previous page
     ↓
Older page

The most recent item is handled first.

Stack vs Queue

A stack and a queue are both linear data structures, but they follow different rules.

A stack follows:

LIFO
Last In, First Out

A queue follows:

FIFO
First In, First Out

Think about plates for a stack:

Last plate added → First plate removed

For a queue, think about people waiting in line:

First person arrives → First person served

We'll look at queues separately.

The Main Idea

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

The three operations you should remember are:

push() → Add to the top
pop()  → Remove from the top
peek() → View the top

For example:

push(10)
push(20)
push(30)

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

pop() → 30

Stacks are used in many important areas of DSA, including recursion, expression evaluation, parentheses matching, undo operations, browser history, and many algorithmic problems.

The key idea is simple:

The last element that goes into a stack is the first element that comes out.