Question

Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract...

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.
  1. Repeat parts 1 and 2 for the Queue interface and the NodeQueue implementation.
  2. Write a new stack implementation, ArrayStack. It should be generic and use an array to store the values in the stack.
    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];
    1. 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!
  5. 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.
  6. 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;
    }
}
Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

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! :)

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
(Please use Java Eclipse) QUESTION 1: For the question below, assume the following implementation of LinkedQueue:...
(Please use Java Eclipse) QUESTION 1: For the question below, assume the following implementation of LinkedQueue: public static final class LinkedQueue<T> implements QueueInterface<T> {     private Node<T> firstNode;     private Node<T> lastNode;     public LinkedQueue() {         firstNode = null;         lastNode = null;     }     @Override     public T getFront() {         if (isEmpty()) {             return null;         }         return firstNode.getData();     }     @Override     public boolean isEmpty() {         return firstNode == null;    ...
Please explain code 1 and code 2 for each lines code 1 public class MyQueue {...
Please explain code 1 and code 2 for each lines code 1 public class MyQueue {    public static final int DEFAULT_SIZE = 10;    private Object data[];    private int index; code 2 package test; import java.util.*; /* Class Node */ class Node { protected Object data; protected Node link; /* Constructor */ public Node() { link = null; data = 0; } /* Constructor */ public Node(Object d,Node n) { data = d; link = n; } /*...
1. BQUEUE.h #pragma once #include class bqnode { public: int time; bqnode *prev, *next; }; class...
1. BQUEUE.h #pragma once #include class bqnode { public: int time; bqnode *prev, *next; }; class BQUEUE { public: BQUEUE(); ~BQUEUE(); BQUEUE(const BQUEUE &); void Enqueue(int); void Dequeue(); void Print(); private: bqnode * front; //use ONLY one pointer }; 2. BQUEUE.cpp #include "BQUEUE.h" using namespace std; BQUEUE::BQUEUE() { } BQUEUE::~BQUEUE() { } BQUEUE::BQUEUE(const BQUEUE & otherList) { if (otherList.front == NULL) return; front = new bqnode(); bqnode *curr = front; bqnode *oldnode = otherList.front; curr->time = oldnode->time; curr->next = NULL;...
(JAVA) Why is my toString method not printing out the last node? It will not print...
(JAVA) Why is my toString method not printing out the last node? It will not print out "A" which is for Alice. Everything else is working just fine except for this. package driver; import exception.StackException; import stack.*; public class StackDriver { public static void main(String[] args) throws Exception { StackInterface<Painting> painting = new LinkedStack <Painting>(); try { System.out.println("Peeking at top of player stack.\n" + painting.peek()); }catch (StackException e) { System.out.println(e); System.out.println("Let's double check if it's empty: " + painting.isEmpty()); }...
In the attached FlexArray Java class, implement a method public int delete (int location) { }...
In the attached FlexArray Java class, implement a method public int delete (int location) { } that deletes the integer value stored at location in the array, returns it, and ensures that the array values are contiguous.  Make sure to handle the array empty situation.  What is the time-complexity of the method, if the array size is n. ***************************************************************************************************************************** public class FlexArray { int [] array; private int size; private int capacity; public FlexArray() { capacity=10; size=0; array=new int[10]; } public FlexArray(int...
Create a class StacktwoPopArr using Arrays, Change the pop function so that two elements get popped...
Create a class StacktwoPopArr using Arrays, Change the pop function so that two elements get popped everytime instead of the one. If there is only one element in the stack, just pop the one element and report that the stack is now empty. If stack is empty, it should just report that stack is empty. All other functions for StackArray remain the same. using java StackArray.java: public class StackArray {       private final int size = 20; //Size of...
The language is Java. Using a singly-linked list, implement the four queue methods enqueue(), dequeue(), peek(),...
The language is Java. Using a singly-linked list, implement the four queue methods enqueue(), dequeue(), peek(), and isEmpty(). For this assignment, enqueue() will be implemented in an unusual manner. That is, in the version of enqueue() we will use, if the element being processed is already in the queue then the element will not be enqueued and the equivalent element already in the queue will be placed at the end of the queue. Additionally, you must implement a circular queue....
Code in JAVA The requirements are as follows: The input will be in a text file...
Code in JAVA The requirements are as follows: The input will be in a text file whose name is given by arg[0] of main(). It will contain a fully-parenthesized infix expression containing only: "(", ")", "+", "-" and integers. Need help on the main and fixing the Queue. //Input: ( ( 1 + 2 ) - ( ( 3 - 4 ) + ( 7 - 2 ) ) ) ( ( 1 + 2 ) - ( 3 -...
TestQueue.java Design a class named Queue for storing integers. Like a stack, a queue holds elements....
TestQueue.java Design a class named Queue for storing integers. Like a stack, a queue holds elements. But in a queue, the elements are retrieved in a first-in first-out fashion. The class contains: An int[] data field named elements that stores the int values in the queue. A data field named size that stores the number of elements in the queue. A constructor that creates a Queue object with default capacity 8. The method enqueue(int v) that adds v into the...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT