$8\mathrm{.}8$ Lab $14-$ Queue Implementation with LinkedList

Module $7$: Lab $14-$ Queue Implementation with LinkedList

This lab includes the following $.$java files:

L$13/$

$$ LinkedQueue.java

$$ MyQueue.java

LinkedQueue is the main in zyBooks, and MyQueue is the interface you are implementing in LinkedQueue.

Here is the starter jar with if you would like to code in a different environment: L$13.$jar.

A Queue is a FIFO $($First in First out$)$ data structure meaning that the first data to be inserted is the first to be removed so we can maintain a certain priority. Queues in Computer Science are much like queues$/$lines in real life. For example, at an ice cream booth people line up and the first person in line is the first to get ice cream and the last person in line is served last. We could maintain chronological order.

Implementing a Queue

We are going to be implementing a Queue using a linked list because as long as we keep references to the head and tail of the list we can have very fast removals and inserts to our queue.

The comments in the source file will guide you through exactly what each function should do$.$

Exceptions

Your stack may run into errors, such as trying to remove an element from an empty stack or add to a full one. We ask you to use exceptions to deal with such errors in this lab. Recall that exceptions are a way to signal errors, and you can use a throw statement to tell Java that something wrong has happened:

throw new NoSuchElementException$()$;

Remember that you don't have to catch these exceptions. Whoever calls our method has to deal with the exception with a try$/$catch or a throws declaration

Incremental Development

Remember to test your code as you go$.$ The main has individual tests written that will each give you output like the following if you implement it correctly:

Testing Add:

Add Looks Good

Completing the Code

IMPORTANT NOTE:

Remember that methods like poll$/$remove$,$ add$/$offer and element$/$peek$()$ are the SAME except one of them returns a value and one throws an exception. For example, once you have written poll then simply call poll from remove and if it returned null then throw the exception. Also, do not modify simulateBooth$().$ You will need that method for testing.

Finish the constructor

Make sure to change maxCount to the correct value

initialize size

Finish the size method

Finish the contains method

Finish add$/$offer

check if the queue is full

Create a new Node with name

if list is empty then create head and tail

if list is not empty insert the node at the tail

increment size

Finish remove$/$poll

check if queue is empty

remove the node at the head

return the name of the node that was removed

decrement size

Finish peek$/$element:

return the name of the item at the head of the list

import java.util.$*$;

public class LinkedQueue implements MyQueue$\{$

public class Node $\{$

String name;

Node next;

public Node$($String name$)\{$

this.name $=$ name;

$\}$

@Override

public String toString$()\{$

return name;

$\}$

$\}$

$/**$

$*$ a reference to the head of the Queue

$*/$

private Node head;

$/**$

$*$ a reference to the tail of the Queue

$*/$

private Node tail;

$/**$

$*$ maximum number of items that can simultaneously be in the Queue

$*/$

private final int maxCount;

$/**$

$*$ the current number of items in the Queue

$*/$

private int size;

$/**$TODO FINISH ME

$*$ The Constructor should set maxCount to the maximum amount of customers for the day

$*$ also make sure to initialize size

$*$ @param maxCount

$*/$

public LinkedQueue$($int maxCount$)\{$

$//$TODO: Change this

this.maxCount$=-1$;

$\}$

$/**$TODO FINISH ME

$*$ This method should add a new Node with the person's name at the

$*$ end of the Queue. This method should also check if the Queue

$*$ is full$($size of Queue $>$ maxCount$)$ and throw an exception if

$*$ the Queue is full

$*$

$*$ @param name $-$ person to add

$*$ @return true if item can be added

$*$ @throws IllegalStateException if the Queue is full

$*$ element cannot be added because it is a duplicate

$*/$

@Override

public boolean add$($String name$)\{$

return false;

$\}$

$/**$TODO FINISH ME

$*$ This method is the same as add EXCEPT that it simply returns

$*$ false if the item can't be inserted instead of throwing an exception

$*$

$*$ @param name

$*$ @return true if item can be inserted, false otherwise

$*/$

@Override

public boolean offer$($String name$)\{$

return false;

$\}$

$/**$TODO FINISH ME

$*$ returns the name of the element at the head of the Queue but do

$*$ NOT remove it

$*$

$*$ @return Element at the head of the Queue

$*$ @throws NoSuchElementException if the Queue i