IC211: Meet Queue

Overview

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 use a linked list of course. To be helpful, I've created a Node class for you:

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

We'll let the data be public here so that the data and next fields are accessible from within the class Queue.

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.

Part 1

You will produce Queue.java defining class Queue, with the interface defined above. For this Step, you should have three files: Lab04.java should simply work with your Queue implementation without modification. If you've done it right, then you should be able to run Lab04 like this:

~/$ java HW07
this is 
the end done
this
is
the
end

Part 2

At this point, everything works fine. However, you may feel like the class "Node" violates our principles of Encapsulation/Data-Hiding and, even more so, our fundamental principle of separating interface from implementation. After all, the mere existence of "Node" is an implementation decision. Shouldn't we feel bad about having made it "public"? [Hint: yes.]

For this next step, you will make Node a private "inner-class" of Queue. What this means in practice is that you will simply move the class Node definition from Node.java inside the class Queue definition within the Queue.java file, and change "public class Node" to "private static class Node". After making the move, delete Node.java and Node.class:

rm Node.*

When you recompile, only recompile Queue.java. Do not recompile Lab04.java. Verify that running Lab04 (i.e. java Lab04) still works. Also, give the ls command and answer: what .class files are there, and what file do you think the compiled version of class Node ends up in?

What did we just do?

A class defined within another class is called an inner class.

An inner class that is marked "static" is just like a class defined in its own file except that its full name is now outer-class-name.inner-class-name. To be concrete, if we have class Alpha and inside of it define a static inner class Beta, then
- inside class Alpha we may refer to the inner class as "Beta", but
- outside class Alpha we must refer to the inner class as "Alpha.Beta"
Hopefully this makes sense, as it is completely analogous to the situation with static methods and data.
An inner class that is marked "private" can only be used within the outer class. To be concrete, if we have class Alpha and inside of it define a private inner class Beta, then only code inside Alpha can
- declare Beta variables, e.g.: Beta b = null;
- call new Beta, e.g.: new Beta();
- access fields of objects of type Beta or call Beta-specific methods.

The following example should help illustrate some of these points. The key idea is that, in the normal course of things, we use private inner classes for helper classes that are part of our implementation that we want to wall off from users of our classes.

Submit

You will only submit Queue.java:

submit -c=IC211 -p=lab04 Queue.java

I will provide a copy of Lab04.class to the submit server and, because you did Step 2, there should no longer be any need for the Node.java file.