Introduction

As discussed in the last episode on stack data structure, we learnt about the various ways a stack could be implemented, as:

• Linked Lists
• Arrays

and I implemented a stack with singly linked list, here is the link to the previous article that discussed implementing a stack as linked list https://chigbogu.hashnode.dev/implementing-stack-data-structure

Fixed Size Array Stack

In this episode, I dissected implementing a stack with Arrays of a fixed size. The full source code is on GitHub https://github.com/chiorji/course-work/blob/635f528969635dc9acfcca705b6b9b0a34750410/src/arraystack/FixedSizeArrayStack.java

Recap

Here's a recap on the basic operations on a stack

• push - inserts new element to the top of the stack
• pop - removes element from the top of the stack and returns data from the removed node
• peek - retrieves the top element on the stack without removing it
• traversing - loop through the stack and return all the data

@SuppressWarnings("unchecked")
public class FixedSizeArrayStack<T> {
    private final T[] stack;
    private int top = -1;
    private int MAX_CAPACITY = 0;

    // constructor with default capacity
    public FixedSizeArrayStack() {
        MAX_CAPACITY = 5;
        stack = (T[]) new Object[5];
    }
    // constructor with program defined capacity
    public FixedSizeArrayStack(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("Illegal capacity: " + capacity);
        this.MAX_CAPACITY = capacity;
        stack = (T[]) new Object[capacity];
    }
}

PUSH

1. START
2. Check if the stack is full
   1. If TRUE, produce error and exit
3. Point the top to the next empty slot in the array
4. Add element to the next empty slot
5. END

 public void push(T value) {
        if (isFull()) throw new StackOverflowError("Stack overflow");
        top = top + 1;
        stack[top] = value;
    }

POP

1. START
2. Check if the stack is empty
3. If TRUE, produce error and exit
4. Grab the value at the top position
5. Decrement top by 1
6. Return the value grabbed at step 4 above
7. END

 public T pop() {
        if (isEmpty()) throw new EmptyStackException();
        T value = stack[top];
        top = top - 1;
        return value;
    }

Peek

1. START
2. Check if the stack is empty
3. If the stack is empty, produce an error and exit
4. Return the top-most element in the stack
5. END

  public T peek() {
        if (isEmpty()) throw new EmptyStackException();
        return stack[top];
    }

Traversing the stack

@Override
    public String toString() {
        if (isEmpty()) return "[]";
        StringBuilder sb = new StringBuilder().append("[");
        // make a temp variable to hold our top value
        int temp = top;
        while (temp > -1) {
            sb.append(stack[temp]);
            if (temp != 0) sb.append(", ");
            temp = temp - 1;
        }
        return sb.append("]").toString();
    }

Testing our implementation

public class ArrayStackTest {
    public static void main(String[] args) {
        // Initialize with a fixed size 
        FixedSizeArrayStack<Integer> stack = new FixedSizeArrayStack<>(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        System.out.println("Size: " + stack.getSize()); // 6
        System.out.println("Stack: " + stack.toString()); // [6, 5, 4, 3, 2, 1]

        // Remove the top-most element in the stack
        Integer popped = stack.pop();

        System.out.println("Popped: " + popped); // 6
        System.out.println("Size: " + stack.getSize()); // 5
        System.out.println("Stack: " + stack.toString()); // [5, 4, 3, 2, 1]

       // Create a stack of the String type with a fixed size of 3
       FixedSizeArrayStack<String> strStack = new FixedSizeArrayStack<>(3);
       strStack.push("Hello World!");
       strStack.push("Stack with a fixed size");
       strStack.push("Here comes the end!");

       System.out.println("Size: " + strStack.getSize()); // 3
       System.out.println("String Stack: " + strStack.toString()); // [Here comes the end!, Stack with a fixed size, Hello World!]
       strStack.push("Would error, no empty slot in the stack"); // ArrayIndexOutOfBoundsException
    }
}

The full source code is on GitHub https://github.com/chiorji/course-work/blob/635f528969635dc9acfcca705b6b9b0a34750410/src/arraystack/FixedSizeArrayStack.java