00:00

Stack Implementation using Array

Last updated:

An array is the simplest storage for a stack. The elements sit in the array from the bottom of the stack (index 0) upwards, and one integer, top, remembers where the top element is. Every stack operation then becomes a single array access plus a change to top.

A stack can be built on an array or on a linked list. This page shows the array version; the linked-list version has its own tutorial.

Stack implementation using Array in Java

The class below stores up to 100 int values:

  • top starts at -1, meaning the stack is empty.

  • push() checks for overflow, increments top and stores the value at array[top].

  • pop() checks for underflow, reads array[top] and decrements top.

  • peek() reads array[top] without changing top.

The class is called IntStack so that it is not confused with java.util.Stack.

StackUsingArray.java
// A fixed-capacity stack of int values backed by an array
class IntStack {
  private final int capacity = 100; // maximum number of items
  private final int[] array;        // storage for the items
  private int top;                  // index of the top item, -1 when empty

  IntStack() {
    array = new int[capacity];
    top = -1;
  }

  // true when the stack holds no items
  boolean isEmpty() {
    return top == -1;
  }

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

  // Adds an item on top of the stack
  void push(int item) {
    if (isFull()) {
      System.out.println("Stack is full, cannot push " + item + ".");
      return;
    }
    array[++top] = item;           // move top up, then store the item
    System.out.println(item + " pushed into the stack.");
  }

  // Removes the top item
  void pop() {
    if (isEmpty()) {
      System.out.println("Stack is empty, cannot pop.");
      return;
    }
    int item = array[top--];       // read the item, then move top down
    System.out.println(item + " popped from the stack.");
  }

  // Shows the top item without removing it
  void peek() {
    if (isEmpty()) {
      System.out.println("Stack is empty, nothing to peek.");
      return;
    }
    System.out.println("Stack top item: " + array[top]);
  }

  // Prints the items from top to bottom
  void printStack() {
    System.out.print("Stack Items:");
    for (int i = top; i >= 0; i--) {
      System.out.print(" " + array[i]);
    }
    System.out.println();
  }
}

public class StackUsingArray {
  public static void main(String[] args) {
    IntStack stack = new IntStack();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);
    stack.pop();
    stack.peek();
    stack.printStack();
  }
}
Output
10 pushed into the stack.
20 pushed into the stack.
30 pushed into the stack.
40 pushed into the stack.
40 popped from the stack.
Stack top item: 30
Stack Items: 30 20 10

Time complexity: O(1) for push, pop, peek, isEmpty and isFull.

Space complexity: O(n), where n is the capacity of the array; the whole array is allocated up front, even when the stack holds few items.