Stack Data Structure Explained

A Stack is a linear data structure that follows the Last In, First Out principle, also known as LIFO. This means that the last element added to the stack is the first element removed from it.

Stacks are simple, but they are very important in computer science. They are used in function calls, undo systems, browser history, expression evaluation, syntax parsing, backtracking, and many real software systems.

Introduction

Data structures help developers organize and manage data efficiently. Arrays, linked lists, queues, stacks, trees, graphs, and hash tables all solve different types of problems.

A Stack is one of the most basic and useful data structures. It is easy to understand because it behaves like a real stack of plates. When you add a new plate, you place it on top. When you remove a plate, you remove the top plate first.

This behavior appears in many programming situations. Whenever the most recent item should be handled first, a Stack is often a clean and natural solution.

What Is a Stack?

A Stack is a collection of elements where insertion and removal happen from the same end. This end is usually called the top of the stack.

The Stack follows the LIFO rule:

Last In, First Out

This means the most recently added element is the first one to be removed.

The main idea is simple:

• Add new elements to the top of the stack.

• Remove elements from the top of the stack.

• Look at the top element without removing it when needed.

• Check whether the stack is empty before removing or reading the top element.

A Stack does not focus on random access. Its main purpose is to control access through the top.

Real-Life Analogy of a Stack

A common real-life example of a Stack is a pile of plates.

Imagine plates placed one above another:

Top → Plate C
      Plate B
      Plate A

Plate A was placed first. Plate B was placed after it. Plate C was placed last.

If we need to remove a plate, we remove Plate C first because it is on top. This matches the LIFO principle.

Last added: Plate C
First removed: Plate C

This simple idea is exactly how a Stack works in programming.

The LIFO Principle

LIFO stands for Last In, First Out. It means that the last item inserted into the stack is the first item removed from the stack.

For example, if we push values in this order:

10, 20, 30

The stack will look like this:

Top → 30
      20
      10

If we pop an element, the value 30 is removed first because it is at the top.

This behavior is different from a Queue, which follows FIFO, or First In, First Out.

Basic Stack Operations

A Stack usually supports a small set of important operations.

• push: Adds an element to the top of the stack.

• pop: Removes and returns the top element.

• peek: Returns the top element without removing it.

• isEmpty: Checks whether the stack has no elements.

• size: Returns the number of elements in the stack.

These operations are enough to solve many problems where recent data must be processed first.

Push Operation

The push operation adds a new element to the top of the stack.

If the stack is empty and we push 10, the stack becomes:

Top → 10

If we push 20, the stack becomes:

Top → 20
      10

If we push 30, the stack becomes:

Top → 30
      20
      10

Every new element is placed above the previous top element.

Pop Operation

The pop operation removes the top element from the stack and returns it.

Consider this stack:

Top → 30
      20
      10

If we call pop, the value 30 is removed.

Removed: 30

The stack becomes:

Top → 20
      10

If we call pop again, the value 20 is removed.

Removed: 20

The stack becomes:

Top → 10

The pop operation must be used carefully when the stack is empty. Removing from an empty stack is usually called stack underflow.

Peek Operation

The peek operation returns the top element without removing it.

Consider this stack:

Top → 30
      20
      10

If we call peek, the result is:

30

But the stack remains unchanged:

Top → 30
      20
      10

Peek is useful when we need to inspect the next element that would be removed, but we do not want to modify the stack.

isEmpty Operation

The isEmpty operation checks whether the stack contains any elements.

If the stack has no elements:

[]

Then isEmpty returns true.

If the stack contains elements:

[10, 20, 30]

Then isEmpty returns false.

This operation is important before calling pop or peek because those operations need a top element to exist.

Manual Run Example

Let us manually run a sequence of Stack operations.

push(10)
push(20)
push(30)
peek()
pop()
push(40)
pop()
pop()

We start with an empty stack:

Stack: []

Step 1: push(10)

We add 10 to the top of the stack.

Stack:
Top → 10

Step 2: push(20)

We add 20 above 10.

Stack:
Top → 20
      10

Step 3: push(30)

We add 30 above 20.

Stack:
Top → 30
      20
      10

Step 4: peek()

The top element is 30.

peek() returns 30

The stack does not change:

Stack:
Top → 30
      20
      10

Step 5: pop()

The top element 30 is removed.

pop() returns 30

The stack becomes:

Stack:
Top → 20
      10

Step 6: push(40)

We add 40 to the top.

Stack:
Top → 40
      20
      10

Step 7: pop()

The top element 40 is removed.

pop() returns 40

The stack becomes:

Stack:
Top → 20
      10

Step 8: pop()

The top element 20 is removed.

pop() returns 20

The stack becomes:

Stack:
Top → 10

This manual run shows the LIFO behavior clearly. The most recently pushed value is always the first one removed.

Stack Implementation Using an Array

A Stack is commonly implemented using an array. In this implementation, the end of the array represents the top of the stack.

For example:

[10, 20, 30]

The value 30 is the top element because it is at the end of the array.

Using the end of the array is efficient because many programming languages can add and remove elements from the end quickly.

Stack Pseudocode

class Stack:
    items = empty array

    push(value):
        add value to end of items

    pop():
        if items is empty:
            return error
        remove and return last item

    peek():
        if items is empty:
            return error
        return last item

    isEmpty():
        return length of items == 0

    size():
        return length of items

This pseudocode shows the main behavior of a Stack without depending on a specific programming language.

Stack Example in PHP

Here is a clean PHP implementation of a Stack using an array:

<?php

class Stack
{
    private array $items = [];

    public function push(mixed $value): void
    {
        $this->items[] = $value;
    }

    public function pop(): mixed
    {
        if ($this->isEmpty()) {
            throw new RuntimeException('Cannot pop from an empty stack.');
        }

        return array_pop($this->items);
    }

    public function peek(): mixed
    {
        if ($this->isEmpty()) {
            throw new RuntimeException('Cannot peek an empty stack.');
        }

        return $this->items[count($this->items) - 1];
    }

    public function isEmpty(): bool
    {
        return count($this->items) === 0;
    }

    public function size(): int
    {
        return count($this->items);
    }

    public function toArray(): array
    {
        return $this->items;
    }
}

$stack = new Stack();

$stack->push(10);
$stack->push(20);
$stack->push(30);

echo $stack->peek(); // 30
echo PHP_EOL;

echo $stack->pop(); // 30
echo PHP_EOL;

echo $stack->pop(); // 20

This implementation protects the stack from invalid operations by throwing an exception when pop or peek is called on an empty stack.

Stack Example in JavaScript

Here is a Stack implementation in JavaScript:

class Stack {
    constructor() {
        this.items = [];
    }

    push(value) {
        this.items.push(value);
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error('Cannot pop from an empty stack.');
        }

        return this.items.pop();
    }

    peek() {
        if (this.isEmpty()) {
            throw new Error('Cannot peek an empty stack.');
        }

        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }

    toArray() {
        return [...this.items];
    }
}

const stack = new Stack();

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

console.log(stack.peek()); // 30
console.log(stack.pop());  // 30
console.log(stack.pop());  // 20

The JavaScript implementation follows the same logic as the PHP version. The internal array stores the values, and the top of the stack is the end of the array.

Stack Implementation Using a Linked List

A Stack can also be implemented using a Linked List. In this version, the head of the linked list represents the top of the stack.

When we push a value, we insert a new node at the beginning. When we pop, we remove the first node.

Top → [30] → [20] → [10] → null

This implementation is useful when we want dynamic node-based memory behavior.

Linked List Stack Example in JavaScript

class StackNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListStack {
    constructor() {
        this.top = null;
        this.length = 0;
    }

    push(value) {
        const newNode = new StackNode(value);
        newNode.next = this.top;
        this.top = newNode;
        this.length++;
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error('Cannot pop from an empty stack.');
        }

        const removedValue = this.top.data;
        this.top = this.top.next;
        this.length--;

        return removedValue;
    }

    peek() {
        if (this.isEmpty()) {
            throw new Error('Cannot peek an empty stack.');
        }

        return this.top.data;
    }

    isEmpty() {
        return this.top === null;
    }

    size() {
        return this.length;
    }
}

In this version, push and pop both work at the head of the linked list, so they are efficient.

Array Stack vs Linked List Stack

Both arrays and linked lists can be used to implement a Stack.

An array-based stack is usually simpler and works well in most high-level programming languages. A linked-list-based stack is useful when learning node-based structures or when dynamic memory behavior is important.

Main differences include:

• Array stack is easier to implement.

• Linked list stack uses nodes and references.

• Array stack may occasionally resize internally.

• Linked list stack allocates memory node by node.

• Both can support push and pop in O(1) time.

For most practical JavaScript and PHP examples, an array-based stack is clear and enough.

Time Complexity of Stack Operations

Time complexity describes how the running time of an operation grows as the number of elements increases.

For a standard Stack, the main operations usually have these complexities:

• push: O(1)

• pop: O(1)

• peek: O(1)

• isEmpty: O(1)

• size: O(1)

• search: O(n)

Push, pop, and peek are constant-time operations because they work directly with the top of the stack.

Why Push Is O(1)

The push operation adds a new element to the top of the stack. It does not need to scan all elements.

For example:

Before:
Top → 20
      10

push(30)

After:
Top → 30
      20
      10

Only the top changes, so the operation takes constant time:

O(1)

Why Pop Is O(1)

The pop operation removes the top element. It does not need to search for the element because the top is already known.

Before:
Top → 30
      20
      10

pop()

After:
Top → 20
      10

Only the top is removed or updated, so the operation takes constant time:

O(1)

Why Search Is O(n)

Searching inside a Stack is not a standard Stack operation because Stacks are designed to access only the top element.

If we need to search for a value, we may need to inspect elements one by one.

Top → 30
      20
      10

To search for 10, the algorithm may need to check 30, then 20, then 10. In the worst case, it checks all elements.

Therefore, searching is:

O(n)

Space Complexity of a Stack

The space complexity of a Stack is O(n), where n is the number of elements stored in the stack.

Each pushed element requires memory. If the stack contains 100 values, it stores 100 values. If it contains 1,000 values, it stores 1,000 values.

Space complexity = O(n)

The operations themselves usually use only a small amount of additional memory, but the data structure stores n elements.

Stack Overflow and Stack Underflow

Two important Stack-related errors are stack overflow and stack underflow.

Stack overflow happens when a stack tries to grow beyond its allowed memory limit. This can happen in low-level fixed-size stacks or with too many recursive function calls.

Stack underflow happens when a program tries to pop or peek from an empty stack.

Stack: []

pop() → underflow error

Good Stack implementations should handle underflow safely by returning null, returning an error value, or throwing an exception.

Stacks and Function Calls

One of the most important real uses of a Stack is managing function calls. Programming languages use a call stack to remember active function calls.

When a function is called, a new stack frame is pushed onto the call stack. When the function finishes, its stack frame is popped.

main()
  calls login()
    calls validateInput()

The call stack may look like this:

Top → validateInput()
      login()
      main()

When validateInput() finishes, it is removed first. Then login() continues. This follows LIFO.

Stacks and Recursion

Recursion depends heavily on the call stack. Every recursive call adds a new function frame to the stack.

For example, a recursive factorial function creates multiple calls:

factorial(4)
factorial(3)
factorial(2)
factorial(1)

The last call must finish first, then control returns to the previous calls.

This is why recursion can cause stack overflow if the recursion depth becomes too large.

Stacks and Undo Systems

Stacks are commonly used to implement undo behavior.

Imagine a text editor where the user performs these actions:

Type A
Type B
Delete B

Each action can be pushed onto an undo stack:

Top → Delete B
      Type B
      Type A

When the user presses undo, the most recent action is reversed first. This is exactly LIFO behavior.

Stacks and Browser History

Browser history can also be understood using stacks.

When a user visits pages:

Home → About → Blog → Contact

The back button should return to the most recently visited previous page.

Top → Contact
      Blog
      About
      Home

When the user goes back, Contact is removed first, then Blog becomes the current previous page.

Stacks and Expression Evaluation

Stacks are used in evaluating mathematical expressions and checking syntax.

For example, when checking balanced parentheses:

(a + b) * (c + d)

The algorithm pushes opening brackets onto the stack and pops them when matching closing brackets appear.

If every opening bracket has a matching closing bracket in the correct order, the expression is balanced.

Balanced Parentheses Example

Let us check this expression:

{[()]}

The process is:

Read { → push {
Read [ → push [
Read ( → push (
Read ) → pop (, match found
Read ] → pop [, match found
Read } → pop {, match found

At the end, the stack is empty, so the brackets are balanced.

If the expression were:

{[(])}

The closing bracket would not match the most recent opening bracket, so the expression would be invalid.

Balanced Parentheses in JavaScript

function isBalanced(expression) {
    const stack = [];
    const pairs = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (const char of expression) {
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        }

        if (char === ')' || char === ']' || char === '}') {
            if (stack.length === 0) {
                return false;
            }

            const top = stack.pop();

            if (top !== pairs[char]) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

console.log(isBalanced('{[()]}')); // true
console.log(isBalanced('{[(])}')); // false

This is a classic Stack problem because the most recent opening bracket must be closed first.

Practical Example: Undo Stack in JavaScript

Here is a simple undo stack example:

class UndoManager {
    constructor() {
        this.undoStack = [];
    }

    addAction(action) {
        this.undoStack.push(action);
    }

    undo() {
        if (this.undoStack.length === 0) {
            return null;
        }

        return this.undoStack.pop();
    }
}

const manager = new UndoManager();

manager.addAction('Type A');
manager.addAction('Type B');
manager.addAction('Delete B');

console.log(manager.undo()); // Delete B
console.log(manager.undo()); // Type B

The most recent action is always undone first.

When Should Developers Use a Stack?

Developers should use a Stack when the most recent item should be processed first.

Stacks are useful when:

• Undo behavior is needed.

• Backtracking is needed.

• Function calls or recursion are involved.

• Syntax parsing is required.

• Expression evaluation is needed.

• Browser-like history behavior is needed.

• Depth-first search needs to be implemented iteratively.

The main signal is LIFO behavior. If the newest item should be handled first, a Stack may be the right structure.

When Not to Use a Stack

A Stack is not the right structure when elements need to be processed in the same order they were added.

Developers should avoid a Stack when:

• First-in, first-out behavior is required.

• Fast random access by index is needed.

• Elements need to be searched frequently.

• Priority-based processing is required.

• The oldest item should be processed first.

In those cases, a Queue, Array, Hash Table, or Priority Queue may be more suitable.

Stack vs Queue

Stacks and Queues 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

For example, a Stack is like a pile of plates. The last plate added is removed first.

A Queue is like a line of people waiting for service. The first person who enters the line is served first.

Main differences include:

• Stack removes the newest item first.

• Queue removes the oldest item first.

• Stack uses push and pop.

• Queue uses enqueue and dequeue.

• Stack is useful for undo and backtracking.

• Queue is useful for scheduling and waiting lines.

Common Mistakes When Learning Stacks

Beginners often understand the basic idea of a Stack, but they may still make implementation mistakes.

Common mistakes include:

• Confusing Stack with Queue.

• Removing from the wrong end of the array.

• Forgetting to handle empty stack cases.

• Using Stack when random access is needed.

• Assuming search is O(1).

• Ignoring stack overflow in recursive solutions.

• Changing the stack when only peek is needed.

The safest rule is simple: only the top element should be directly accessed.

Practical Checklist for Understanding Stacks

Before moving to Queues, Trees, Graphs, or advanced algorithms, developers should be able to answer these questions:

• What does LIFO mean?

• What is the top of a Stack?

• What does push do?

• What does pop do?

• What does peek do?

• Why are push and pop O(1)?

• What is stack underflow?

• How are stacks used in function calls?

• Why are stacks useful for undo systems?

• What is the difference between a Stack and a Queue?

If these questions are clear, the developer understands the real logic behind Stacks.

Advantages of Stacks

Stacks have several advantages.

• They are simple to understand.

• They are easy to implement.

• Push and pop are O(1).

• They naturally support LIFO behavior.

• They are useful for undo, recursion, parsing, and backtracking.

• They can be implemented using arrays or linked lists.

These advantages make Stacks one of the most important data structures for beginners and professionals.

Disadvantages of Stacks

Stacks also have limitations.

• They do not provide fast random access.

• They are not suitable for FIFO behavior.

• Searching inside a Stack is O(n).

• They can cause overflow if memory limits are reached.

• They are restrictive because only the top element is directly accessible.

These limitations are not problems when a Stack is used for the right purpose. They simply define when another data structure may be better.

Stacks in Real Software Projects

Stacks appear in real software projects in many forms, even when developers do not create a Stack class manually.

Common real-world uses include:

• Call stack management in programming languages.

• Undo and redo features in editors.

• Browser back navigation.

• Syntax parsing in compilers.

• Expression evaluation in calculators.

• Backtracking algorithms.

• Depth-first search in graphs.

• Routing history in applications.

Understanding Stacks helps developers understand how these systems work internally.

Conclusion

A Stack is a linear data structure that follows the Last In, First Out principle. The last element added to the stack is the first element removed.

The main Stack operations are push, pop, peek, isEmpty, and size. Push adds an element to the top, pop removes the top element, and peek reads the top element without removing it.

Stacks usually provide O(1) time complexity for push, pop, peek, isEmpty, and size operations. Searching inside a Stack takes O(n) because the structure is not designed for random access.

Stacks can be implemented using arrays or linked lists. They are used in function calls, recursion, undo systems, browser history, expression evaluation, syntax checking, and backtracking.

For developers learning Data Structures and Algorithms, Stacks are essential. They teach controlled access, LIFO behavior, memory thinking, and the foundation for many algorithmic techniques used in real software systems.