Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Key Operations of a Stack

Explore the fundamental operations of stack data structures in Java, including how to implement and use isEmpty, isFull, push, pop, peek, and size methods. Understand their time and space complexities to effectively manage data with LIFO behavior in both array-based and linked list stacks.

We'll cover the following...

With stack implementations using arrays and linked lists established, the next step is to examine the fundamental operations for interacting with a stack. These operations define the stack’s behavior and how its data is manipulated.

A stack supports several core operations, but they all revolve around the LIFO (Last in, first out) principle. Before we can add or remove elements, we often need to check the current state of the stack. Let's begin with two essential utility operations.

The isEmpty() operation

The isEmpty() method checks whether the stack is empty. This is crucial before attempting to remove or view elements, as popping an empty stack would result in an error.

Example: Consider a stack that currently holds [88, 95, 72, 80, 91]. The top index points to position 4 (where 91 is stored). Calling isEmpty() on this stack would return false because top is 4, not -1.

If we were to pop all five elements one by one, top would eventually become -1 again. At that point, calling isEmpty() would return true.

Java implementation

In an array-based stack, we check if top equals -1. Remember that we initialized top to -1 when creating an empty stack, so if it's still -1, no elements have been added.

Java 25
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        System.out.println("Is stack empty? " + stack.isEmpty());  // Output: true (stack is empty)
    }
}
class Stack {
    private int capacity;
    private int[] data;
    private int top;
    public Stack(int capacity) {
        this.capacity = capacity;     // Maximum number of elements
        this.data = new int[capacity]; // Array to store elements
        this.top = -1;                // Index of top element (-1 means empty)
    }
    public Stack() {
        this(10);   // Default capacity of 10
    }
    public boolean isEmpty() {
        // Check if the stack is empty
        return top == -1;
    }
}

The isFull() operation

The isFull() operation checks whether the stack has reached its maximum capacity. This is only relevant for array-based stacks with a fixed size. Before pushing a new element, we should check if there’s space available.

Example: Consider a stack with capacity 5 that currently holds [88, 95, 72, 80, 91]. The top is 4, and the capacity is 5. As top equals capacity - 1, i.e., (5 - 1 = 4), the stack is full. Calling isFull() would return true.

If we pop one element (91), top would become 3. Now top (3) is less than capacity - 1 (4), so calling isFull() would return false.

Java implementation

In an array-based stack, we check if top equals capacity - 1. As array indices start at 0, the last valid index is capacity - 1. If top has reached this position, the stack is full.

Java 25
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        // Simulate a full stack with elements: [88, 95, 72, 80, 91]
        stack.top = 4;  // top index is 4
        System.out.println("Is stack full? " + stack.isFull());  // Output: true (stack is full)
        System.out.println("Simulating popping one element from the stack");
        stack.top = 3;  // top index is now 3
        System.out.println("Is stack full? " + stack.isFull());  // Output: false (stack has space)
    }
}
class Stack {
    int capacity;
    int[] data;
    int top;
    public Stack(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.top = -1;
    }
    public Stack() {
        this(10);
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        // Check if the stack is full
        return top == capacity - 1;
    }
}

Note: For linked list-based stacks, isFull() is typically not needed because they can grow dynamically until the system runs out of memory.

Push operation

The push operation adds a new element to the top of the stack. This is how we insert data into the stack, and it always happens at one end, i.e., the top.

Before pushing an element into an array-based stack, we must first check if the stack is full using isFull(). If there's space available, we increment the top index and place the new element at that position.

Example: Let’s say we have a stack with capacity 10 that currently holds [88, 95, 72, 80], and we want to push the value 91 onto the stack. After the push, the stack contains [88, 95, 72, 80, 91] with top at index 4.

Java implementation

Here’s how we implement the Push operation step by step:

  1. We will check if the stack is full by calling the isFull() function. If it is full, we print an error message and return false as no further elements can be added to the stack.

  2. If the stack has capacity, increment top as we will place our new element at the top.

  3. Place the new element at the top.

Java 25
class Stack {
    private int capacity;
    private int[] data;
    private int top;
    public Stack(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.top = -1;
    }
    public Stack() {
        this(10);
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        return top == capacity - 1;
    }
    
    public int getTop() {
        return top;
    }
    public boolean push(int value) {
        // Check if stack is full
        if (isFull()) {
            System.out.println("Stack Overflow! Cannot push element.");
            return false;
        }
        // Increment top and add the element
        top++;
        data[top] = value;
        return true;
    }
}
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        // Push elements one by one
        stack.push(88);   // Stack: [88], top = 0
        stack.push(95);   // Stack: [88, 95], top = 1
        stack.push(72);   // Stack: [88, 95, 72], top = 2
        stack.push(80);   // Stack: [88, 95, 72, 80], top = 3
        stack.push(91);   // Stack: [88, 95, 72, 80, 91], top = 4
        System.out.println("Top index: " + stack.getTop());  // Output: Top index: 4
    }
}

Pop operation

The pop operation removes and returns the element at the top of the stack. This is how we retrieve data from the stack while also removing it from the structure.

Before popping, we must check if the stack is empty using isEmpty(). If the stack has elements, we retrieve the element at the top index, then decrement top to reflect that the stack now has one fewer element.

Example: Consider a stack that currently contains [88, 95, 72, 80, 91], and we want to pop an element. After the pop, the stack contains [88, 95, 72, 80] with top at index 3. The value 91 is returned to the caller.

Java implementation

Here’s how we implement the Pop operation step by step:

  1. We will check if the stack is empty by calling the isEmpty() method. If it is empty, we print an error message and throw an EmptyStackException as no elements can be removed from the stack.

  2. If the stack is not empty, we retrieve the value stored at its top index and store it in the variable value.

  3. After retrieving the top element, we decrement the top index to indicate that the top element has been removed.

  4. In the end, we return the value of the removed top element.

Java 25
class Stack {
    private int capacity;
    private int[] data;
    int top;
    public Stack(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
        this.top = -1;
    }
    public Stack() {
        this(10);
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        return top == capacity - 1;
    }
    public boolean push(int value) {
        if (isFull()) {
            System.out.println("Stack Overflow! Cannot push element.");
            return false;
        }
        top++;
        data[top] = value;
        return true;
    }
    public int pop() {
        // Check if stack is empty
        if (isEmpty()) {
            System.out.println("Stack Underflow! Cannot pop from empty stack.");
            return -1;
        }
        // Get the top element
        int value = data[top];
        // Decrement top
        top--;
        return value;
    }
}
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        stack.push(88);
        stack.push(95);
        stack.push(72);
        stack.push(80);
        stack.push(91);
        
        System.out.println("Popping elements from the stack");  // Output: 1
        // Pop elements
        System.out.println(stack.pop());  // Output: 91, Stack now: [88, 95, 72, 80]
        System.out.println(stack.pop());  // Output: 80, Stack now: [88, 95, 72]
        System.out.println(stack.pop());  // Output: 72, Stack now: [88, 95]
        System.out.println("Top index after popping 3 elements: " + stack.top);  // Output: 1
    }
}

Peek operation

The peek operation returns the element at the top of the stack without removing it. This allows us to see what's on top without modifying the stack's contents. Like pop, we must first check if the stack is empty. If it has elements, we simply return the value at the top ...