How to Implement a Stack Using Arrays in Java

Stacks are fundamental data structures in computer science that operate on a Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. Stacks are widely used in various applications, including parsing expressions, backtracking algorithms, and managing function calls in programming languages. In this article, we will explore how to implement a stack using arrays in Java, including definitions, use cases, and actionable insights.

What is a Stack?

A stack is a linear data structure that allows operations at one end only. The two primary operations performed on a stack are:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the element from the top of the stack.

Additionally, stacks often support other operations like peek (to view the top element without removing it) and isEmpty (to check if the stack is empty).

Use Cases of Stacks

Stacks have numerous applications in software development, including:

• Function Call Management: Stacks keep track of active functions or methods in programming languages.
• Undo Mechanisms: Applications like text editors use stacks to implement undo features.
• Expression Evaluation: Compilers use stacks to evaluate expressions and manage operator precedence.
• Backtracking Algorithms: Problems like maze solving or puzzle games often leverage stacks to backtrack to previous states.

Implementing a Stack Using Arrays

In Java, you can implement a stack using an array. This approach is straightforward but comes with certain limitations, such as a fixed size. If you need a dynamic stack, consider using ArrayList or the Stack class from the Java Collections Framework. However, for educational purposes, we'll focus on a basic array implementation.

Step-by-Step Implementation

Here is how to implement a stack using arrays in Java:

Step 1: Define the Stack Class

Create a class named ArrayStack that will encapsulate the stack's behavior.

public class ArrayStack {
    private int maxSize; // Maximum size of the stack
    private int[] stackArray; // Array to hold stack elements
    private int top; // Index of the top element

    public ArrayStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1; // Indicates an empty stack
    }
}

Step 2: Implement the Push Operation

The push method adds an element to the top of the stack, increasing the top index.

public void push(int value) {
    if (top == maxSize - 1) {
        throw new StackOverflowError("Stack is full");
    }
    stackArray[++top] = value;
}

Step 3: Implement the Pop Operation

The pop method removes and returns the top element, decreasing the top index.

public int pop() {
    if (isEmpty()) {
        throw new IllegalStateException("Stack is empty");
    }
    return stackArray[top--];
}

Step 4: Implement the Peek Operation

The peek method allows you to see the top element without removing it.

public int peek() {
    if (isEmpty()) {
        throw new IllegalStateException("Stack is empty");
    }
    return stackArray[top];
}

Step 5: Implement the isEmpty Method

This method checks if the stack is empty.

public boolean isEmpty() {
    return top == -1;
}

Step 6: Implement the Size Method

This method returns the current number of elements in the stack.

public int size() {
    return top + 1;
}

Complete Stack Implementation

Here’s the complete code for the ArrayStack class:

public class ArrayStack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public ArrayStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1;
    }

    public void push(int value) {
        if (top == maxSize - 1) {
            throw new StackOverflowError("Stack is full");
        }
        stackArray[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stackArray[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stackArray[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }
}

Example Usage

To demonstrate how to use the ArrayStack class, consider the following example:

public class Main {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);

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

        System.out.println("Top element: " + stack.peek()); // Output: 30
        System.out.println("Stack size: " + stack.size()); // Output: 3

        System.out.println("Popped element: " + stack.pop()); // Output: 30
        System.out.println("Stack size after pop: " + stack.size()); // Output: 2
    }
}

Conclusion

Implementing a stack using arrays in Java is a great way to understand the fundamentals of data structures. While this approach has its limitations, such as a fixed size, it provides a clear insight into how stacks function. Remember to consider more dynamic alternatives in real-world applications.

By mastering the stack data structure, you can enhance your programming skills and tackle complex problems effectively. Whether you're building applications, solving algorithms, or designing systems, understanding stacks will be beneficial in your coding journey.