CS 61BL Summer 2021
About Beacon Ed Gradescope Queue Resources Staff
Project 1: Deques
Introduction
Getting the Skeleton Files and Working with a Partner The Deque API
Project Tasks
MaxArrayDeque
Guitar Hero
GuitarString
Just For Fun: TTFAF
Even More Fun
Why It Works
Submission and Grading
Frequently Asked Questions
Tips
The due date for this project is Sunday, 07/04 at midnight. You cannot use slip days on projects, though you can turn in up to 2 days late for partial credit. You must submit with your partner.
Introduction
In Project 1, we will build implementations of a “Double Ended Queue” using both lists and arrays in a package that other classes can use. The project is roughly split into three parts: the testing portion, the data structure portion and the application portion.
In the test writing part of the project, you will write unit tests to set goals and expectations for your nished project. You will ll in the two provided testing les, and
, and both will use the JUnit testing suite.
In the data structure part of the project, you will create two Java les: LinkedListDeque.java and ArrayDeque.java , with public
methods listed below. You will be verifying the correctness of these data structures yourself using the randomized and timing test skills you gained from Lab 3.
In the application part of this project, you’ll create a Java le MaxArrayDeque.java as well as use your package to ultimately
implement a sound synthesizer capable of playing music from Guitar Hero. You must test your MaxArrayDeque , but we’ll provide the tests for sound synthesizer.
We will provide relatively little scaffolding. In other words, we’ll say what you should do, but not how.
Additionally, we will be enforcing style. You must follow the style guide or you will lose points on the autograder.
Getting the Skeleton Files and Working with a Partner
As with all projects, we recommend doing pair programming for as much of the project as possible. This means that you and your partner should
LinkedListDequeTest.java
ArrayDequeTest.java
be on a Zoom call, where one person is typing and both are collectively deciding what to write. Some bene ts of pair programming are:
Both partners are on the same page and understand all parts of the project
You are much more likely to catch bugs or mistakes when there are two sets of eyes
You can discuss how to proceed, so you won’t get stuck as often You avoid merge conflicts.
The point about merge conflicts is especially important to avoid hassle with Git! To avoid merge conflicts, we recommend that you always clearly communicate with your partner what parts of the project you are working on, and avoid working on the same thing on each of your local computers. An example of a good workflow might be:
1. Both partners hop on a Zoom call
2. Partner1 pulls the skeleton code.
3. Both partners start thinking about what to write for the project.
Partner1 types it down, acting as the scribe.
4. After working for an hour, Partner1 has to go to dinner. Partner1
pushes the code to the remote partner repository (nicknamed
origin) and leaves the Zoom call.
5. Partner2 is bored and wants to keep working, so they pull from the
partner repository (nicknamed origin). This gets Partner2 all the
work that they just did on the Zoom call.
6. Partner2 works on ArrayDeque for a while, and lets Partner1 know.
7. After dinner, Partner1 also wants to work. They know Partner2 is
currently making changes to ArrayDeque, so they decide to avoid making changes there to prevent merge conflicts. Instead, Partner1 works on LinkedListDeque.
8. Partner2 decides to go to bed. They push their changes to the remote.
9. Partner1 also nishes working on LinkedList. They try to push to the remote, but realize that the remote has changes they don’t have, so
they must pull rst. Partner1 pulls, and Git is able to automatically merge. Now, Partner1’s computer has the most up-to-date changes to ArrayDeque from Partner2, as well as Partner1’s changes to LinkedListDeque. Partner1 can push to the remote, and now the remote is fully up to date!
As with Project 0, you should start by downloading the skeleton les.
To do this, head to the folder containing your copy of your partner repository. For example, if your partnership is ‘p101’, then head to the ‘sp21-p101’ folder (or any subdirectory).
To make sure you have the latest copy of the skeleton les, use the command:
If you’re using a newer version of git, you might need to run:
You should now see a proj1 directory appear with two folders:
git pull skeleton main
git pull skeleton main –allow-unrelated-histories
proj1 deque
LinkedListDequeTest.java
ArrayDequeTest.java
Deque.java
gh2
GuitarHeroLite.java
GuitarPlayer.java
GuitarString.java
──├ ──├ ──├
──└ ──└
──└ ──├
──├
TTFAF.java
TestGuitarString.java
If you get some sort of error, STOP and either gure it out by carefully reading the git guide or seek help at Lab or Ed. You’ll potentially save yourself a lot of trouble vs. guess-and-check with git commands. If you nd yourself trying to use commands recommended by Google like
force push , don’t. Don’t use force push, even if a post you found on Stack Overflow says to do it!
The only provided les in the skeleton are the empty testing les as well as some skeleton for the second part of this project located in the gh2 folder (guitar hero 2).
Before we get into the details of the Deque API and the implementation requirements, let’s briefly talk about packages and why we are using them in this project.
Packages
Part of this project is using packages to separate logic and functionality. At the end of the project, you’ll have two packages: the
package that provides an implementation of the data structure, and the gh2 package that implements a synthesizer used to play guitar hero. You should already see folders with these names in the starter code, and your job is to implement them. Let’s look at the speci cs for what a package really is.
A package is a collection of Java classes that all work together towards some common goal. We’ve already seen packages in CS 61B without knowing it. For example, org.junit is a package that contains various classes useful for testing, including our familiar
which contains useful static methods like words, when we saw
deque
class, . In other
org.junit
, the was the package name, was the class name,
org.junit.Assert.assertEquals
Deque
assertEquals
Assert
Assert
──└ ──├
and was the method name. We call
the “canonical name” of the
method, and we call the “simple name” of the method.
When creating a package, we specify that code is part of a package by specifying the package name at the top of the le using the package keyword. For example, if we wanted to declare that a le is part of the
deque package, we’d add the following line to the top of the le.
If a programmer wanted to use a class or method from our deque package, they would have to either use the full canonical name, e.g.
, or alternately use import
, at which point they could just use the simple
name . So import statements just allow you to use the simple name of a class/method.
Typically, package names are the internet address of the entity writing the code, but backwards. For example, the JUnit library is hosted at
junit.org , so the package is called org.junit .
Why are packages useful? It all boils down to that word “canonical”. As long as no two programmers use the same package name for their package, we can freely use the same class name in several different contexts. For example, there might exist a class called
, which is different from
. Given the requirement to either
use the full canonical name or to use an import, this means we’ll never accidentally use one class when we meant to use the other.
Conceptually, you can think of packages as being similar to different folders on your computer. When you are building a large system, it is a good idea to organize it into different packages.
assertEquals
org.junit.Assert.assertEquals
package deque;
deque.ArrayDeque
deque.ArrayDeque
ArrayDeque
com.hrblock.TaxCalculator
com.turbotax.TaxCalculator
assertEquals
From this point forwards, most of our code in CS 61B will be part of a package.
With that out of the way, let’s talk about the methods that a Deque should have.
The Deque API
The double ended queue is very similar to the SLList and AList classes that we’ve discussed in class. Here is a de nition from cplusplus.com.
Deque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).
Speci cally, any deque implementation must have exactly the following operations:
public void addFirst(T item) : Adds an item of type T to the front of the deque. You can assume that item is never
.
: Adds an item of type T to the back of the deque. You can assume that item is never
null
public void addLast(T item)
.
empty, otherwise.
deque.
public void printDeque() : Prints the items in the deque
from rst to last, separated by a space. Once all the items have been printed, print out a new line.
null
public boolean isEmpty()
false
: Returns true if deque is : Returns the number of items in the
public int size()
: Removes and returns the item at the front of the deque. If no such item exists, returns null .
public T removeLast() : Removes and returns the item at the back of the deque. If no such item exists, returns null .
public T get(int index) : Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth. If no such item exists, returns null . Must not alter the deque!
In addition, we also want our Deques to implement the special method:
public boolean equals(Object o) : Returns whether or not the parameter o is equal to the Deque. o is considered equal if it is a Deque and if it contains the same contents (as goverened by the generic T ’s equals method) in the same order.
Your deques should accept any generic type (not just integers). For information on creating and using generic data structures, see lecture 5. Make sure to pay close attention to the rules of thumb on the last slide about generics.
So… we’ve de ned a bunch of methods that any Deque should have. There are two speci c ways we want you to implement a Deque (one powered by a Linked List, and the other by an array), but ultimately, they’ll have the same methods and external behavior. Have we learned about any programming tools that could enable us to do this? If you said, “Of course, silly, that sounds like an interface”, then you would be correct (and we would be silly)!
We have provided an empty le for the Deque interface. Recall that an interface does NOT typically provide implementations for any methods. Instead, it just lets you de ne what methods a class that implements the Deque interface must have.
Project Tasks
public T removeFirst()
0. Testing
In agreement with the principles of test driven development, you will rst write tests for the two Deque implementations, and then write the Deque implementations to pass the tests you wrote. Write JUnit tests that con rm your Deque has the expected behavior de ned in the section above. Your two testing les, LinkedListDequeTest.java and ArrayDequeTest.java will likely be identical except for the dynamic type of the Deques being created. We recommend writing at least one test for every method described in the Deque API above, e.g. a test that targets the addFirst method.
The compiler will be upset if you write tests referencing classes/methods that haven’t been de ned anywhere, so you’ll have to de ne the methods of the Deque interface. Write in the method signatures for all the methods described in the section above, and you should be good to start writing your tests.
Note: In the Deque interface, give a implementation, which returns is 0 . Since your and implement the interface, given the default
implementation, now you won’t have to de ne isEmpty in the LinkedListDeque and ArrayDeque classes!
isEmpty()
default
true
if the
size()
LinkedListDeque
ArrayDeque
Deque
isEmpty()
You’ll fail all your tests, since you haven’t written your LinkedListDeque and ArrayDeque to do anything yet. This is the intention: in test driven development, you set the goals/expectations rst and slowly build up your code base until you can pass the tests.
Edit Friday July 2nd 11:51 AM: The paragraph below is no longer relevant. You may instantiate new deques however you like. You do not need to use the static ad and lld variables provided in the skeleton.
This portion of the project is meant to ensure that you learn to write your own tests, instead of just relying on the autograder. In the real world, there is no autograder to tell you if your code works! Additionally, running your own tests locally is much faster, easier, and doesn’t use up autograder tokens.
1. Linked List Deque
As your rst deque implementation, you’ll build the LinkedListDeque class, which will be Linked List based.
Your operations are subject to the following rules:
add and remove operations must not involve any looping or recursion. A single such operation must take “constant time”, i.e. execution time should not depend on the size of the deque. This means that you cannot use loops that go over all/most elements of the deque.
must use iteration, not recursion. must take constant time.
Iterating over the LinkedListDeque using a for-each loop should take time proportional to the number of items.
Do not maintain references to items that are no longer in the deque. The amount of memory that your program uses at any given time must be proportional to the number of items. For example, if you add 10,000 items to the deque, and then remove 9,999 items, the
get
size
There is a Deque variable provided in both testing classes ( ad in ArrayDequeTest and lld for LinkedListDequeTest). You must use these variables for your tests, if you want the autograder to be able to run correctly. Do not reassign the variable at the top of your tests. Instead, you can reassign the variable to a new Deque as the very last line of each test. This is different from how we normally write tests, but it is necessary for the autograder.
resulting memory usage should amount to a deque with 1 item, and not 10,000. Remember that the Java garbage collector will “delete” things for us if and only if there are no pointers to that object.
Implement all the methods listed above in “The Deque API” section. Add @Override tags to each method that overrides a Deque method.
In addition, you also need to implement:
public LinkedListDeque() : Creates an empty linked list deque.
public T getRecursive(int index) : Same as get, but uses recursion.
You may add any private helper classes or methods in LinkedListDeque.java if you deem it necessary. If you do, please
add helpful javadoc comments for your and your TAs sake.
While this may sound simple, there are many design issues to consider, and you may nd the implementation more challenging than you’d expect. Make sure to consult the lecture on doubly linked lists, particularly the slides on sentinel nodes: two sentinel topology, and circular sentinel topology. I prefer the circular approach. You are not allowed to use Java’s built in LinkedList data structure (or any data structure from java.util.* ) in your implementation and the autograder will instantly give you a 0 if we detect that you’ve imported any such data structure.
2. Array Deque
As your second deque implementation, you’ll build the ArrayDeque class. This deque must use arrays as the core data structure.
For this implementation, your operations are subject to the following rules:
and must take constant time, except during resizing operations.
get and size must take constant time.
The starting size of your underlying array should be 8. At any given moment, the current size of the array should be proportional to the number of items.
The amount of memory that your program uses at any given time must be proportional to the number of items. For example, if you add 10,000 items to the deque, and then remove 9,999 items, you shouldn’t still be using an array of length 10,000ish. For arrays of length 16 or more, your usage factor should always be at least 25%. This means that before performing a remove operation that will bring the number of elements in the array under 25% the length of the array, you should resize the size of the array down. For smaller arrays, your usage factor can be arbitrarily low.
Implement all the methods listed above in “The Deque API” section. Add @Override tags to each method that overrides a Deque method.
In addition, you also need to implement:
public ArrayDeque() : Creates an empty array deque.
You may add any private helper classes or methods in ArrayDeque.java if you deem it necessary.
You will need to somehow keep track of what array indices hold the Deque’s front and back elements. We strongly recommend that you treat your array as circular for this exercise. In other words, if your front item is at position zero, and you addFirst , the new front should loop back around to the end of the array (so the new front item in the deque will be the last item in the underlying array). This will result in far fewer headaches than non-circular approaches. See the project 1 demo slides for more details.
add
remove
Correctly resizing your array is very tricky, and will require some deep thought. Try drawing out various approaches by hand. It may take you quite some time to come up with the right approach, and we encourage you to debate the big ideas with your fellow students or TAs. Make sure that your actual implementation is by you alone.
MaxArrayDeque
After you’ve fully implemented your correctness, you will now build the
and tested its . A
MaxArrayDeque
MaxArrayDeque
ArrayDeque
MaxArrayDeque
MaxArrayDeque has all of the methods that an
but it also has 2 additional methods and a new constructor:
has,
: creates a with the given .
: returns the maximum element in the deque as governed by the previously given . If the
is empty, simply return
: returns the maximum
element in the deque as governed by the parameter
c . If the MaxArrayDeque is empty, simply return .
The can either tell you the max element in itself by using the given to it in the constructor, or an arbitrary that is different from the one given in the constructor.
Do not override the equals(Object o) method of this class.
If you nd yourself starting off by copying your entire ArrayDeque implementation in a MaxArrayDeque le, then you’re doing it wrong. This is an exercise in clean code, and redundancy is one our worst enemies when battling complexity! For a hint, re-read the second sentence of this section above.
Comparator
ArrayDeque
public MaxArrayDeque(Comparator
public T max()
Comparator
null .
public T max(Comparator
Comparator
null
MaxArrayDeque
Comparator
Comparator
There are no runtime requirements on these additional methods, we only care about the correctness of your answer. Sometimes, there might be multiple elements in the MaxArrayDeque that are all equal and hence all the max: in in this case, you can return any of them and they will be considered correct.
You should write tests for this part as well! They do not need to be nearly as robust as your randomized and timing tests you created for the two Deque implementations above since the functionality you’re adding is fairly simple. You’ll likely be creating multiple Comparator
Comparator objects to do something useful ( nd the maximum element) and to get practice writing your own Comparator classes. You will not be turning in these tests, but we still highly suggest making them for your sake.
You will not use the MaxArrayDeque you made for the next part. It is its own isolated exercise.
Guitar Hero
In this part of the project, we will create another package for generating synthesized musical instruments using the deque package we just made. We’ll get the opportunity to use our data structure for implementing an algorithm that allows us to simulate the plucking of a guitar string.
The GH2 Package
The gh2 package has just one primary component that you will edit:
GuitarString , a class which uses an Deque
We’ve provided you with skeleton code for which is where you will use your deque package that you made in the rst part of this project.
GuitarString
We want to nish the GuitarString le, which should use the deque package to replicate the sound of a plucked string. We’ll be
using the Karplus-Strong algorithm, which is quite easy to implement with a Deque .
The Karplus-Algorithm is simply the following three steps:
1. Replace every item in a Deque with random noise ( double values between -0.5 and 0.5).
2. Remove the front double in the and average it with the next double in the Deque (hint: use and
get() ) multiplied by an energy decay factor of 0.996 (we’ll call this entire quantity ). Then, add newDouble to the back of the .
3. Play the ( ) that you dequeued in step 2. Go back to step 2 (and repeat forever).
Or visually, if the Deque is as shown on the top, we’d remove the 0.2, combine it with the 0.4 to form 0.2988, add the 0.2988, and play the 0.2.
Deque
removeFirst)
newDouble
Deque
double
newDouble
GuitarString
You can play a value with the method.
double
For example
speaker to extend itself to 1/3rd of its total reach,
StdAudio.play(0.333)
StdAudio.play(-0.9) will tell it to stretch its little heart backwards almost as far as it can reach. Movement of the speaker diaphragm displaces air, and if you displace air in nice patterns, these disruptions will be interpreted by your consciousness as pleasing thanks to billions of years of evolution. See this page for more. If you simply do
StdAudio.play(0.9) and never play anything again, the diaphragm shown in the image would just be sitting still 9/10ths of the way forwards.
Complete GuitarString.java so that it implements steps 1 and 2 of the Karplus-Strong algorithm. Note that you will have to ll you
Deque buffer with zeros in the constructor. Step 3 will be done by the client of the class.
Make sure to open your project with Maven, as usual, otherwise IntelliJ won’t be able to nd StdAudio .
For example, the provided class provides a sample test that attempts to play an A-note on a guitar string. If you run the test should hear an A-note when you run this test. If you don’t, you should try the method and debug from there. Consider adding a or method
StdAudio.play
will tell the diaphragm of your
GuitarString
GuitarString
testPluckTheAString
TestGuitarString
testTic
print
toString
to that will help you see what’s going on between tics.
Note: we’ve said Deque here, but not speci ed which Deque implementation to use. That is because we only need those operations
addLast , , and get and we know that classes that implement have them. So you are free to choose either the
for the actual implementation, or the
. For an optional (but highly suggested) exercise, think
about the tradeoffs with using one vs the other and discuss with your friends what you think the better choice is, or if they’re both equally ne choices.
GuitarHeroLite
You should now also be able to use the GuitarHeroLite class. Running it will provide a graphical interface, allowing the user (you!) to interactively play sounds using the gh2 package’s GuitarString class.
The following part of the assignment is not graded.
Consider creating a program GuitarHero that is similar to GuitarHeroLite , but supports a total of 37 notes on the chromatic scale from 110Hz to 880Hz. Use the following 37 keys to represent the
keyboard, from lowest note to highest note:
;
This keyboard arrangement imitates a piano keyboard: The “white keys” are on the qwerty and zxcv rows and the “black keys” on the 12345 and asdf rows of the keyboard.
The ith character of the string keyboard corresponds to a frequency of $440 \cdot 2^{(i – 24) / 12}$, so that the character ‘q’ is 110Hz, ‘i’ is
LinkedListDeque
removeFirst
Deque
ArrayDeque
String keyboard = “q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.
GuitarString.java
220Hz, ‘v’ is 440Hz, and ‘ ‘ is 880Hz. Don’t even think of including 37 individual GuitarString variables or a 37-way if statement! Instead, create an array of 37 objects and use
to gure out which key was typed. Make sure your program does not crash if a key is pressed that does not
correspond to one of your 37 notes.
Just For Fun: TTFAF
Once you’re relatively comfortable that GuitarString should be working, try running TTFAF . Make sure your sound is on!
You can read the and TTFAF classes to gure out how they work. in particular includes (as commented-out code) an example of how to use it another way.
Even More Fun
This part of the assignment is not graded and just for fun.
Harp strings: Create a Harp class in the gh2 package. Flipping the sign of the new value before enqueueing it in tic() will change the sound from guitar-like to harp-like. You may want to play with the decay factors to improve the realism, and adjust the buffer sizes by a factor of two since the natural resonance frequency is cut in half by the tic() change.
Drums: Create a Drum class in the gh2 package. Flipping the sign of a new value with probability 0.5 before enqueueing it in tic() will produce a drum sound. A decay factor of 1.0 (no decay) will yield a better sound, and you will need to adjust the set of frequencies used.
Guitars play each note on one of 6 physical strings. To simulate this you can divide your GuitarString instances into 6 groups, and
keyboard.indexOf(key)
GuitarString
GuitarPlayer
TTFAF
when a string is plucked, zero out all other strings in that group. Pianos come with a damper pedal which can be used to make the strings stationary. You can implement this by, on iterations where a certain key (such as Shift) is held down, changing the decay factor. While we have used equal temperament, the ear nds it more pleasing when musical intervals follow the small fractions in the just intonation system. For example, when a musician uses a brass instrument to play a perfect fth harmonically, the ratio of frequencies is 3/2 = 1.5 rather than 27/12 1.498. Write a program where each successive pair of notes has just intonation.
Why It Works
The two primary components that make the Karplus-Strong algorithm work are the ring buffer feedback mechanism and the averaging operation.
The ring buffer feedback mechanism. The ring buffer models the medium (a string tied down at both ends) in which the energy travels back and forth. The length of the ring buffer determines the fundamental frequency of the resulting sound. Sonically, the feedback mechanism reinforces only the fundamental frequency and its harmonics (frequencies at integer multiples of the fundamental). The energy decay factor (.996 in this case) models the slight dissipation in energy as the wave makes a round trip through the string.
The averaging operation. The averaging operation serves as a gentle low-pass lter (which removes higher frequencies while allowing lower frequencies to pass, hence the name). Because it is in the path of the feedback, this has the effect of gradually attenuating the higher harmonics while keeping the lower ones, which corresponds closely with how a plucked guitar string sounds.
∼
Submission and Grading
To submit the project, add and commit your les, then push to your remote repository. Then on Gradescope go to the assignment and submit there. One partner should submit the project, and then add the other to the submission.
The entire project is worth 24 points, or 8% of your total grade.
: 1 point : 1 point
: 9 points : 9 points
: 2 points : 2 points
Frequently Asked Questions
Deque
Intellij is telling me “The method … of type LinkedListDeque has the same erasure as … of type Deque but does not override it.”
You probably forgot the generic T in the implements line of your class signature (i.e. you wrote instead of
). If you used something other than T for your generic type parameter, use that instead.
Q: How should I print the items in my deque when I don’t know their type?
A: It’s ne to use the default String that will be printed (this string comes from an Object’s implementation of toString() , which we’ll talk more about later this semester). For example, if you called the generic type in your class , to print Jumanji j , you can call .
deque/LinkedListDequeTest.java
deque/ArrayDequeTest
deque/LinkedListDeque.java
deque/ArrayDeque
deque/MaxArrayDeque
gh2/GuitarString
implements Deque
implements Deque
Jumanji
System.out.print(j)
Q: I can’t get Java to create an array of generic objects!
A: Use the strange syntax we saw in lecture, i.e. T[] a = (T[]) new Object[1000]; . Here, T is a generic type, it’s a placeholder for other Object types like “String” or “Integer”.
Q: I tried that but I’m getting a compiler warning?
A: Sorry, this is something the designers of Java messed up when they introduced generics into Java. There’s no nice way around it. Enjoy your compiler warning. We’ll talk more about this in a few weeks.
Q: How do I make my arrows point to particular elds of a data structure?
In your diagram from lecture it looked like the arrows were able to point to the middle of an array or at speci c elds of a node.
A: Any time I drew an arrow in class that pointed at an object, the pointer was to the ENTIRE object, not a particular eld of an object. In fact it is impossible for a reference to point to the elds of an object in Java.
Guitar Hero
I’m getting a “class le contains wrong class” error.
Make sure all of your Java les have the right package declaration at the top. Also make sure that anything that is part of the gh2 package is in a folder called “gh2”.
I’m getting a message that I did not override an abstract method, but I am!
Chances are you have a typo. You should always use the @Override tag when overriding methods so that the compiler will nd any such typos.
When I try to run the provided tests I get “No runnable methods”.
Make sure you’ve uncommented the tests, including the @Test annotation.
When I try to compile my code, it says type K#1 is not compatible with type K#2, or something similar.
If you’re de ning an inner class, make sure it does not redeclare a new generic type parameter, e.g. the rst given in private class should not be there!
I’m getting a strange autograder error!
While GuitarString is a guitar string simulator, it should not involve playing any sounds. The playing should be done by the
GuitarString client.
Credits: RingBuffer gures from wikipedia. This assignment adapted
from Kevin Wayne’s Guitar Heroine assignment. Tips
Check out the project 1 slides for some additional visually oriented tips.
If you’re stuck and don’t even know where to start: One great rst step is implementing SLList and/or AList . For maximum ef ciency, work with a friend or two or three.
Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery. If you wrote too much stuff and feel overwhelmed, comment out whatever is unnecessary.
If your rst try goes badly, don’t be afraid to scrap your code and start over. The amount of code for each class isn’t actually that much (my solution is about 130 lines for each .java le, including all comments and whitespace).
For ArrayDeque , consider not doing resizing at all until you know your code works without it. Resizing is a performance optimization (and is required for full credit).
MapWizard
Work out what your data structures will look like on paper before you try implementing them in code! If you can nd a willing friend, have them give commands, while you attempt to draw everything out. Try to come up with operations that might reveal problems with your implementation.
Make sure you think carefully about what happens if the data structure goes from empty, to some non-zero size (e.g. 4 items) back down to zero again, and then back to some non-zero size. This is a common oversight.
Sentinel nodes make life much easier, once you understand them.
Circular data structures may take a little while to understand, but make life much easier for both implementations (but especially the
ArrayDeque ).
Consider a helper function to do little tasks like compute array indices. For example, in my implementation of , I wrote a function called that computed the index immediately “before” a given index.
Consider using the Java Visualizer (which you installed in lab 1) to visualize your Deque as you step through with the debugger. The visualizer is an icon of a blue coffee cup with an eye, and is the tab next to the “Console” tab in the debugger panel). See the CS 61B plugin guide if you can’t gure out how to get the visualizer to show.
ArrayDeque
int minusOne(int index)