Question

Develop and test two Java classes:

1. an array-based stack ADT that implements the provided StackInterface.java
2. a linked list-based queue ADT that implements the provided QueueInterface.java

• You may not make any changes to StackInterface.java or QueueInterface.java
• The classes must be generic
• The attached generic singly linked list node class, LLNode.java, must be used for the queue implementation; you may not make any modifications to this class
• Your implementations cannot throw any exceptions

Each ADT must include a toString( ) method:

• The stack's toString( ) must display items in the stack in order from top to bottom
• The queue's toString( ) must display the items in the queue in order from front to rear

You are encouraged to review the rubric below for details on how the project will be graded.

This what i need to work with below:

-------------------------------------------------------------------------------------------------------------------------------------------------------------

package interfaces;

public interface StackInterface {

   void push(E element); // add an element to the stack - always at the "top"
  
   E pop(); // remove and return the top of the stack
  
   E peek(); // return the top of the stack ... without removing
  
   boolean isEmpty();
  
   boolean isFull();
  
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

package interfaces;

public interface QueueInterface {

   void enqueue(E element); // add an element to the queue - always at the end of the queue
  
   E dequeue(); // remove and return the front of the queue
  
   boolean isEmpty();
  
   boolean isFull();
  
}
-----------------------------------------------------------------------------------------------------------------------------------------------------

package nodes;

public class LLNode {
  
   private E info;
   private LLNode next;
  
   public LLNode(E info) {
       this.info = info;
       next = null;
   }
  
   public E getInfo() {
       return info;
   }
  
   public void setInfo(E info) {
       this.info = info;
   }
  
   public LLNode getNext() {
       return next;
   }
  
   public void setNext(LLNode next) {
       this.next = next;
   }
}

Array doesnt need to be extended when stack is full and the lenght of array can be up to 6

Answer 1

Answer : An array based stack ADT

public class ArrayStack implements Stack {

        private Object[] theArray;
        private int topOfStack;
        private static final int DEFAULT_CAPACITY = 10;

        /**
         * Construct the stack.
         */
        public ArrayStack() {
            theArray = new Object[DEFAULT_CAPACITY];
            topOfStack = -1;
        }

        /**
         * Test if the stack is logically empty.
         *
         * @return true if empty, false otherwise.
         */
        public boolean isEmpty() {
            return topOfStack == -1;
        }

        /**
         * Make the stack logically empty.
         */
        public void makeEmpty() {
            topOfStack = -1;
        }

        /**
         * Get the most recently inserted item in the stack. * Does not alter
         * the stack.
         *
         * @return the most recently inserted item in the stack.
         * @throws UnderflowException if the stack is empty.
         */
        public Object top() {
            if (isEmpty()) {
                throw new UnderflowException("ArrayStack top");
            }
            return theArray[ topOfStack];
        }

        /**
         * Remove the most recently inserted item from the stack.
         *
         * @throws UnderflowException if the stack is empty.
         */
        public void pop() {

            if (isEmpty()) {
                throw new UnderflowException("ArrayStack pop");
            }
            topOfStack--;
        }

        /**
         * Return and remove the most recently inserted item * from the stack.
         *
         * @return the most recently inserted item in the stack.
         * @throws Underflow if the stack is empty.
         */
        public Object topAndPop() {
            if (isEmpty()) {
                throw new UnderflowException("ArrayStack topAndPop");
            }
            return theArray[ topOfStack--];
        }

        /**
         * Insert a new item into the stack.
         *
         * @param x the item to insert.
         */
        public void push(Object x) {
            if (topOfStack + 1 == theArray.length) {
                doubleArray();
            }
            theArray[ ++topOfStack] = x;
        }

        /**
         * Internal method to extend theArray.
         */
        private void doubleArray() {
            Object[] newArray;

            newArray = new Object[theArray.length * 2];
            for (int i = 0; i < theArray.length; i++) {
                newArray[ i] = theArray[ i];
            }
            theArray = newArray;
        }
    }