Stack Data Structure: Introduction Tutorial

What Is a Stack?

A stack is a linear data structure in which elements are added and removed from the same end, called the top of the stack.

A stack follows the LIFO (Last In, First Out) principle. This means the element added most recently is the first element removed.

Real-world example: Imagine a stack of plates. When you place a new plate on top, it becomes the first plate you can remove. You cannot normally remove a plate from the middle without first removing the plates above it.

Understanding LIFO

LIFO stands for Last In, First Out. If elements are inserted in the order A, B, and C, then C is removed first.

Push A
Push B
Push C

Stack:
Top
 ↓
C
B
A

Pop → C
Pop → B
Pop → A

The last element inserted is always the first element removed. This ordering is the defining characteristic of a stack.

Basic Stack Structure

A stack can be visualized as a collection where only the top element is directly accessible for insertion and removal.

        TOP
         ↓
      +-----+
      |  C  |
      +-----+
      |  B  |
      +-----+
      |  A  |
      +-----+

New elements are added above the current top, and elements are removed from the top.

Core Stack Operations

A stack typically provides a small set of operations for managing its elements.

Operation	Purpose
`push()`	Adds an element to the top
`pop()`	Removes and returns the top element
`peek()`	Returns the top element without removing it
`isEmpty()`	Checks whether the stack contains elements
`size()`	Returns the number of elements

Push Operation

The push operation adds an element to the top of the stack. If the stack contains A and B, pushing C places C above B.

Stack before push:

B
A

push(C)

Stack after push:

C
B
A

In a properly implemented stack, adding an element to the top is typically an O(1) operation.

Pop Operation

The pop operation removes and returns the element at the top of the stack. It is the operation that demonstrates the LIFO principle most directly.

Stack:

C
B
A

pop()

Removed: C

Remaining:

B
A

A pop operation is typically O(1) because the stack only needs to access its top element.

Peek Operation

The peek operation returns the top element without removing it. It is useful when a program needs to inspect the next item that would be removed.

Stack:

C
B
A

peek() → C

Stack remains unchanged.

Checking Whether a Stack Is Empty

The isEmpty() operation determines whether the stack contains any elements. This check is important before attempting to remove an element from an empty stack.

const stack = [];

console.log(stack.length === 0);
// true

stack.push("A");

console.log(stack.length === 0);
// false

Stack Implementation Using an Array

An array is one of the simplest ways to implement a stack. JavaScript arrays already provide push() and pop(), which operate naturally at the end of the array.

const stack = [];

stack.push("A");
stack.push("B");
stack.push("C");

console.log(stack);
// ["A", "B", "C"]

console.log(stack.pop());
// "C"

console.log(stack.pop());
// "B"

In this implementation, the end of the array represents the top of the stack.

Creating a Stack Class

A custom class can make the stack behavior more explicit and provide controlled operations such as push, pop, peek, and isEmpty.

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

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

  pop() {
    if (this.isEmpty()) {
      return null;
    }

    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }

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

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

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

const stack = new Stack();

stack.push("HTML");
stack.push("CSS");
stack.push("JavaScript");

console.log(stack.peek());
// JavaScript

console.log(stack.pop());
// JavaScript

console.log(stack.size());
// 2

Stack Implementation Using a Linked List

A stack can also be implemented using a linked list. The head of the linked list can represent the top of the stack.

Adding or removing the head node can be performed in constant time without shifting other nodes.

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

class Stack {
  constructor() {
    this.top = null;
    this.count = 0;
  }

  push(value) {
    const node = new Node(value);

    node.next = this.top;
    this.top = node;
    this.count++;
  }

  pop() {
    if (this.top === null) {
      return null;
    }

    const value = this.top.value;
    this.top = this.top.next;
    this.count--;

    return value;
  }

  peek() {
    return this.top === null ? null : this.top.value;
  }

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

  size() {
    return this.count;
  }
}

const stack = new Stack();

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

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

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

Array vs Linked List Stack

Both arrays and linked lists can implement a stack efficiently. The choice depends on the requirements of the application and the language being used.

Feature	Array	Linked List
Push	O(1) amortized	O(1)
Pop	O(1)	O(1)
Memory layout	Contiguous or dynamically managed	Separate nodes
Extra node memory	No	Yes, for links

Stack Overflow and Stack Underflow

Two conditions are commonly discussed when learning stacks: overflow and underflow.

Stack Overflow

Stack overflow occurs when an application attempts to add more elements than a fixed-capacity stack can hold. It can also refer to excessive function-call depth exhausting the program's call stack.

Stack Underflow

Stack underflow occurs when a program attempts to remove or inspect an element from an empty stack. A well-designed implementation should handle this condition explicitly.

const stack = [];

if (stack.length === 0) {
  console.log("Stack is empty");
} else {
  console.log(stack.pop());
}

Stack Complexity

When a stack is implemented correctly, its primary operations are efficient because they only interact with the top element.

Operation	Time Complexity	Purpose
Push	O(1)	Add an element to the top
Pop	O(1)	Remove the top element
Peek	O(1)	View the top element
isEmpty	O(1)	Check whether the stack is empty
Search	O(n)	Find an arbitrary element

Real-World Applications of Stacks

Stacks are useful whenever the most recently added item needs to be processed first. This simple rule appears in many areas of software development.

Function calls: programming languages use call stacks to manage active function calls.
Undo operations: editors can store recent actions and reverse them in LIFO order.
Browser navigation: previous states can be tracked to support backward navigation.
Expression evaluation: stacks help process operands and operators.
Parentheses matching: nested delimiters can be validated using a stack.
Backtracking: previous decisions can be stored and reversed.
Depth-first search: iterative DFS uses a stack to control traversal.
Syntax parsing: nested structures can be processed using stack-based techniques.

Stack and Function Calls

The call stack is one of the most important practical examples of stack behavior. When one function calls another, the new function call is placed above the previous call.

function first() {
  second();
}

function second() {
  third();
}

function third() {
  console.log("Running third");
}

first();

Conceptually, the active calls form a stack:

Top
 ↓
third()
second()
first()

When third() finishes, it is removed first. Then second() resumes, followed by first().

Stack and Recursion

Recursive functions are closely related to stacks because each recursive call creates another function-call frame. Those frames remain active until the recursive calls return.

function countdown(n) {
  if (n === 0) {
    return;
  }

  console.log(n);
  countdown(n - 1);
}

countdown(3);

The calls conceptually build up as:

countdown(0)
countdown(1)
countdown(2)
countdown(3)

As each call returns, the most recent active call finishes first. Excessive recursion depth can eventually cause a stack overflow.

Stack vs Queue

Stacks and queues are both linear data structures, but they use different ordering rules.

Feature	Stack	Queue
Ordering	LIFO	FIFO
Insertion	Top	Rear
Removal	Top	Front
Common example	Undo history	Task processing
Graph traversal	DFS	BFS

When Should You Use a Stack?

A stack is a good choice when the problem naturally requires the most recent item to be processed first.

Look for These Signals

The problem requires LIFO ordering.
The most recent decision must be undone first.
The data contains nested structures.
You need to reverse a sequence.
You need to track previous states.
You are implementing iterative depth-first traversal.
You are processing operators and operands.

Common Stack Mistakes

Removing elements from the wrong end of the data structure.
Forgetting to handle an empty stack before calling pop().
Confusing LIFO behavior with FIFO behavior.
Using a stack when random access to arbitrary elements is the primary requirement.
Ignoring stack capacity when implementing a fixed-size stack.
Creating excessive recursive calls that can exhaust the call stack.

Key Takeaways

A stack is a linear data structure based on the LIFO principle.
Elements are inserted and removed from the top.
The primary operations are push, pop, peek, isEmpty, and size.
Push, pop, and peek are typically O(1) operations.
Stacks can be implemented using arrays or linked lists.
Function calls and recursion rely heavily on stack behavior.
Stacks are useful for undo operations, expression processing, backtracking, and DFS.
Stack overflow and underflow are important conditions to handle.
The key signal for a stack problem is a need for the most recently added item to be processed first.

Topics

Stack Data Structure: Introduction