Stack Introduction

Introduction to stacks, implementation using arrays and linked list

Stack Data Structure

What is a Stack?

A stack is a linear data structure. It follows the LIFO rule, which means Last In, First Out.

• The last element we add is the first element we remove.
• Think of a pile of plates. We put a new plate on top, and we also take a plate from the top.

Core Operations

All operations work at the top of the stack. Each one takes constant time, which is O(1).

• Push: Add a new element to the top.
• Pop: Remove the most recent element from the top.
• Peek: Look at the top element without removing it.
• isEmpty: Check if the stack has no elements.

Example

Push 10  ->  [10]
Push 20  ->  [10, 20]
Push 30  ->  [10, 20, 30]
Peek     ->  30           (stack stays the same)
Pop      ->  30           (stack is now [10, 20])
Pop      ->  20           (stack is now [10])

Stack Errors

There are two common errors in a stack.

• Stack Overflow: This happens when we push an element into a stack that is already full. It applies to stacks with a fixed size.
• Stack Underflow: This happens when we pop or read from an empty stack.

Implementation Methods

We can build a stack in two main ways.

• Array-based:
  • It uses an array and a top pointer to track the last element.
  • It saves memory when we know the maximum size in advance.
• Linked list-based:
  • Each node points to the node below it. The top pointer points to the head of the list.
  • It can grow and shrink easily, so there is no size limit.

Solution 1: Stack Using an Array

In JavaScript, arrays already have push() and pop(). They work on the end of the array. So the end of the array is the top of our stack.

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

    // Push element to the top
    push(element) {
        this.items.push(element);
    }

    // Remove and return element from the top
    pop() {
        if (this.isEmpty()) return "Stack Underflow";
        return this.items.pop();
    }

    // View top element without removing it
    peek() {
        return this.isEmpty() ? null : this.items[this.items.length - 1];
    }

    // Check if stack is empty
    isEmpty() {
        return this.items.length === 0;
    }
}

How the Code Works

• items is the array that holds all the elements.
• push adds the element at the end of the array.
• pop first checks if the stack is empty. If yes, it returns "Stack Underflow". If not, it removes and returns the last element.
• peek returns the last element, or null if the stack is empty.
• isEmpty returns true when the array has no elements.

Note: A JavaScript array grows on its own, so this stack never gets a Stack Overflow.

Tip: Returning a text like "Stack Underflow" can be confusing, because a stack may also hold text values. In real projects, it is better to throw new Error("Stack Underflow").

Complexity

• Time Complexity: O(1) for every operation.
  • We only touch the last element, so we never loop through the array.
  • push is O(1) on average. Sometimes the array must resize, but this is rare.
• Space Complexity: O(n)
  • n is the number of elements in the stack.
  • Each operation itself uses only O(1) extra space.

Solution 2: Stack Using a Linked List

In this method, push and pop only change pointers at the head of the list. We do not need to resize any array.

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

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

    // Add element to the top (head)
    push(value) {
        const newNode = new Node(value);
        newNode.next = this.top;
        this.top = newNode;
        this.size++;
    }

    // Remove element from the top
    pop() {
        if (this.isEmpty()) return "Stack Underflow";
        const poppedValue = this.top.value;
        this.top = this.top.next;
        this.size--;
        return poppedValue;
    }

    // View top element
    peek() {
        return this.top ? this.top.value : null;
    }

    // Check if stack is empty
    isEmpty() {
        return this.top === null;
    }
}

How the Code Works

• Node: Each node holds a value and a next pointer to the node below it.
• top: It points to the node at the top of the stack. It is null when the stack is empty.
• push:
  • Create a new node.
  • Point its next to the current top.
  • Make the new node the new top.
• pop:
  • Save the value of the top node.
  • Move top to the next node.
  • Return the saved value.
• peek: Return the value of top, or null if the stack is empty.
• isEmpty: Return true when top is null.

Complexity

• Time Complexity: O(1) for every operation.
  • We only change the pointer at the head, so we never loop.
• Space Complexity: O(n)
  • We create one node for each element.
  • Each node also stores a next pointer, so it uses a little more memory than an array.

Why Are Stack Operations O(1)?

• A stack allows access to only the top element.
• We never search the whole structure to find the last element we added.
• The top pointer (or the end of the array) always shows the current position.

Comparison

Real-World Uses

• Undo / Redo: The stack keeps a history of actions, so we can go back.
• Browser history: The stack helps with the back and forward buttons.
• Function call stack: The stack tracks which functions are running right now.
• Expression checking: Compilers use a stack to check balanced brackets like (), {} and [].

Using a Stack to Make Algorithms Faster

Many problems need us to look back at old elements again and again. A simple solution can take O(n²) time. A stack can often reduce this to O(n).

The main idea is to use the stack to store "unresolved work". This is old information that we may need later.

• When a new element comes, compare it with the top of the stack.
• Remove old elements that are no longer useful.
• Keep only what we need for future decisions.

Each element is pushed once and popped at most once. So the total work stays O(n).

Summary

• A stack is a LIFO data structure: last in, first out.
• The main operations are push, pop, peek and isEmpty. All of them take O(1) time.
• Stack Overflow means pushing into a full stack. Stack Underflow means popping from an empty stack.
• We can build a stack with an array or a linked list.
  • Both give O(1) time for every operation.
  • Both use O(n) space.
• Stacks are used in undo/redo, browser history, the function call stack and bracket checking.
• A stack can reduce many O(n²) problems to O(n), because we keep only the useful past elements.