This is a Queue.java file which I need to write the code and I attached the Node
ID: 3731163 • Letter: T
Question
This is a Queue.java file which I need to write the code and I attached the Node.java and QueueTest.java file below as well.
import java.util.NoSuchElementException;
/**
* A classic first-in first-out queue data structure implemented
* as a linked sequence of nodes.
*
* @param <E>
* the type of element held in this queue
*/
public class Queue<E> {
/**
* Queue uses a node based implementation, where the nodes form a singly
* linked-list like structure. The queue must maintain a reference to the
* node holding the element at the front of the queue, and a reference to
* the node holding the element at the end of the queue.
*/
/**
* The node at the front of the queue (the first node, or head, of the
* linked list).
*/
private Node<E> front;
/**
* The node at the back of the queue (the last node of the linked list)
*/
private Node<E> back;
/**
* The number of elements stored in this queue (or the number of nodes)
*/
private int size;
/**
* Creates an empty queue (size is zero).
*/
public Queue() {
}
/**
* Enqueue an element. This operation adds the element to the back of the
* queue.
*
* @param element
* the element to add to the back of the queue
*/
public void enqueue(E element) {
}
/**
* Dequeue an element. This operation removes and returns the element at the
* front of the queue if the queue is not empty.
*
* @return the element at the front of the queue if the queue is not empty
* @throws NoSuchElementException
* if the queue is empty
*/
public E dequeue() {
}
/**
* Return the element at the front of the queue without dequeuing the
* element.
*
* @return the element at the front of the queue if the queue is not empty
* @throws NoSuchElementException
* if the queue is empty
*/
public E peek() {
}
/**
* Returns the number of elements in this queue.
*
* @return the number of elements in this queue
*/
public int size() {
}
/**
* Returns true if this queue is empty, and false otherwise.
*
* @return true if this queue is empty, and false otherwise
*/
public boolean isEmpty() {
}
/**
* Returns the node at the front of the queue. This method is here for
* debugging and testing purposes.
*
* @return the node at the front of the queue
*/
Node<E> getFront() {
return this.front;
}
/**
* Returns the node at the back of the queue. This method is here for
* debugging and testing purposes.
*
* @return the node at the back of the queue
*/
Node<E> getBack() {
return this.back;
}
/**
* Returns a hash code for this queue. The hash code is computed using the
* elements of this stack.
*
* @return a hash code for this queue
*/
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
Node<E> n = this.front;
while (n != null) {
result = prime * result + n.getElement().hashCode();
n = n.getNext();
}
return result;
}
/**
* Compares the specified object to this queue for equality. Two queues are
* equal if they contain the same number of elements in the same order.
*
* @param obj
* the object to compare to this queue for equality
* @return true if the specified object is equal to this queue
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (this.getClass() != obj.getClass()) {
return false;
}
Queue<E> other = (Queue<E>) obj;
if (this.size == other.size()) {
Node<E> n = this.front;
Node<E> nOther = other.front;
for (int i = 0; i < this.size; i++) {
if (!n.getElement().equals(nOther.getElement())) {
return false;
}
n = n.getNext();
nOther = nOther.getNext();
}
}
return true;
}
/**
* Returns a string representation of this queue. The string representation
* consists of a list of the queue's elements from the front of the queue to
* the back of the queue, enclosed in square brackets ("[]"). Adjacent
* elements are separated by the characters ", " (comma and space). Elements
* are converted to strings as by String.valueOf(Object).
*
* @return a string representation of this queue
*/
@Override
public String toString() {
// see equals for an example of iterating over the nodes of the queue
}
}
Node.java
/**
* A simple node class for implementing singly linked sequences. Each node is an
* aggregation of a data element and another node (the next node in the
* sequence).
*
* @param <E>
* the type of the data element stored in this node
*/
public class Node<E> {
private E element;
private Node<E> next;
/**
* Create a node holding the given data element and having the given next
* node in the sequence.
*
* @param element
* the data element to store in the node
* @param next
* the next node in the sequence
*/
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
/**
* Get the next node in the sequence. Returns null if there are no more
* nodes in the sequence.
*
* @return the next node in the sequence
*/
public Node<E> getNext() {
return this.next;
}
/**
* Set the next node in the sequence. Setting the next node to null
* indicates the end of the sequence.
*
* @param next
* the next node in the sequence
*/
public void setNext(Node<E> next) {
this.next = next;
}
/**
* Get the data element stored in this node.
*
* @return the data element stored in this node
*/
public E getElement() {
return this.element;
}
/**
* Set the data element stored in this node.
*
* @param element
* the data element to store in this node
*/
public void setElement(E element) {
this.element = element;
}
}
QueueTest.java
import static org.junit.Assert.*;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import org.junit.FixMethodOrder;
import org.junit.Rule;
import org.junit.runners.MethodSorters;
import org.junit.Test;
import org.junit.rules.Timeout;
@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class QueueTest {
@Rule
public Timeout globalTimeout = Timeout.seconds(2);
@Test
public void test00_fields() {
try {
List<Field> fields = Arrays.asList(eecs2030.lab6.Queue.class.getDeclaredFields());
for (Field f : fields) {
String name = f.getName();
if (name.equals("front")) {
if (f.getType() != eecs2030.lab6.Node.class) {
fail("this.front has the wrong type");
}
} else if (name.equals("back")) {
if (f.getType() != eecs2030.lab6.Node.class) {
fail("this.back has the wrong type");
}
} else if (name.equals("size")) {
if (f.getType() != Integer.TYPE) {
fail("this.size has the wrong type");
}
} else {
fail("there is a field named: " + name + " that should not be in the class");
}
}
} catch (Exception x) {
fail("exception occurred trying to get the fields of this class");
}
}
@Test
public void test01_ctor() {
Queue<String> q = new Queue<>();
assertNull("this.back is not null", q.getBack());
assertNull("this.front is not null", q.getFront());
assertEquals("this.size is not 0", 0, q.size());
}
/**
* Checks that the structure of the queue got matches the structure of the
* list exp. Checks that the queue has the correct size, front node, and
* back node, and that the elements in the queue equal the elements the
* expected list.
*
* @param exp
* the expected list
* @param got
* the queue to check
*/
private <E> void checkStructure(List<E> exp, eecs2030.lab6.Queue<E> got) {
if (exp.isEmpty()) {
if (got.size() != 0) {
fail("expected an empty list; got a queue of size: " + got.size());
}
if (got.getFront() != null) {
fail("expected an empty list; got a queue with a non-null front node");
}
if (got.getBack() != null) {
fail("expected an empty list; got a queue with a non-null back node");
}
} else {
if (exp.size() != got.size()) {
String err = String.format("queue has the wrong size; expected size: %d, got size: %d", exp.size(),
got.size());
fail(err);
}
Node<E> n = got.getFront();
for (int i = 0; i < exp.size(); i++) {
E expData = exp.get(i);
E gotData = n.getElement();
if (!expData.equals(gotData)) {
String err = String.format("node: %d has the wrong element; expected: %s but got: %s", i, expData,
gotData);
fail(err);
}
if (i == exp.size() - 1) {
// at the back node
if (got.getBack() != n) {
fail("this.back is pointing to the wrong node");
}
}
n = n.getNext();
if (n == null && i != exp.size() - 1) {
String err = String.format("node: %d has an unexpected null next link", i);
fail(err);
}
}
if (n != null) {
fail("this.back has a non-null next link");
}
}
}
@Test
public void test01_enqueue() {
Queue<String> q = new Queue<>();
q.enqueue("abc");
List<String> t = Arrays.asList("abc");
this.checkStructure(t, q);
}
@Test
public void test02_enqueue() {
Queue<Integer> q = new Queue<>();
q.enqueue(100);
q.enqueue(200);
List<Integer> t = Arrays.asList(100, 200);
this.checkStructure(t, q);
}
@Test
public void test03_enqueue() {
Queue<Integer> q = new Queue<>();
q.enqueue(100);
q.enqueue(200);
q.enqueue(300);
q.enqueue(400);
q.enqueue(0);
List<Integer> t = Arrays.asList(100, 200, 300, 400, 0);
this.checkStructure(t, q);
}
private static <E> Queue<E> makeQueue(List<E> t) {
Queue<E> q = new Queue<>();
if (t.isEmpty()) {
return q;
}
try {
Class<?> c = q.getClass();
Node<E> n = new Node<>(t.get(0), null);
Node<E> front = n;
Node<E> back = n;
for (int i = 1; i < t.size(); i++) {
back = new Node<>(t.get(i), null);
n.setNext(back);
n = back;
}
// try to set q.front
Field f = c.getDeclaredField("front");
f.setAccessible(true);
f.set(q, front);
// try to set q.back and q.size
Field b = c.getDeclaredField("back");
b.setAccessible(true);
b.set(q, back);
Field s = c.getDeclaredField("size");
s.setAccessible(true);
s.setInt(q, t.size());
} catch (NoSuchFieldException x) {
x.printStackTrace();
} catch (IllegalAccessException x) {
x.printStackTrace();
}
return q;
}
@Test
public void test04_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("abc"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
t.remove(0);
this.checkStructure(t, q);
}
@Test
public void test05_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("abc", "def"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
t.remove(0);
this.checkStructure(t, q);
}
@Test
public void test06_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("abc", "def", "xyz"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
t.remove(0);
this.checkStructure(t, q);
}
@Test
public void test07_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("abc", "def", "xyz"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
q.dequeue();
t.remove(0);
t.remove(0);
this.checkStructure(t, q);
}
@Test
public void test08_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("1", "2", "3"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
q.dequeue();
q.dequeue();
t.remove(0);
t.remove(0);
t.remove(0);
this.checkStructure(t, q);
}
@Test(expected = NoSuchElementException.class)
public void test09_dequeue() {
Queue<Double> q = new Queue<Double>();
q.dequeue();
}
@Test(expected = NoSuchElementException.class)
public void test10_dequeue() {
List<String> t = new ArrayList<>(Arrays.asList("1", "2", "3"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
q.dequeue();
q.dequeue();
q.dequeue();
}
@Test(expected = NoSuchElementException.class)
public void test11_peek() {
Queue<Double> q = new Queue<Double>();
q.peek();
}
@Test
public void test12_peek() {
List<String> t = new ArrayList<>(Arrays.asList("1", "2", "3"));
Queue<String> q = QueueTest.makeQueue(t);
String got = q.peek();
assertEquals("peek returned the wrong element",
t.get(0), got);
}
@Test
public void test13_peek() {
List<String> t = new ArrayList<>(Arrays.asList("1", "2", "3"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
String got = q.peek();
assertEquals("peek returned the wrong element",
t.get(1), got);
}
@Test
public void test14_peek() {
List<String> t = new ArrayList<>(Arrays.asList("1", "2", "3"));
Queue<String> q = QueueTest.makeQueue(t);
q.dequeue();
q.dequeue();
String got = q.peek();
assertEquals("peek returned the wrong element",
t.get(2), got);
}
@Test
public void test15_size() {
Queue<Double> q = new Queue<Double>();
int got = q.size();
assertEquals("size returned the wrong value",
0, got);
}
@Test
public void test16_size() {
Queue<Double> q = new Queue<Double>();
q.enqueue(1.0);
int got = q.size();
assertEquals("size returned the wrong value",
1, got);
}
@Test
public void test17_size() {
Queue<Double> q = new Queue<Double>();
q.enqueue(1.0);
q.enqueue(2.0);
int got = q.size();
assertEquals("size returned the wrong value",
2, got);
}
@Test
public void test18_size() {
Queue<Double> q = new Queue<Double>();
q.enqueue(1.0);
q.enqueue(2.0);
q.enqueue(3.0);
int got = q.size();
assertEquals("size returned the wrong value",
3, got);
}
@Test
public void test19_size() {
Queue<Double> q = new Queue<Double>();
q.enqueue(1.0);
q.enqueue(2.0);
q.enqueue(3.0);
q.enqueue(4.0);
q.enqueue(5.0);
q.enqueue(6.0);
q.dequeue();
int got = q.size();
assertEquals("size returned the wrong value",
5, got);
}
@Test
public void test20_size() {
Queue<Double> q = new Queue<Double>();
q.enqueue(1.0);
q.dequeue();
q.enqueue(2.0);
q.enqueue(3.0);
q.enqueue(4.0);
q.enqueue(5.0);
q.enqueue(6.0);
q.dequeue();
q.enqueue(7.0);
int got = q.size();
assertEquals("size returned the wrong value",
5, got);
}
@Test
public void test21_isEmpty() {
Queue<Double> q = new Queue<Double>();
assertTrue("isEmpty returned false for an empty queue",
q.isEmpty());
}
@Test
public void test22_isEmpty() {
Queue<Double> q = new Queue<Double>();
q.enqueue(2.0);
q.dequeue();
assertTrue("isEmpty returned false for an empty queue",
q.isEmpty());
}
@Test
public void test23_isEmpty() {
Queue<Double> q = new Queue<Double>();
q.enqueue(0.0);
assertFalse("isEmpty returned true for an non-empty queue",
q.isEmpty());
}
@Test
public void test24_isEmpty() {
Queue<Double> q = new Queue<Double>();
q.enqueue(0.0);
q.dequeue();
q.enqueue(1.0);
assertFalse("isEmpty returned true for an non-empty queue",
q.isEmpty());
}
@Test
public void test25_toString() {
Queue<Double> q = new Queue<Double>();
assertEquals("[]", q.toString());
}
@Test
public void test26_toString() {
Queue<String> q = new Queue<>();
q.enqueue("hi");
assertEquals("[hi]", q.toString());
}
@Test
public void test27_toString() {
Queue<String> q = new Queue<>();
q.enqueue("hi");
q.enqueue("high");
assertEquals("[hi, high]", q.toString());
}
@Test
public void test28_toString() {
Queue<String> q = new Queue<>();
q.enqueue("hi");
q.enqueue("high");
q.enqueue("why");
assertEquals("[hi, high, why]", q.toString());
}
@Test
public void test29_toString() {
Queue<Integer> q = new Queue<>();
q.enqueue(0);
q.enqueue(1);
q.dequeue();
q.enqueue(2);
q.dequeue();
q.enqueue(3);
assertEquals("[2, 3]", q.toString());
}
}
Explanation / Answer
import java.util.NoSuchElementException;
/**
* A classic first-in first-out queue data structure implemented
* as a linked sequence of nodes.
*
* @param <E>
* the type of element held in this queue
*/
public class Queue<E> {
/**
* Queue uses a node based implementation, where the nodes form a singly
* linked-list like structure. The queue must maintain a reference to the
* node holding the element at the front of the queue, and a reference to
* the node holding the element at the end of the queue.
*/
/**
* The node at the front of the queue (the first node, or head, of the
* linked list).
*/
private Node<E> front;
/**
* The node at the back of the queue (the last node of the linked list)
*/
private Node<E> back;
/**
* The number of elements stored in this queue (or the number of nodes)
*/
private int size;
/**
* Creates an empty queue (size is zero).
*/
public Queue() {
front = null;
back = null;
}
/**
* Enqueue an element. This operation adds the element to the back of the
* queue.
*
* @param element
* the element to add to the back of the queue
*/
public void enqueue(E element) {
Node<E> newNode = new Node(element);
if(front == null){
front = newNode;
back = front;
}
}
/**
* Dequeue an element. This operation removes and returns the element at the
* front of the queue if the queue is not empty.
*
* @return the element at the front of the queue if the queue is not empty
* @throws NoSuchElementException
* if the queue is empty
*/
public E dequeue() {
if(front == null)
return null;
E v = null;
if(front.next == null) {
v = front.getElement();
front = null;
back = null;
}else{
v = front.getElement();
front = front.getNext();
}
return v;
}
/**
* Return the element at the front of the queue without dequeuing the
* element.
*
* @return the element at the front of the queue if the queue is not empty
* @throws NoSuchElementException
* if the queue is empty
*/
public E peek() {
if(front == null)
return null;
else
return front.getElement();
}
/**
* Returns the number of elements in this queue.
*
* @return the number of elements in this queue
*/
public int size() {
int count = 0;
Node<E> t = front;
while(t != null) {
count++;
t = t.getNext();
}
return count;
}
/**
* Returns true if this queue is empty, and false otherwise.
*
* @return true if this queue is empty, and false otherwise
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns the node at the front of the queue. This method is here for
* debugging and testing purposes.
*
* @return the node at the front of the queue
*/
Node<E> getFront() {
return this.front;
}
/**
* Returns the node at the back of the queue. This method is here for
* debugging and testing purposes.
*
* @return the node at the back of the queue
*/
Node<E> getBack() {
return this.back;
}
/**
* Returns a hash code for this queue. The hash code is computed using the
* elements of this stack.
*
* @return a hash code for this queue
*/
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
Node<E> n = this.front;
while (n != null) {
result = prime * result + n.getElement().hashCode();
n = n.getNext();
}
return result;
}
/**
* Compares the specified object to this queue for equality. Two queues are
* equal if they contain the same number of elements in the same order.
*
* @param obj
* the object to compare to this queue for equality
* @return true if the specified object is equal to this queue
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (this.getClass() != obj.getClass()) {
return false;
}
Queue<E> other = (Queue<E>) obj;
if (this.size == other.size()) {
Node<E> n = this.front;
Node<E> nOther = other.front;
for (int i = 0; i < this.size; i++) {
if (!n.getElement().equals(nOther.getElement())) {
return false;
}
}
}
return true;
}
/**
* Returns a string representation of this queue. The string representation
* consists of a list of the queue's elements from the front of the queue to
* the back of the queue, enclosed in square brackets ("[]"). Adjacent
* elements are separated by the characters ", " (comma and space). Elements
* are converted to strings as by String.valueOf(Object).
*
* @return a string representation of this queue
*/
@Override
public String toString() {
String result = "[";
Node<E> t = front;
while(t != null) {
result = result + t.getElement()+" ";
t = t.getNext();
}
result = result + "]";
return result;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.