Should I use arrays or linked lists in my implementations? In general we don't tell you how to implement your data structures—you can use arrays, linked lists, or maybe even invent your own new structure provide you abide by the specified time and space requirements. So, before you begin to write the code, make sure that your data structure will achieve the required resource bounds.
How serious are you about not calling any external library function other than those in
You will receive a substantial deduction.
The goal of this assignment is to implement data types from first principles, using
resizing arrays and linked lists—feel free to use
on future programming assignments.
We also require you to use
StdIn (instead of
because we will intercept the calls to
StdIn in our testing.
Can I add extra public methods to the
Can I use different names for the methods?
No, you must implement the API exactly as specified.
The only exception is the
main() method, which you should use for
What is meant by uniformly at random?
If there are n items in the randomized queue, then you should choose each one
with probability 1/n, up to the randomness of
independent of past decisions.
You can generate a pseudo-random integer between 0 and n−1 using
Given an array, how can I rearrange the entries in random order?
StdRandom.shuffle()—it implements the Knuth shuffle
discussed in lecture and runs in linear time. Note that depending on your implementation,
you may not need to call this method.
What should my deque (or randomized queue) iterator do if the deque
(or randomized queue) is structurally modified
at any time after the iterator is created (but before it is done iterating)?
You don't need to worry about this in your solution.
An industrial-strength solution (used in the Java libraries)
is to make the iterator fail-fast: throw a
java.lang.ConcurrentModificationException as soon as this is detected.
Why does the following code lead to a
generic array creation compile-time error when
Item is a generic
Java prohibits the creation of arrays of generic types. See the Q+A in Section 1.3 for a brief discussion. Instead, use a cast.Item a = new Item;
Unfortunately, this leads to a compiler warning.Item a = (Item) new Object;
The compiler says that my program uses unchecked or unsafe operations and to recompile with -Xlint:unchecked for details. Usually this means you did a potentially unsafe cast. When implementing a generic stack with an array, this is unavoidable since Java does not allow generic array creation. For example, the compiler outputs the following warning with ResizingArrayStack.java:
% javac ResizingArrayStack.java Note: ResizingArrayStack.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. % javac -Xlint:unchecked ResizingArrayStack.java ResizingArrayStack.java:25: warning: [unchecked] unchecked cast found : java.lang.Object required: Item a = (Item) new Object; ^ ResizingArrayStack.java:36: warning: [unchecked] unchecked cast found : java.lang.Object required: Item Item temp = (Item) new Object[capacity]; ^ 2 warnings
You should not make any other casts.
Checkstyle complains that my nested class' instance variables must be private and have accessor methods that are not private. Do I need to make them private? No, but there's no harm in doing so. The access modifier of a nested class' instance variable is irrelevant—regardless of its access modifiers, it can be accessed anywhere in the file. (Of course, the enclosing class' instance variables should be private.)
Can a nested class have a constructor? Yes.
What assumptions can I make about the input to
Standard input can contain any sequence of strings.
You may assume that there is one integer command-line argument k
and it is between 0 and the number of strings on standard input.
Will I lose points for loitering? Yes. Loitering is maintaining a useless reference to an object that could otherwise be garbage collected.
These are purely suggestions for how you might make progress. You do not have to follow these steps. These same steps apply to each of the two data types that you will be implementing.
RandomizedQueue. They are summarized in the table below. Every detail in these performance requirements is important. Do not proceed until you understand them.
|Non-iterator operations||Constant worst-case time||Constant amortized time|
|Iterator constructor||Constant worst-case time||linear in current # of items|
|Other iterator operations||Constant worst-case time||Constant worst-case time|
|Non-iterator memory use||Linear in current # of items||Linear in current # of items|
|Memory per iterator||Constant||Linear in current # of items|
RandomizedQueue. You might start by considering why a resizing array does not support constant worst-case time operations in a stack.
Deque, you know that if you call
addFirst()with the numbers 1 through n in ascending order, then call
removeLast()n times, you should see the numbers 1 through n in ascending order. As soon as you have those two methods written, you can write a unit test for these methods. Arguably even better are randomized unit tests (which we employ heavily in our correctness testing). We recommend that you create a client class with a name like
TestDeque, where each unit test is a method in this class. Don't forget to test your iterator.
Deque), you must decide whether to use a linked list, an array, or something else. If you make the wrong choice, you will not achieve the performance requirements and you will have to abandon your code and start over.