Before you start, fill out a "Project Plan" in PSP
with estimates of how long the program will be, how many defects you'll
encounter, and how long it'll take you. (You will not be graded on how
accurate your estimates are, but you are expected to make some
kind of reasonable estimate.)
As you work on the assignment,
keep track of all the defects you encounter,
and your time use, using the
PSP forms
(click on "Input" under "Defect Removal Data" or "Time Management Data"
respectively).
Write a "Dequeue" class
to hold a double-ended queue of Objects,
implemented as a dynamically-allocated linked list (not an array).
(Part of it is already done for you in the textbook; you are to complete
the definition and test it.)
It should provide at least the following operations:
- Create an empty dequeue.
- Test whether a dequeue is empty.
- Find the length of a dequeue.
- Add a specified Object to the front of a dequeue.
- Add a specified Object to the back of a dequeue.
- Remove (and return) the Object from the front of a dequeue, if
there is one.
- Remove (and return) the Object from the back of a dequeue, if
there is one.
- "toString()", converting the dequeue to a single String that makes
it easy to see all the contents of the queue in order.
- A "test" method containing adequate examples to test all of the
above operations. (Although it should also be possible to experiment
with the dequeue data structure interactively by using BlueJ to call
specific methods on specific objects.)
As always, remember to write down the contract of each of these methods,
and several examples of its use with correct answers, before writing any
code for the method itself.
And as always, design your program for modifiability and re-usability; I
reserve the right to change the assignment slightly the day before it's due,
and your next homework assignment may well be built on this one.
Hints:
- You may need one or more additional classes in order to do this.
- You
may implement the linked list "my way", as an abstract class with concrete
subclasses for Empty and NonEmpty or something like that, or "Goodrich
& Tamassia's way", with a null reference indicating the end of a
list. I don't care which you choose, as long as it works and is well
structured.
- You may do it as a singly-linked list, each entry referring to
the next, or as a doubly-linked list, with each entry referring to
both the next and the previous. The former is conceptually
simpler and more similar to examples I've shown you in class; the latter
resembles the example in the textbook, and is more flexible and symmetrical.
Again, I don't care which you
choose, as long as it works and is well structured.
- Application:
do exercise P-4.1 on page 181 of the textbook.
The problem in the textbook says "Write a program that takes as input a
sequence of transactions of the form..." Since I don't want to waste a
lot of time on input parsing, which isn't really relevant to the
problem, I recommend the following interface. Write a class named
Portfolio representing the shares currently owned, their
purchase prices and sequence. Provide three public methods:
- buy(numShares,price), which represents a "buy" action.
Note that calling the method again constitutes buying another batch of
shares on a subsequent day.
- sell(numShares,price), which represents a "sell" action.
Note that calling the method again constitutes selling another batch
of shares on a subsequent day.
- gainSoFar(), which returns the total capital gain (or
loss) for all the shares sold to date.
The example in the textbook could be tested, then, by the sequence of
calls
buy(100,20)
buy(20,24)
buy(200,36)
sell(150,30)
gainSoFar()
The final gainSoFar() call should return the answer 940.
Hint: You'll probably need a queue of some sort.
Fortunately, you just wrote one in the previous part of the assignment.
(You may not need all of the capabilities of the Dequeue class.)
Since you've already got the Dequeue and related classes in a package, I
recommend that you add one more class, Portfolio, to the
same package. (There are more elegant ways for one Java program
to use another; if you want to try these, look up "packages" in the
Flanagan book or your favorite Java book.)
You may also need another new class to represent a transaction in the
history. Decide what information you need to store about such a
transaction, and design an appropriate class.
-
How to turn this in: Once you've got all of this working,
"WinZip" the entire folder into a single file and
send me an
e-mail, attaching this ZIP file.
If you have any comments about problems you encountered in writing the
program, or things you learned, put these in the body of the e-mail.