Add stack implementations

Lord-of-Algorithms · Lord-of-Algorithms · commit c71a95e4b411 · 2024-07-25T18:40:46.000+03:00
diff --git a/src/lineards/stack/DynamicArrayStack.java b/src/lineards/stack/DynamicArrayStack.java
@@ -0,0 +1,70 @@
+package lineards.stack;
+
+import java.util.NoSuchElementException;
+
+/**
+ * A dynamic array implementation of a stack that dynamically resizes as elements are added or removed.
+ */
+public class DynamicArrayStack implements Stack {
+
+    private char[] data;
+    private int top;
+
+    /**
+     * Constructor to initialize the stack with an initial capacity.
+     */
+    public DynamicArrayStack(int capacity) {
+        if (capacity < 1) {
+            throw new IllegalArgumentException("Initial capacity must be at least 1");
+        }
+        data = new char[capacity];
+        top = -1;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return top == -1;
+    }
+
+    @Override
+    public void push(char value) {
+        if (top + 1 == data.length) {
+            resize(data.length * 2);  // Double the size of the array if it is full
+        }
+        data[++top] = value;
+    }
+
+    @Override
+    public char pop() {
+        if (isEmpty())
+            throw new NoSuchElementException("Stack is empty");
+
+        char value = data[top--];
+
+        // Reduce the size of the array if it is less than 1/4 full
+        if (top + 1 > 0 && top + 1 == data.length / 4) { //  The top + 1 > 0 ensures that there’s at least one element in the stack. The number of elements in the stack is actually top + 1.
+            resize(data.length / 2);
+        }
+
+        return value;
+    }
+
+    @Override
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Stack is empty");
+        }
+        return data[top];
+    }
+
+    /**
+     * Resizes the internal array to the specified new capacity.
+     *
+     * @param newCapacity The new capacity of the array
+     */
+    private void resize(int newCapacity) {
+        char[] newArray = new char[newCapacity];
+        System.arraycopy(data, 0, newArray, 0, top + 1);
+        data = newArray;
+    }
+}
diff --git a/src/lineards/stack/LinkedListStack.java b/src/lineards/stack/LinkedListStack.java
@@ -0,0 +1,62 @@
+package lineards.stack;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Implements the Stack interface using a singly linked list.
+ * This implementation uses a custom Node class to represent each element in the stack,
+ * allowing dynamic memory allocation as elements are added or removed.
+ */
+public class LinkedListStack implements Stack {
+
+    /**
+     * Node represents an element in the stack,
+     * containing a value and reference to the next Node.
+     */
+    private static class Node {
+        final char data;
+        Node next;
+
+        /**
+         * Constructs a new Node with the given data value.
+         */
+        Node(char data) {
+            this.data = data;
+        }
+    }
+
+    // Top element of the stack
+    private Node top;
+
+    @Override
+    public boolean isEmpty() {
+        return top == null;
+    }
+
+    @Override
+    public void push(char value) {
+        // Create a node
+        Node node = new Node(value);
+        // Make the new node the top element
+        node.next = top;
+        top = node;
+    }
+
+    @Override
+    public char pop() {
+        if (isEmpty())
+            throw new NoSuchElementException("Stack is empty");
+        char value = top.data;
+        // Remove the top element
+        top = top.next;
+        return value;
+    }
+
+    @Override
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Stack is empty");
+        }
+        return top.data;
+    }
+}
diff --git a/src/lineards/stack/Stack.java b/src/lineards/stack/Stack.java
@@ -0,0 +1,39 @@
+package lineards.stack;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Defines the interface for a stack.
+ */
+interface Stack {
+
+    /**
+     * Checks if the stack is empty.
+     *
+     * @return true if there are no elements in the stack, false otherwise.
+     */
+    boolean isEmpty();
+
+    /**
+     * Adds a character to the top of the stack.
+     *
+     * @param value The character to be pushed onto the stack.
+     */
+    void push(char value);
+
+    /**
+     * Removes and returns the character at the top of the stack.
+     *
+     * @return The character at the top of the stack.
+     * @throws NoSuchElementException if the stack is empty.
+     */
+    char pop();
+
+    /**
+     * Retrieves, but does not remove, the character at the top of the stack.
+     *
+     * @return The character currently at the top of the stack.
+     * @throws NoSuchElementException if the stack is empty.
+     */
+    char peek();
+}
diff --git a/src/lineards/stack/StackMain.java b/src/lineards/stack/StackMain.java
@@ -0,0 +1,78 @@
+package lineards.stack;
+
+/**
+ * Demonstrates the functionalities of different stack implementations.
+ */
+public class StackMain {
+
+    public static void main(String[] args) {
+        // Demo for StaticArrayStack
+        demoStaticArrayStack();
+
+        // Demo for DynamicArrayStack
+        demoDynamicArrayStack();
+
+        // Demo for LinkedListStack
+        demoLinkedListStack();
+    }
+
+    private static void demoStaticArrayStack() {
+        System.out.println("Demo: StaticArrayStack");
+        StaticArrayStack staticStack = new StaticArrayStack(3);
+        System.out.println("Push A, B, C");
+        staticStack.push('A');
+        staticStack.push('B');
+        staticStack.push('C');
+
+        try {
+            System.out.println("Pushing D...");
+            staticStack.push('D'); // This should fail because the stack is full
+        } catch (IllegalStateException e) {
+            System.out.println("Caught exception: " + e.getMessage());
+        }
+
+        System.out.println("Pop from stack: " + staticStack.pop()); // Should be C
+        System.out.println("Peek from stack: " + staticStack.peek()); // Should be B
+        System.out.println("Is empty: " + staticStack.isEmpty()); // Should be false
+        staticStack.pop();
+        staticStack.pop();
+        System.out.println("Is empty after popping all elements: " + staticStack.isEmpty()); // Should be true
+        System.out.println();
+    }
+
+    private static void demoDynamicArrayStack() {
+        System.out.println("Demo: DynamicArrayStack");
+        DynamicArrayStack dynamicStack = new DynamicArrayStack(2);
+        System.out.println("Push W, X, Y, Z");
+        dynamicStack.push('W');
+        dynamicStack.push('X');
+        dynamicStack.push('Y'); // Should resize and allow pushing another element
+        dynamicStack.push('Z');
+
+        System.out.println("Pop from stack: " + dynamicStack.pop()); // Should be Z
+        System.out.println("Peek from stack: " + dynamicStack.peek()); // Should be Y
+        System.out.println("Is empty: " + dynamicStack.isEmpty()); // Should be false
+        dynamicStack.pop();
+        dynamicStack.pop();
+        dynamicStack.pop();
+        System.out.println("Is empty after popping all elements: " + dynamicStack.isEmpty()); // Should be true
+        System.out.println();
+    }
+
+    private static void demoLinkedListStack() {
+        System.out.println("Demo: LinkedListStack");
+        LinkedListStack linkedListStack = new LinkedListStack();
+        System.out.println("Push 1, 2, 3");
+        linkedListStack.push('1');
+        linkedListStack.push('2');
+        linkedListStack.push('3');
+
+        System.out.println("Pop from stack: " + linkedListStack.pop()); // Should be 3
+        System.out.println("Peek from stack: " + linkedListStack.peek()); // Should be 2
+        System.out.println("Is empty: " + linkedListStack.isEmpty()); // Should be false
+        linkedListStack.pop();
+        linkedListStack.pop();
+        System.out.println("Is empty after popping all elements: " + linkedListStack.isEmpty()); // Should be true
+        System.out.println();
+    }
+}
diff --git a/src/lineards/stack/StaticArrayStack.java b/src/lineards/stack/StaticArrayStack.java
@@ -0,0 +1,69 @@
+package lineards.stack;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Implementation of the {@link Stack} interface using a static-sized array.
+ */
+public class StaticArrayStack implements Stack {
+
+    // Array to store the elements
+    private final char[] data;
+    // Index of the top element
+    private int top;
+
+    /**
+     * Constructor to initialize the stack with a given size.
+     */
+    public StaticArrayStack(int size) {
+        if (size < 1) {
+            throw new IllegalArgumentException("Size must be at least 1");
+        }
+        data = new char[size];
+        top = -1;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return top == -1;
+    }
+
+    /**
+     * Adds a character to the top of the stack.
+     *
+     * @param value The character to be pushed onto the stack.
+     * @throws IllegalStateException if the stack is full.
+     */
+    @Override
+    public void push(char value) {
+        if (isFull()) {
+            throw new IllegalStateException("Stack is full");
+        }
+        // Increment top and add element
+        data[++top] = value;
+    }
+
+    @Override
+    public char pop() {
+        if (isEmpty())
+            throw new NoSuchElementException("Stack is empty");
+        // Decrement top which causes the
+        // element to be removed
+        return data[top--];
+    }
+
+    @Override
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Stack is empty");
+        }
+        return data[top];
+    }
+
+    /**
+     * Checks if the stack is full.
+     */
+    private boolean isFull() {
+        return top == data.length - 1;
+    }
+}
