Implement a Stack Using Arrays in Java ~ Coding Workspace

A stack is a fundamental data structure that follows the Last In First Out (LIFO) principle. In a stack, the last element added is the first to be removed. Stacks are widely used in various algorithms, such as balancing expressions, undo/redo operations in text editors, and function calls in recursion.

In this article, we'll explore how to implement a stack using Java arrays. We’ll also examine multiple implementation options and analyze each approach's time and space complexity.

Basic Stack Operations

A stack supports the following core operations:

push(element): Adds an element to the top of the stack.
pop(): Removes the top element of the stack and returns it.
peek(): Returns the top element of the stack without removing it.
isEmpty(): Checks if the stack is empty.
size(): Returns the number of elements in the stack.

Approach 1: Stack Using a Fixed-Size Array

The most basic implementation of a stack uses a fixed-size array. Here, we define an array with a predefined capacity and manage the stack elements manually using an index.

Code Example:

public class Stack {
    private int[] stackArray;
    private int top;
    private int capacity;

    // Constructor to initialize the stack
    public Stack(int size) {
        capacity = size;
        stackArray = new int[capacity];
        top = -1;
    }

    // Push operation
    public void push(int element) {
        if (top == capacity - 1) {
            System.out.println("Stack Overflow! Cannot push " + element);
        } else {
            stackArray[++top] = element;
            System.out.println("Pushed " + element + " to stack");
        }
    }

    // Pop operation
    public int pop() {
        if (top == -1) {
            System.out.println("Stack Underflow! Cannot pop");
            return -1;
        } else {
            return stackArray[top--];
        }
    }

    // Peek operation
    public int peek() {
        if (top == -1) {
            System.out.println("Stack is empty.");
            return -1;
        } else {
            return stackArray[top];
        }
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return top == -1;
    }

    // Get the size of the stack
    public int size() {
        return top + 1;
    }
    
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack size: " + stack.size());
    }
}

Time Complexity:

push(element): O(1) — Inserting an element at the top is constant time.
pop(): O(1) — Removing the top element is constant time.
peek(): O(1) — Accessing the top element is constant time.
isEmpty(): O(1) — Checking if the stack is empty is constant time.
size(): O(1) — Accessing the size of the stack is constant time.

Space Complexity:

O(n) — The stack requires a fixed-size array to store elements, where n is the capacity of the stack.

Approach 2: Stack Using a Dynamic Array (ArrayList)

A dynamic array implementation allows for a flexible stack where the size can grow or shrink based on the number of elements. In this approach, we use an ArrayList to implement the stack, so we don’t need to worry about the size limit.

Code Example:

import java.util.ArrayList;

public class DynamicStack {
    private ArrayList<Integer> stackList;

    // Constructor to initialize the stack
    public DynamicStack() {
        stackList = new ArrayList<>();
    }

    // Push operation
    public void push(int element) {
        stackList.add(element);
        System.out.println("Pushed " + element + " to stack");
    }

    // Pop operation
    public int pop() {
        if (stackList.isEmpty()) {
            System.out.println("Stack Underflow! Cannot pop");
            return -1;
        } else {
            return stackList.remove(stackList.size() - 1);
        }
    }

    // Peek operation
    public int peek() {
        if (stackList.isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        } else {
            return stackList.get(stackList.size() - 1);
        }
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return stackList.isEmpty();
    }

    // Get the size of the stack
    public int size() {
        return stackList.size();
    }
    
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack size: " + stack.size());
    }
}

Time Complexity:

push(element): O(1) — Adding an element at the end of the ArrayList is constant time.
pop(): O(1) — Removing the last element of the ArrayList is constant time.
peek(): O(1) — Accessing the last element of the ArrayList is constant time.
isEmpty(): O(1) — Checking if the stack is empty is constant time.
size(): O(1) — Accessing the size of the stack is constant time.

Space Complexity:

O(n) — The stack’s space complexity is determined by the number of elements stored in the ArrayList.

Approach 3: Stack Using Linked List

A linked list implementation of a stack allows for dynamic resizing of the stack without needing a fixed-size array. Each element in the stack is represented as a node in the linked list, and the top of the stack is the head of the list.

Code Example:

public class LinkedListStack {
    private Node top;

    // Node class to represent each element
    private class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    // Push operation
    public void push(int element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
        System.out.println("Pushed " + element + " to stack");
    }

    // Pop operation
    public int pop() {
        if (top == null) {
            System.out.println("Stack Underflow! Cannot pop");
            return -1;
        } else {
            int poppedData = top.data;
            top = top.next;
            return poppedData;
        }
    }

    // Peek operation
    public int peek() {
        if (top == null) {
            System.out.println("Stack is empty.");
            return -1;
        } else {
            return top.data;
        }
    }

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

    // Get the size of the stack
    public int size() {
        int size = 0;
        Node current = top;
        while (current != null) {
            size++;
            current = current.next;
        }
        return size;
    }
    
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack size: " + stack.size());
    }
}

Time Complexity:

push(element): O(1) — Inserting a new node at the top of the stack is constant time.
pop(): O(1) — Removing the top element from the stack is constant time.
peek(): O(1) — Accessing the top element is constant time.
isEmpty(): O(1) — Checking if the stack is empty is constant time.
size(): O(n) — Traversing the linked list to calculate the size takes linear time.

Space Complexity:

O(n) — The stack’s space complexity is determined by the number of elements in the linked list.

Conclusion

In this article, we explored three different approaches to implementing a Java stack: a fixed-size array, a dynamic array (ArrayList), and a linked list. Each approach offers its own advantages and trade-offs in terms of flexibility, complexity, and performance:

Fixed-size Array: Efficient in terms of time complexity but limited by size.
Dynamic Array: More flexible than a fixed-size array but may incur some overhead when resizing.
Linked List: Offers dynamic memory usage with O(1) push and pop operations, but calculating the size takes O(n) time.

By understanding these implementations, you can choose the most appropriate one based on your use case.

Thank you for reading my latest article! I would greatly appreciate your feedback to improve my future posts. 💬 Was the information clear and valuable? Are there any areas you think could be improved? Please share your thoughts in the comments or reach out directly. Your insights are highly valued. 👇😊. Happy coding! 💻✨

Coding Workspace

All programing code in one workspace