It makes a nice example for us, because it's got a simple, small, well-defined interface, and it's dead useful. However, last lesson we saw a simple bit of extra functionality we wanted to add (a "peek" method that would allow us to see what was in the front of the queue without actually dequeueing it) that caused us some problems. We wanted to derive a new class,
PeekaQueue
, from our original Queue that
added this bit of functionality, but we were originally
flummoxed, because with only enqueue(), dequeue(), and empty()
at our disposal, the "peek" operation was impossible to
implement in a reasonable fashion.
Do you remember what our solution was?
We changed the Node class (which was nested in Queue) from
private
to protected
and did the
same for the head
and tail
references. This allowed our PeekaQueue
class
access to head.data
, which is what we needed to
implement a peek()
method.
This worked, and it sure was an easy fix, but hopefully it
left you feeling a bit queasy. Not that I want you to feel
queasy, but I hope that you recognized that we were doing
something a bit underhanded. The problem is that we strayed
from the enlightened path of strict separation of interface
from implementation. So now the custodian of the Queue class
cannot change its implementation without worrying about
breaking derived classes like PeekaQueue.
The problem is that there is no interface, whether public or protected, for traversing the elements of the Queue in a non-destructive way. If we added such an interface, even if only as protected, then new classes that extend Queue could implement a much wider range of features (like peek) and still be completely separated from the underlying implementation of the Queue as a linked list. So what would such an interface look like?
class Iter { public boolean hasNext(); // tells you whether there is a "next" string public String next(); // returns the "next" string and advances }Now, this iterator really belongs to our class Queue. It doesn't make any sense at all without a Queue object around. Therefore, we will define the Iter class inside the Queue class, just like we did with Node. Finally, we give Queue one new public method,
iterator()
, which returns an Iter
initialized to the very first element in the Queue.
With this functionality in place, PeekaQueue becomes quite easy.
Just to close the loop, let's take a look at a simple program that uses PeekaQueue. This is a funny program. It reads a ;-terminated sequence of words, and it prints success if the sequence of words is comprised of two intermingled copies of the same sequence of words. Like this:
a1 a2 a3 b1 a4 b2 b3 b4 b5 a5where we assume ai = bi. It's just a cute application of a PeekaQueue.
public boolean hasa(String s);that returns true if String s is currently in the queue. For example, the following program reads through a file, reports and duplicate strings it finds, and prints out the contents of the file with duplicates removed.
Just to make clear the tremendous value of this program, we'll use it to remove duplicates from a well-known pop song (by a Grammy award winning artist). You'll see that with this technology we can substantially reduce the time required to listen to this song!
shake.txt | |
i stay out too late got nothing in my brain that's what people say mmm-mmm that's what people say mmm-mmm i go on too many dates but i can't make them stay at least that's what people say mmm-mmm that's what people say mmm-mmm but i keep cruising can't stop won't stop moving it's like i got this music in my mind saying it's gonna be alright 'cause the players gonna play play play play play and the haters gonna hate hate hate hate hate baby i'm just gonna shake shake shake shake shake i shake it off i shake it off heart-breakers gonna break break break break break and the fakers gonna fake fake fake fake fake baby i'm just gonna shake shake shake shake shake i shake it off i shake it off |
~/$ java Ex2 shake.txt duplicate that's duplicate what [...] duplicate off
i stay out too late got nothing in my brain that's what people say mmm-mmm go on many dates but can't make them at least keep cruising stop won't moving it's like this music mind saying gonna be alright 'cause the players play and haters hate baby i'm just shake it off heart-breakers break fakers fake
|
So now we move on to the real question: how do we implement HasaQueue? The answer is that we let the iterator do the work for us! Iterators give us a nice, well-defined interface that we can separate away from the implementation (i.e. the linked-list stuff). You'll see in this code that we can iterate through the elements of the Queue (without actually dequeuing anything) without referring to Node in an way.