Java A Queue is a FIFO (first in, first out) data structure. Consider the follow
ID: 3667386 • Letter: J
Question
Java
A Queue is a FIFO (first in, first out) data structure. Consider the following queue interface:
public interface Queue {
public int size(); // current queue size
public boolean isEmpty(); // true if queue is empty
public void enqueue(Object element); // add element at end of queue
public Object dequeue(); // return and remove first element.
public Object first(); // return (without removing) first element
public Object last(); // return (without removing) last element
public String toString(); // return a string representation of the queue content
public Iterator iterator(); // element iterator
}
The iterator iterates over all elements of the queue. Operations not allowed on an empty queue shall generate an
unchecked exception.
Tasks:
Create a linked implementation LinkedQueue.java of the interface Queue. Use the head-and-tail
approach.
Write also a program QueueMain.java showing how all methods work.
Create Javadoc comments in the code and generates good-looking and extensive HTML documentation
for the interface and the class. All public class members shall be documented.
Notice:
The implementation shall be linked, i.e. a sequence of linked nodes where each node represents an
element.
You are not allowed to use any of the predefined classes in the Java library.
In the report, the HTML pages generated by the classes Queue and LinkedQueue shall be attached. Attach
no other HTML pages!
- Write a JUnit test for the class LinkedQueue
Explanation / Answer
//Programs:
//QueueMain.java
import java.util.Scanner;
/**
* Unit tests the <tt>LinkedQueue</tt> data type.
*/
public class QueueMain {
public static void main(String[] args) {
Scanner StdIn=new Scanner(System.in);
LinkedQueue q = new LinkedQueue();
int item=0;
while (item!=-999) {
System.out.println("Enter element <-999 to stop>");
item = StdIn.nextInt();
if (item!=0) q.enqueue(item);
else if (!q.isEmpty())
System.out.print(q.dequeue() + " ");
}
System.out.println("(" + q.size() + " left on queue)");
boolean status=q.isEmpty();
if(status==true)
System.out.print("Queue is empty");
else
System.out.print("Queue is not empty");
System.out.println("Last element: "+q.last());
System.out.println("Last element: "+q.first());
System.out.println("Queue: "+ q.toString());
}
}
/**********************************/
//LinkedQueue.java
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedQueue implements Queue{
private int N; // number of elements on queue
private Node first; // beginning of queue
private Node last; // end of queue
// helper linked list class
private class Node {
private int item;
private Node next;
}
/**
* Initializes an empty queue.
*/
public LinkedQueue() {
first = null;
last = null;
N = 0;
assert check();
}
/**
* Is this queue empty?
* @return true if this queue is empty; false otherwise
*/
@Override
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
@Override
public int size() {
return N;
}
/**
* Adds the item to this queue.
* @param element
*/
@Override
public void enqueue(Object element) {
Node oldlast = last;
last = new Node();
last.item = (int)element;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
assert check();
}
/**
* Removes and returns the item on this queue that was least recently added.
* @return the item on this queue that was least recently added
* @throws java.util.NoSuchElementException if this queue is empty
*/
@Override
public Object dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
int item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null; // to avoid loitering
assert check();
return item;
}
@Override
public Object first() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
@Override
public Object last() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return last.item;
}
/**
* Returns an iterator that iterates over the items in this queue in FIFO order.
* @return an iterator that iterates over the items in this queue in FIFO order
*/
public Iterator iterator() {
return new ListIterator();
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Object next() {
if (!hasNext()) throw new NoSuchElementException();
int item = current.item;
current = current.next;
return item;
}
}
/**
* Returns a string representation of this queue.
* @return the sequence of items in FIFO order, separated by spaces
*/
@Override
public String toString()
{
StringBuilder s = new StringBuilder();
for (Object listIter = iterator().next(); iterator().hasNext();){
s.append(iterator().next()).append(" ");
}
return s.toString();
}
// check internal invariants
private boolean check() {
if (N < 0) {
return false;
}
else if (N == 0) {
if (first != null) return false;
if (last != null) return false;
}
else if (N == 1) {
if (first == null || last == null) return false;
if (first != last) return false;
if (first.next != null) return false;
}
else {
if (first == null || last == null) return false;
if (first == last) return false;
if (first.next == null) return false;
if (last.next != null) return false;
// check internal consistency of instance variable N
int numberOfNodes = 0;
for (Node x = first; x != null && numberOfNodes <= N; x = x.next) {
numberOfNodes++;
}
if (numberOfNodes != N) return false;
// check internal consistency of instance variable last
Node lastNode = first;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
if (last != lastNode) return false;
}
return true;
}
}
/*********************************/
//Queue.java
import java.util.Iterator;
public interface Queue {
public int size(); // current queue size
public boolean isEmpty(); // true if queue is empty
public void enqueue(Object element); // add element at end of queue
public Object dequeue(); // return and remove first element.
public Object first(); // return (without removing) first element
public Object last(); // return (without removing) last element
@Override
public String toString(); // return a string representation of the queue content
public Iterator iterator(); // element iterator
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.