Question

Use Java:

Also: Please include screenshots if possible.

1. Create a class called AbstractStackTest.
   1. Write an abstract method called makeStack that returns a Stack of Strings. Use the Stack interface as the return type, not a specific implementation!
2. Write a class named NodeStackTest that extends your AbstractStackTest class. Implement the makeStack method to return a NodeStack.

3. Repeat parts 1 and 2 for the Queue interface and the NodeQueue implementation.
4. Write a new stack implementation, ArrayStack. It should be generic and use an array to store the values in the stack.
5. 1. Note that, in Java, you cannot create an array of a generic type, i.e. T[] array = new T[10]; will cause a compiler error. Instead, use an Object array to store the elements in your stack. This means that you will have to cast the value that you return in your peek and dequeue methods, e.g. return (T)array[0];
6. 2. Create your array to be some small initial size (e.g. 2). If your array fills up, you will need to make a new, larger array (remember Arrays.copyOf()).You should double the size of the array each time. Do not worry about making the array smaller! Once you make a new array, don’t forget to update your stack’s field to point to the new array!
7. Write a new class called ArrayStackTest that extends AbstractStackTest. Implement the makeStack method to return an instance of your ArrayStack class. Run your tests to make sure that they all pass on your ArrayStack implementation.
8. Repeat parts 4 and 7 but implement an ArrayQueue.

Use existing code:

public interface Stack {

    public void push(T value);

    T pop();

    T peek();

    int size();

}

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

public interface Queue {

    void enqueue (T value);

    T dequeue();

    T peek();

    int size();
}

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

public class NodeStack implements Stack {

    private Node top;
    private int size;

    public NodeStack() {
        top = null;
        size = 0;
    }

    @Override
    public void push(T value) {
        Node node = new Node<>(value);
        node.setNext(top);
        this.top = node;
        this.size++;
    }

    @Override
    public T pop() {
        T value = top.getValue();
        this.top = top.getNext();
        size--;
        return value;
    }

    @Override
    public T peek() {
        return top.getValue();
    }

    @Override
    public int size() {
        return this.size;
    }
}

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

public class NodeQueue implements Queue {

    private Node front;
    private Node back;
    private int size;


    public NodeQueue() {
        this.front = null;
        this.back = null;
        this.size = 0;
    }

    @Override
    public void enqueue(T value) {
        Node node = new Node<>(value);

        if(front ==null){
            front = node;
            back=node;
        } else {
            back.setNext(node);
            back = node;
        }

        size++;
    }

    @Override
    public T peek() {
        return front.getValue();
    }


    @Override
    public T dequeue() {
        T value = front.getValue();
        front = front.getNext();

        if(front ==null){
            back = null;
        }
        size--;
        return value;
    }

    @Override
    public int size() {
        return size;
    }
}

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

public class Node<T> {

    private T value;
    private Node<T> next;

    public Node(T value) {
        this.value = value;
        this.next=null;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

Answer 1

Hello! :)

Here are the complete codes to solve the assignment:

AbstractQueueTest.java:

public abstract class AbstractQueueTest
{
    public abstract Queue<String> makeQueue();
}

AbstractStackTest.java:

public abstract class AbstractStackTest
{
    public abstract Stack<String> makeStack();
}

ArrayQueue.java:

import java.util.Arrays;

public class ArrayQueue<T> implements Queue<T>
{
    private Object data[];
    private int front;
    private int back;
    private int size;

    public ArrayQueue()
    {
        data = new Object[2];
        front = 0;
        back = 0;
        size = 0;
    }

    @Override
    public void enqueue(T value)
    {
        if(front == data.length)
        {
            final int previousLength = data.length;
            final int nextLength = previousLength * 2;
            data = Arrays.copyOf(data, nextLength);
        }
        ++size;
        data[front++] = value;
    }

    @Override
    public T peek()
    {
        return (T)data[back];
    }


    @Override
    public T dequeue()
    {
        --size;
        return (T)data[back++];
    }

    @Override
    public int size()
    {
        return this.size;
    }
}

ArrayQueueTest.java:

public class ArrayQueueTest extends AbstractQueueTest
{
    @Override
    public Queue<String> makeQueue()
    {
        return new ArrayQueue<>();
    }
}

ArrayStack.java:

import java.util.Arrays;

public class ArrayStack<T> implements Stack<T>
{
    private Object data[];
    private int size;

    public ArrayStack()
    {
        data = new Object[2];
        size = 0;
    }

    @Override
    public void push(T value)
    {
        if(size == data.length)
        {
            final int previousLength = data.length;
            final int nextLength = previousLength * 2;
            data = Arrays.copyOf(data, nextLength);
        }
        
        data[size++] = value;
    }

    @Override
    public T pop()
    {
        return (T)data[--size];
    }

    @Override
    public T peek()
    {
        return (T)data[size - 1];
    }

    @Override
    public int size()
    {
        return this.size;
    }
}

ArrayStackTest.java:

public class ArrayStackTest extends AbstractStackTest
{
    @Override
    public Stack<String> makeStack()
    {
        return new ArrayStack<>();
    }
}

Node.java:

public class Node<T> {

    private T value;
    private Node<T> next;

    public Node(T value) {
        this.value = value;
        this.next=null;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

NodeQueue.java:

public class NodeQueue<T> implements Queue<T> {

    private Node front;
    private Node back;
    private int size;


    public NodeQueue() {
        this.front = null;
        this.back = null;
        this.size = 0;
    }

    @Override
    public void enqueue(T value) {
        Node node = new Node<>(value);

        if(front ==null){
            front = node;
            back=node;
        } else {
            back.setNext(node);
            back = node;
        }

        size++;
    }

    @Override
    public T peek() {
        return (T)front.getValue();
    }


    @Override
    public T dequeue() {
        T value = (T)front.getValue();
        front = front.getNext();

        if(front ==null){
            back = null;
        }
        size--;
        return value;
    }

    @Override
    public int size() {
        return size;
    }
}

NodeQueueTest.java:

public class NodeQueueTest extends AbstractQueueTest
{
    public Queue<String> makeQueue()
    {
        return new NodeQueue<>();
    }
}

NodeStack.java:

public class NodeStack<T> implements Stack<T> {

    private Node top;
    private int size;

    public NodeStack() {
        top = null;
        size = 0;
    }

    @Override
    public void push(T value) {
        Node node = new Node<>(value);
        node.setNext(top);
        this.top = node;
        this.size++;
    }

    @Override
    public T pop() {
        T value = (T)top.getValue();
        this.top = top.getNext();
        size--;
        return value;
    }

    @Override
    public T peek() {
        return (T)top.getValue();
    }

    @Override
    public int size() {
        return this.size;
    }
}

NodeStackTest.java:

public class NodeStackTest extends AbstractStackTest
{
    @Override
    public Stack<String> makeStack()
    {
        return new NodeStack<>();
    }
}

Queue.java:

public interface Queue<T> {

    void enqueue (T value);

    T dequeue();

    T peek();

    int size();
}

Stack.java:

public interface Stack<T> {

    public void push(T value);

    T pop();

    T peek();

    int size();
}

Test.java:

public class Test
{
    private static int status;

    public static void test(boolean condition)
    {
        final int line = Thread.currentThread().getStackTrace()[2].getLineNumber();

        if(condition)
        {
            System.out.print("TEST PASSED");
        }
        else
        {
            System.out.print("TEST FAILED");
            status = 1;
        }

        System.out.println(" at line: " + line);
    }

    public static void main(String[] args)
    {
        status = 0;

        // Testing ArrayStack

        Stack arrayStack = new ArrayStackTest().makeStack();

        test(arrayStack.size() == 0);

        arrayStack.push("A");
        arrayStack.push("B");
        arrayStack.push("C");
        arrayStack.push("D");

        test(arrayStack.size() == 4);

        test(arrayStack.peek() == "D");
        test(arrayStack.pop() == "D");
        test(arrayStack.peek() == "C");
        test(arrayStack.pop() == "C");

        // Testing NodeStack

        Stack nodeStack = new NodeStackTest().makeStack();

        test(nodeStack.size() == 0);

        nodeStack.push("A");
        nodeStack.push("B");
        nodeStack.push("C");
        nodeStack.push("D");

        test(nodeStack.size() == 4);

        test(nodeStack.peek() == "D");
        test(nodeStack.pop() == "D");
        test(nodeStack.peek() == "C");
        test(nodeStack.pop() == "C");

        // Testing ArrayQueue

        Queue arrayQueue = new ArrayQueueTest().makeQueue();

        test(arrayQueue.size() == 0);

        arrayQueue.enqueue("A");
        arrayQueue.enqueue("B");
        arrayQueue.enqueue("C");
        arrayQueue.enqueue("D");

        test(arrayQueue.size() == 4);

        test(arrayQueue.peek() == "A");
        test(arrayQueue.dequeue() == "A");
        test(arrayQueue.peek() == "B");
        test(arrayQueue.dequeue() == "B");

        // Testing NodeQueue

        Queue nodeQueue = new NodeQueueTest().makeQueue();

        test(nodeQueue.size() == 0);

        nodeQueue.enqueue("A");
        nodeQueue.enqueue("B");
        nodeQueue.enqueue("C");
        nodeQueue.enqueue("D");

        test(nodeQueue.size() == 4);

        test(nodeQueue.peek() == "A");
        test(nodeQueue.dequeue() == "A");
        test(nodeQueue.peek() == "B");
        test(nodeQueue.dequeue() == "B");

        System.exit(status);
    }
}

Here is a screenshot of a demo run:

Hope this helps! :)