Array vs ArrayList Implementation of Stack in Java

Photo by La-Rel Easter on Unsplash

In Java, a stack is a linear data structure that allows elements to be added and removed from only one end, called the top of the stack. The stack follows the last-in, first-out (LIFO) principle, meaning that the element that is added last to the stack is the first one to be removed.

Here are some common operations that can be performed on a stack:

• push(element): adds an element to the top of the stack
• pop(): removes and returns the element at the top of the stack
• peek(): returns the element at the top of the stack without removing it
• isEmpty(): returns true if the stack is empty, false otherwise
• size(): returns the number of elements in the stack

A stack can be implemented using an array, a linked list, or other data structures. In Java, the java.util.Stack class is a pre-implemented stack data structure. It extends the Vector class and provides additional methods for stack operations.

LET US FIRST UNDERSTAND THE ARRAY IMPLEMENTATION

An array can be used to implement a stack in Java. Here’s a simple example of how this could work:

1. Declare a private array variable to hold the stack elements and a private integer variable to store the top index of the stack:

private int[] stack;
private int top;

2. Initialize the stack by setting the top index to -1 and allocating memory for the stack array:

stack = new int[MAX_SIZE];
top = -1;

3. Implement the push operation by adding an element to the top of the stack and incrementing the top index:

public void push(int element) {
  if (top == MAX_SIZE - 1) {
    // Stack is full, do something
  } else {
    top++;
    stack[top] = element;
  }
}

4. Implement the pop operation by removing the element at the top of the stack and decrementing the top index:

public int pop() {
  if (top == -1) {
    // Stack is empty, do something
  } else {
    int element = stack[top];
    top--;
    return element;
  }
}

5. You can also implement other stack operations, such as peek (which returns the element at the top of the stack without removing it), isEmpty, and size.

Problems with Array Implementation:

No Dynamic Resizing: The stack size is fixed, so if you try to push an element onto a full stack, you will need to handle this case. One solution is to resize the stack array when it becomes full, but this can be inefficient because it requires creating a new array and copying all the elements from the old array to the new one.

If you pop all the elements from the stack, the top index will be -1, but the array will still be allocated in memory. To free up this memory, you would need to set the stack array to null and allocate a new array when you push an element onto the empty stack.

The push and pop operations have a time complexity of O(1) in this implementation, which is efficient. However, other stack operations such as peek, isEmpty, and size have a time complexity of O(n) because they involve looping through the elements of the stack array.

NOW LET US LOOK AT ARRAYLIST IMPLEMENTATION OF STACK

An ArrayList can be used to implement a stack in Java. Here’s a simple example of how this could work:

1. Declare a private ArrayList variable to hold the stack elements and a private integer variable to store the top index of the stack:

private ArrayList<Integer> stack;
private int top;

2. Initialize the stack by setting the top index to -1 and allocating memory for the stack ArrayList:

stack = new ArrayList<>();
top = -1;

3. Implement the push operation by adding an element to the top of the stack and incrementing the top index:

public void push(int element) {
  top++;
  stack.add(element);
}

4. Implement the pop operation by removing the element at the top of the stack and decrementing the top index:

public int pop() {
  if (top == -1) {
    // Stack is empty, do something
  } else {
    int element = stack.get(top);
    stack.remove(top);
    top--;
    return element;
  }
}

5. You can also implement other stack operations, such as peek (which returns the element at the top of the stack without removing it), isEmpty, and size.

Using an ArrayList to implement a stack has the advantage of having a dynamic size, so you don’t have to worry about resizing the stack array when it becomes full. However, the push and pop operations have a time complexity of O(1) at the beginning of the ArrayList, but O(n) at the end. This is because adding or removing an element at the end of an ArrayList is efficient, but doing so at the beginning or middle requires shifting the remaining elements to make room for the new element or close the gap left by the removed element.