For today’s lab, you need to complete the LinkedQueue implementation. Follow the
ID: 3711669 • Letter: F
Question
For today’s lab, you need to complete the LinkedQueue implementation. Follow the guidance in the java files to complete the queue services (methods) and the driver program.
1. Complete LinkedQueue.java.
2. Complete the driver TestQueue.java.
3. Run the driver and check if operations on the queue are correctly implemented.
//*********************************************************** // LinkedQueue.java
// A linked-list implementation of the classic FIFO queue interface.
//***********************************************************
public class LinkedQueue implements QueueADT {
private Node front, back; private int numElements;
//---------------------------------------------
// Constructor; initializes the front and back pointers // and the number of elements.
//---------------------------------------------
public LinkedQueue() {
}
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item) {
}
//---------------------------------------------
// Removes and returns object from front of queue.
//---------------------------------------------
public Object dequeue() {
}
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
public boolean isEmpty() {
}
//---------------------------------------------
// Returns true if queue is full, but it never is.
//---------------------------------------------
public boolean isFull() {
}
//---------------------------------------------
// Returns the number of elements in the queue.
//---------------------------------------------
public int size() {
} //---------------------------------------------
// Returns a string containing the elements of the queue
// from first to last
//---------------------------------------------
public String toString() {
String result = " ";
Node temp = front;
while (temp != null) {
result += temp.getElement() + " ";
temp = temp.getNext();
}
return result;
}
}
//************************************************************
//Node.java
//A general node for a singly linked list of objects.
//************************************************************
public class Node {
private Node next;
private Object element;
//-------------------------------------------------------
//Creates an empty node
//-------------------------------------------------------
public Node() {
next = null;
element = null;
}
//-------------------------------------------------------
//Creates a node storing a specified element
//-------------------------------------------------------
public Node(Object element) {
next = null;
this.element = element;
}
//-------------------------------------------------------
//Returns the node that follows this one
//-------------------------------------------------------
public Node getNext() {
return next;
}
//-------------------------------------------------------
//Sets the node that follows this one
//-------------------------------------------------------
public void setNext(Node node) {
next = node;
}
//-------------------------------------------------------
//Returns the element stored in this node
//-------------------------------------------------------
public Object getElement() {
return element;
}
//-------------------------------------------------------
//Sets the element stored in this node
//-------------------------------------------------------
public void setElement(Object element) {
this.element = element;
}
}
//**********************************************************
// QueueADT.java
// The classic FIFO queue interface.
//**********************************************************
public interface QueueADT {
//---------------------------------------------
// Puts item on end of queue.
//---------------------------------------------
public void enqueue(Object item);
//---------------------------------------------
// Removes and returns object from front of queue.
//-------------------------------------------
public Object dequeue();
//---------------------------------------------
// Returns true if queue is empty.
//---------------------------------------------
public boolean isEmpty();
//---------------------------------------------
// Returns true if queue is full.
//---------------------------------------------
public boolean isFull();
//---------------------------------------------
//Returns the number of elements in the queue.
//---------------------------------------------
public int size();
}
//**********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations. //**********************************************************
public class TestQueue {
public static void main(String[] args) {
QueueADT q = new LinkedQueue();
System.out.println(" Enqueuing chocolate, cake, pie, truffles:");
q.enqueue("chocolate");
q.enqueue("cake");
q.enqueue("pie");
q.enqueue("truffles");
System.out.println(" Here's the queue: " + q);
// put your code here: print the size of the queue
System.out.println(" Dequeuing two...");
//put your code here: call the dequeue method twice and print out the dequeued items
System.out.println(" Enqueuing cookies, profiteroles, mousse, cheesecake, ice cream:");
q.enqueue("cookies");
q.enqueue("profiteroles");
q.enqueue("mousse");
q.enqueue("cheesecake");
q.enqueue("ice cream");
//think about which of the above items cannot be added into the queue?
System.out.println(" Here's the queue again: " + q);
System.out.println("Now it contains " + q.size() + " items.");
System.out.println(" Dequeuing everything in queue");
//put your code here: dequeue everything in the queue now using a loop
System.out.println(" Now it contains " + q.size() + " items.");
if (q.isEmpty())
System.out.println("Queue is empty!");
else
System.out.println("Queue is not empty -- why not??!!");
}
}
Explanation / Answer
Below is your code: -
LinkedQueue.java
//*********************************************************** // LinkedQueue.java
// A linked-list implementation of the classic FIFO queue interface.
//***********************************************************
public class LinkedQueue implements QueueADT {
private Node front, back;
private int numElements;
// ---------------------------------------------
// Constructor; initializes the front and back pointers // and the number of
// elements.
// ---------------------------------------------
public LinkedQueue() {
numElements = 0;
front = back = null;
}
// ---------------------------------------------
// Puts item on end of queue.
// ---------------------------------------------
public void enqueue(Object item) {
Node node = new Node(item);
if (isEmpty())
front = node;
else
back.setNext(node);
back = node;
numElements++;
}
// ---------------------------------------------
// Removes and returns object from front of queue.
// ---------------------------------------------
public Object dequeue() {
if (isEmpty())
return null;
Object result = front.getElement();
front = front.getNext();
numElements--;
if (isEmpty())
back = null;
return result;
}
// ---------------------------------------------
// Returns true if queue is empty.
// ---------------------------------------------
public boolean isEmpty() {
return (numElements == 0);
}
// ---------------------------------------------
// Returns true if queue is full, but it never is.
// ---------------------------------------------
public boolean isFull() {
return false;
}
// ---------------------------------------------
// Returns the number of elements in the queue.
// ---------------------------------------------
public int size() {
return numElements;
} // ---------------------------------------------
// Returns a string containing the elements of the queue
// from first to last
// ---------------------------------------------
public String toString() {
String result = " ";
Node temp = front;
while (temp != null) {
result += temp.getElement() + " ";
temp = temp.getNext();
}
return result;
}
}
Node.java
//************************************************************
//Node.java
//A general node for a singly linked list of objects.
//************************************************************
public class Node {
private Node next;
private Object element;
// -------------------------------------------------------
// Creates an empty node
// -------------------------------------------------------
public Node() {
next = null;
element = null;
}
// -------------------------------------------------------
// Creates a node storing a specified element
// -------------------------------------------------------
public Node(Object element) {
next = null;
this.element = element;
}
// -------------------------------------------------------
// Returns the node that follows this one
// -------------------------------------------------------
public Node getNext() {
return next;
}
// -------------------------------------------------------
// Sets the node that follows this one
// -------------------------------------------------------
public void setNext(Node node) {
next = node;
}
// -------------------------------------------------------
// Returns the element stored in this node
// -------------------------------------------------------
public Object getElement() {
return element;
}
// -------------------------------------------------------
// Sets the element stored in this node
// -------------------------------------------------------
public void setElement(Object element) {
this.element = element;
}
}
QueueADT.java
//**********************************************************
// QueueADT.java
// The classic FIFO queue interface.
//**********************************************************
public interface QueueADT {
// ---------------------------------------------
// Puts item on end of queue.
// ---------------------------------------------
public void enqueue(Object item);
// ---------------------------------------------
// Removes and returns object from front of queue.
// -------------------------------------------
public Object dequeue();
// ---------------------------------------------
// Returns true if queue is empty.
// ---------------------------------------------
public boolean isEmpty();
// ---------------------------------------------
// Returns true if queue is full.
// ---------------------------------------------
public boolean isFull();
// ---------------------------------------------
// Returns the number of elements in the queue.
// ---------------------------------------------
public int size();
}
TestQueue.java
//**********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations. //**********************************************************
public class TestQueue {
public static void main(String[] args) {
QueueADT q = new LinkedQueue();
System.out.println(" Enqueuing chocolate, cake, pie, truffles:");
q.enqueue("chocolate");
q.enqueue("cake");
q.enqueue("pie");
q.enqueue("truffles");
System.out.println(" Here's the queue: " + q);
// put your code here: print the size of the queue
System.out.println("Now it contains " + q.size() + " items.");
System.out.println(" Dequeuing two...");
// put your code here: call the dequeue method twice and print out the
// dequeued items
q.dequeue();
q.dequeue();
System.out.println(" Here's the queue: " + q);
System.out.println(" Enqueuing cookies, profiteroles, mousse, cheesecake, ice cream:");
q.enqueue("cookies");
q.enqueue("profiteroles");
q.enqueue("mousse");
q.enqueue("cheesecake");
q.enqueue("ice cream");
// think about which of the above items cannot be added into the queue?
System.out.println(" Here's the queue again: " + q);
System.out.println("Now it contains " + q.size() + " items.");
System.out.println(" Dequeuing everything in queue");
// put your code here: dequeue everything in the queue now using a loop
while(!q.isEmpty()) {
q.dequeue();
}
System.out.println(" Now it contains " + q.size() + " items.");
if (q.isEmpty())
System.out.println("Queue is empty!");
else
System.out.println("Queue is not empty -- why not??!!");
}
}
Output
Enqueuing chocolate, cake, pie, truffles:
Here's the queue:
chocolate
cake
pie
truffles
Now it contains 4 items.
Dequeuing two...
Here's the queue:
pie
truffles
Enqueuing cookies, profiteroles, mousse, cheesecake, ice cream:
Here's the queue again:
pie
truffles
cookies
profiteroles
mousse
cheesecake
ice cream
Now it contains 7 items.
Dequeuing everything in queue
Now it contains 0 items.
Queue is empty!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.