600.226 Data Structures (Spring 2004 - Prof. Eisner)

Homework 3 ... due 4pm Friday 20 Feb 2004

Summary

Goal of this homework: More practice with abstract data types. You will implement both stacks and queues, and use both.

Collaboration policy for this homework: You must follow the CS Department Academic Integrity Code and this time may not collaborate with another student (in contrast to the previous homework). Of course, you may get help from the course staff.

How to hand in your work: instructions, upload page

What to hand in (all packaged up in a zip or tar file):

Acknowledgments: Many thanks to Yuan Chen (one of your CAs) for her great work writing the GUI class, test-driving the assignment, and providing some of these instructions.

Introduction

You use a word processor or text editor every day. Those programs add new features every year. But at their core, they simply let a user modify a sequence of characters. How is this sequence represented?

Since the user can insert or delete characters in the middle of the string, you might wish to use a List data structure as in chapter 5. In particular, a doubly linked list of characters would support efficient insertion and deletion into the middle of the sequence.

But suppose the user were only adding and deleting characters from the end of the string, by typing and backspacing. Then you could get away with using a Stack, which is simpler and cheaper.

But in fact, the user doesn't do so much more than that! The user only adds and deletes characters next to the cursor. You can therefore get away with using two stacks. One stack holds the characters to the left of the cursor. The other stack holds the characters to the right of the cursor. This diagram shows how to represent the word elephantine with the cursor between the letters p and h:

	     LEFT STACK               RIGHT STACK
         ___ ___ ___ ___       ___ ___ ___ ___ ___ ___ ___
	|_e_|_l_|_e_|_p_|     |_h_|_a_|_n_|_t_|_i_|_n_|_e_|
	bottom        top     top                    bottom

To move the cursor right, you would just pop the h from the right stack and push it onto the left stack:

	     LEFT STACK               RIGHT STACK
         ___ ___ ___ ___ ___       ___ ___ ___ ___ ___ ___
	|_e_|_l_|_e_|_p_|_h_|     |_a_|_n_|_t_|_i_|_n_|_e_|
	bottom            top     top                bottom

In this assignment, you'll build EditableString - a small word-processor class that uses this 2-stack representation. The class will include methods for inserting and deleting characters, and for moving the cursor. To test your class, we've provided a cute EditableStringWindow class that puts a window on the screen. Whenever the user presses a key, the window calls the appropriate one of your EditableString methods, such as backspace.

Your initial version of EditableString will just use the stack class that is built into Java. In the second half of the assignment, you will switch from using data structures to implementing them. In particular, you will implement your own stack class. The word processor should then work just as well with your stack class as it does with Java's!

The Files

Start by downloading the files from this source directory. Read the following descriptions carefully:

Implementing JavaStack and EditableString

You should be able to compile and run EditableStringWindow right away. You can see what the interface will look like, but it won't do much, since all the methods it calls are still stubs!

Your first job is to read through JavaStack.java and fill in the JavaStack.pop method, which is a stub. Make sure you know exactly what that method is supposed to do (by looking at the documentation of the Stack interface). To understand how to implement it in terms of java.util.Stack, look at the online java.util.Stack documentation. (Note: This is found at the standard source of Java platform documentation, java.sun.com.)

Your second job is to fill in all the methods of EditableString.java, replacing the stubs. Test your methods directly, and by using java EditableStringWindow. Just for fun, you could also try java EditableStringWindow 2, which creates two EditableStringWindows on the very same EditableString; thus edits in one window also affect the other window.

Important notes:

Implementing a Queue

The next part of the assignment is to implement a queue using a portion of an array. This is discussed extensively in chapter 4 of your textbook, so we won't give you many more instructions here.

Specifically, you should write an ArrayQueue class that implements the Queue interface that was provided to you. Your ArrayQueue class should also have 2 constructors:

Make sure that you throw QueueEmptyException and QueueFullException as appropriate; see the Queue interface for details. These are unchecked exceptions (because they are subclasses of RuntimeException), so they do not have to be mentioned in the method signatures.

As always, test your class carefully.

Implementing a Stack

Finally, you'll implement a stack. The book already gives you code for implementing stacks in terms of arrays and in terms of linked lists. So what other ways are left for you to try?

Well, a stack can theoretically be implemented in terms of a queue! That's because you can get to any element on a queue by repeatedly dequeuing the front element and enqueuing it again at the back. So if you want to remove ("pop") the element that you've just enqueued ("pushed"), you can get to it it by "cycling once around the queue."

Of course this is a silly way to implement a stack, just like doing arithmetic with Russian dolls is theoretically possible but silly. However, it gives you a chance to try out your queue code on a real problem.

Write a class ArrayQueueStack that implements Stack. It should contain a protected ArrayQueue q. All the stack methods should be implemented just by calling queue methods. You should take care to throw StackFullException and StackEmptyException rather than the corresponding queue exceptions, even though the stack exceptions are "morally equivalent" to the queue exceptions.

Using Your Stack

Now for the punchline. Change the constructor of EditableString so that it initializes left and right by calling new ArrayQueueStack() rather than new JavaStack(). Recompile everything. EditableStringWindow should work just as before!

To check that your exceptions work, you should change new ArrayQueueStack() to new ArrayQueueStack(30). Then if you type a line or two into the window, your methods should throw a StackFullException. The GUI explicitly catches this exception, and should display a message about it in the status bar at the bottom of the GUI window.

Answer the following in your Readme:
  1. If there are currently n characters in the EditableString, what is the worst-case asymptotic (big-Oh) runtime of the moveLeft method (a) when the stacks are implemented with JavaStack? (b) when the stacks are implemented with ArrayQueueStack?
  2. Same question for the moveToStart method.

Jason Eisner - jason@cs.jhu.edu - $Date: 2004/02/12 10:10:54 $