00:00

Stack Data Structure

Last updated:

A stack is a collection in which elements are added and removed at the same end, so the element added last is always the first one to come out. This rule is called LIFO (Last In, First Out). Stacks appear everywhere in programming: the JVM uses one to manage method calls, compilers use them to check brackets and evaluate expressions, and editors use them for undo.

This tutorial explains the stack operations, their cost, the two common ways to implement a stack in Java, and where stacks are useful.

What is a Stack Data Structure?

A stack is a linear data structure with a single access point called the top. New elements are placed on the top, and only the element on the top can be read or removed. Think of a pile of plates: you put a plate on the pile and take a plate from the pile, both at the top.

Because of this LIFO order, a stack naturally reverses things and remembers "where you came from", which is why it is used for method calls, undo/redo, expression parsing, backtracking and the back button of a browser.

Operations on Stack Data Structure

A stack supports these basic operations:

  1. push() - adds an element on the top.

  2. pop() - removes the top element and returns it.

  3. peek() - returns the top element without removing it (also called top()).

  4. isEmpty() - tells whether the stack has no elements.

  5. isFull() - tells whether a fixed-size stack has no free space. A stack that can grow, such as one built on a linked list or on ArrayDeque, does not need this operation.

Stack working flow: elements are pushed onto and popped from the top

The snippets below are methods of an array-based stack with three fields: int[] intArray (the storage), int capacity (its length) and int top, the index of the top element, which is -1 while the stack is empty. The complete class is on the Stack Implementation using Array page.

1. Push Operation in Stack

Push places a new element on the top. In an array-based stack, top moves up by one and the value is stored at the new top index.

If the array is already full, there is no room for the element. This is called stack overflow.

Stack push operation: a new element is placed on the top

Algorithm for Push Operation:

  1. If the stack is full (top == capacity - 1), report overflow and stop.

  2. Otherwise increase top by 1.

  3. Store the new element at intArray[top].

Example of push operation in Stack

ArrayStack.java
// Push: add a value on top of the stack
public void push(int data) {
  if (isFull()) {
    System.out.println("Stack Overflow");
    return;
  }
  // move top up by one, then store the value there
  intArray[++top] = data;
}

2. Pop Operation in Stack

Pop removes the top element and returns it. Elements therefore come out in the reverse of the order in which they were pushed.

Popping from an empty stack is an error called stack underflow.

Stack pop operation: the top element is removed

Algorithm for Pop Operation:

  1. If the stack is empty (top == -1), report underflow and stop.

  2. Otherwise read the element at intArray[top].

  3. Decrease top by 1 and return the element that was read.

Example of pop operation in Stack

ArrayStack.java
// Pop: remove and return the value on top of the stack
public int pop() {
  if (isEmpty()) {
    throw new IllegalStateException("Stack Underflow");
  }
  // read the top value, then move top down by one
  return intArray[top--];
}

3. Top or Peek Operation in Stack

Peek (or top) returns the top element but leaves it on the stack.

Stack peek or top operation: the top element is read without removing it

Algorithm for Top or Peek Operation:

  1. If the stack is empty (top == -1), there is no element to return; report the error.

  2. Otherwise return intArray[top] without changing top.

Example of peek or Top operation in Stack

ArrayStack.java
// Peek: return the top value without removing it
public int peek() {
  if (isEmpty()) {
    throw new IllegalStateException("Stack is empty");
  }
  return intArray[top];
}

4. isEmpty Operation in Stack

isEmpty returns true when the stack holds no elements and false otherwise. It should be checked before pop() or peek().

Stack isEmpty operation

Algorithm for isEmpty Operation:

  1. If top == -1, return true.

  2. Otherwise return false.

Example of isEmpty operation in Stack

ArrayStack.java
// isEmpty: true when no element has been pushed
public boolean isEmpty() {
  return top == -1;
}

5. isFull Operation in Stack

isFull returns true when every slot of a fixed-size stack is used, and false otherwise. It should be checked before push().

Stack isFull operation

Algorithm for isFull Operation:

  1. If top == capacity - 1, return true.

  2. Otherwise return false.

ArrayStack.java
// isFull: true when every slot of the array is used
public boolean isFull() {
  return top == capacity - 1;
}

Complexity Analysis of Operations on Stack

Every operation touches only the top of the stack, so none of them depends on how many elements are stored:

Operations Time Complexity Space Complexity
push() O(1) O(1)
pop() O(1)

O(1)

top() or peek() O(1) O(1)
isEmpty() O(1) O(1)
isFull() O(1) O(1)

For a stack built on a growable array (such as ArrayDeque), push() is O(1) amortized: an occasional push has to copy the array into a larger one.

Stack implementation in Java

A stack is usually built on one of two structures:

  1. Using Array

  2. Using Linked List

Stack implementation using an array

An integer top records the index of the top element. push() increments top and stores the value at that index; pop() returns the value at top and then decrements it. The array has a fixed capacity, so the stack can overflow. Read more...

Stack implementation using linked list

The head of a singly linked list acts as the top. push() creates a new node whose next refers to the current top and then makes the new node the top. pop() saves the top node's value, moves top to top.next, and returns the saved value. The stack grows as needed and never overflows (until memory runs out). Read more...

Applications of Stack Data Structure

  • Method calls: the JVM pushes a frame for every call and pops it on return.
  • Expression evaluation and conversion (infix, postfix, prefix).
  • Checking balanced brackets in code or text.
  • Undo and redo in editors.
  • Back navigation in web browsers.
  • Backtracking (maze solving, puzzles) and iterative depth-first search.

Advantages of Stack Data Structure

  • push, pop and peek all run in O(1) time.
  • Very simple to implement on top of an array or a linked list.
  • The LIFO order matches many problems directly: reversing data, matching brackets, undoing actions, returning from method calls.
  • Little overhead: an array-based stack needs only the array and one index.

Disadvantages of Stack Data Structure

  • Only the top element can be accessed; reaching an element further down means popping everything above it.
  • No random access and no efficient search (searching is O(n)).
  • A fixed-size (array) stack can overflow, and popping an empty stack causes underflow; both must be checked.
  • Deep recursion relies on the call stack, which has a limited size and can throw StackOverflowError.