Question: I need to build a queue class using java. I have three java files. The first one is Queue.java which I need to work on.
I need to build a queue class using java.
I have three java files. The first one is Queue.java which I need to work on. The second one is the UnboundedQueueInterface.java which Queue.java implements. The third file is a JUnit test file PublicUnboundedQueueInterfaceTest.java.
I will rate if the codes pass all JUnit tests in PublicUnboundedQueueInterfaceTest.java.
By the way, I am asked to NOT use any Java class that implements the Collection interface (e.g. ArrayList, Vector etc.)
Here is the Queue.java which all the work will be done:
package structures;
import java.util.NoSuchElementException;
/**************************************************************************************
* NOTE: before starting to code, check support/structures/UnboundedQueueInterface.java
* for detailed explanation of each interface method, including the parameters, return
* values, assumptions, and requirements
***************************************************************************************/
public class Queue implements UnboundedQueueInterface {
public Queue() {
// TODO 1
}
public Queue(Queue other) {
// TODO 2
}
@Override
public boolean isEmpty() {
// TODO 3
return false;
}
@Override
public int size() {
// TODO 4
return 0;
}
@Override
public void enqueue(T element) {
// TODO 5
}
@Override
public T dequeue() throws NoSuchElementException {
// TODO 6
return null;
}
@Override
public T peek() throws NoSuchElementException {
// TODO 7
return null;
}
@Override
public UnboundedQueueInterface reversed() {
// TODO 8
return null;
}
}
class Node {
public T data;
public Node next;
public Node(T data) { this.data=data;}
public Node(T data, Node next) {
this.data = data; this.next=next;
}
}
Here is the UnboundedQueueInterface.java:
package structures;
import java.util.NoSuchElementException;
/**
* An unbounded queue.
*
* When implementing this interface, be sure to implement
* both a regular no-argument constructor, and a copy constructor.
*
* The copy constructor should have a signature something like:
*
* public Queue(Queue other) {
* ...
* }
*
* and is fairly straightforward if you utilize the other methods you
* need to implement (like size(), enqueue(), and dequeue()).
*
*/
public interface UnboundedQueueInterface {
/**
* Returns true if the queue contains no
* elements. Must be O(1).
*/
public boolean isEmpty();
/**
* Returns the number of element in the queue. Must be O(1).
*
* @return the number of elements stored in the queue
*/
public int size();
/**
* Enqueue an element at the rear of the queue. Most be O(1).
* @param element
*/
public void enqueue(T element);
/**
* Dequeue (i.e. remove and return) the front element of the queue.
* Must be O(1).
* @return the front element in the queue
* @throws NoSuchElementException if the queue is empty
*/
public T dequeue() throws NoSuchElementException;
/**
* Return (but do not remove) the front element of the queue.
* Must be O(1).
* @return the front element in the queue
* @throws NoSuchElementException if the queue is empty
*/
public T peek() throws NoSuchElementException;
/**
* Returns a new queue with the elements in reverse order.
* Must be O(n).
*
* @return a reversed copy of the queue
*/
public UnboundedQueueInterface reversed();
}
Here is the PublicUnboundedQueueInterfaceTest.java:
package structures;
import static org.junit.Assert.*;
import org.junit.Test;
public class PublicUnboundedQueueInterfaceTest {
UnboundedQueueInterface q;
@Test
public void testCopyConstructorEmpty() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
r = new Queue(q);
assertTrue(r.isEmpty());
assertTrue(q.isEmpty());
}
@Test
public void testCopyConstructorEmptyNotAliased() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
r = new Queue(q);
assertTrue(r.isEmpty());
assertTrue(q.isEmpty());
q.enqueue(1);
q.enqueue(2);
assertEquals(2, q.size());
assertTrue(r.isEmpty());
r.enqueue(3);
r.enqueue(4);
r.enqueue(5);
assertEquals(2, q.size());
assertEquals(3, r.size());
r.dequeue();
r.dequeue();
r.dequeue();
assertTrue(r.isEmpty());
assertEquals(2, q.size());
q.dequeue();
q.dequeue();
assertTrue(q.isEmpty());
}
@Test
public void testCopyConstructorOneElement() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
q.enqueue(1);
r = new Queue(q);
assertEquals(1, q.size());
assertEquals(1, r.size());
}
@Test
public void testCopyConstructorOneElementNotAliased() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
q.enqueue(1);
r = new Queue(q);
q.enqueue(2);
assertEquals(1, (int)r.dequeue());
assertTrue(r.isEmpty());
assertEquals(2, q.size());
}
@Test
public void testCopyConstructorTwoElements() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
q.enqueue(1);
q.enqueue(2);
r = new Queue(q);
assertEquals(2, q.size());
assertEquals(2, r.size());
}
@Test
public void testCopyConstructorTwoElementsNotAliased() throws Exception {
Queue q = new Queue();
UnboundedQueueInterface r;
q.enqueue(1);
q.enqueue(2);
r = new Queue(q);
q.enqueue(3);
assertEquals(1, (int)r.dequeue());
assertEquals(3, q.size());
assertEquals(1, r.size());
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help