IC211 Spring AY 2020

HW Odds and Ends

Name (Last, First): ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________

[100pts] A "queue" is an object that stores data. It has a very simple interface that mimics the behaviour of waiting in a line (or a "queue" as the British say). Specifically, its interface is: empty which tells you whether the queue is empty, enqueue which adds data to the "back" of the queue, and dequeue which removes a piece of data from the front of the queue. Your job is to define a class Queue for storing queues of strings. Here is the interface it must support:

Interface for Queue class Node for you to use 
/**
   * adds s to the back of the queue
   */
  public void enqueue(String s) { ... }

  /**
   * removes and returns string from the front of the queue
   */
  public String dequeue() { ... }

  /**
   * returns true if the queue is empty
   */
  public boolean empty() { ... }
 You'll need to use a linked list. To be helpful, here's a Node class for you to put inside your Queue class: 

private class Node {
  public String data;
  public Node next;
  public Node(String d, Node n) {
    data = d;
    next = n;
  }
}

We call a class within a class a "nested class", and a non-static nested class is called an "inner class". It is appropriate to put a class definition inside a class if the intent is to have it private and only used as a helper class for the parent class. In this case, the Queue is what people will use, and they don't need to know about the Node objects inside.

Do NOT make a Node.java file for this class.

Note: Since you'll want to add to the back of the list, you should really keep a pointer to the last node of the list as well as the first node (see diagram to the right). This makes adding to the back of the list easy.

The file HW07.java should work with your Queue implementation. If you've done it right, then you should be able to run HW07 like this: 
~/$ java HW07
this is the end done
this
is
the
end

Turn in this sheet, along with a printout of your Queue.java source code, and a screen capture showing HW07 running on the above input.