CC143 Stacks and Queues

Objectives

• Gain familiarity with implementing stacks and queues using arrays and linked lists for underlying storage.
• Gain familiarity with raising exceptions. The goal of this assignment is to implement the stack and queue data structures.

The Interfaces

These are the interfaces that we worked with in the previous homework: LA 5 and HW 4.

Implementation notes

• Do not use any classes from the java.util package to implement the queue or stack.
• Provide complexity metrics (Big-O / Big-Theta) for the stack and queue operations that you implemented. Include the Big-O metrics in the JavaDoc comments for each of the operations inherited from one of the interface. (That is, you don't have to report Big-O metrics for any helper methods that are creating in the stack or queue implementations.) Needless to say, the Big-O values must be associated with the methods in the classes. They cannot be associated with the methods in the interfaces.
• The constructors for the bounded stack and bounded queue shall take a single int value as its parameter, the capacity of the data structure.
• The constructors for the unbounded stack and unbounded queue shall be parameterless.

For more information about the standard behavior of the stack and queue, please refer to the Powerpoint slides posted on the Moodle site. Another good source of information about stacks and queues is Wikipedia:

• http://en.wikipedia.org/wiki/Stack_(data_structure)
• http://en.wikipedia.org/wiki/Queue_(data_structure)

Standard Option

For the standard option, there will be two implementations for the unbounded data structures.

• Within the csc143.data_structures package, provide one implementation the bounded queue and the bounded stack. Use an array as the underlying data structure.
• Within the csc143.data_structures package, provide two implementations of the unbounded stack and the unbounded queue. For one of the implementations, use a linked list as the underlying data structure; for the other, an array.
• The initial size of the underlying array for the unbounded stack and unbounded queue shall be ten (10) elements.

The initial size requirement for the underlying array may prompt you to make some changes within the project. Make sure you note that in your report notes.

Note: You will use these classes to implement the next assignment. You may find it easier to use these classes if they are generic. This is one of the pieces of the Challenge option.

Challenge Option

For the challenge option, add the following features:

• Constant-time operations
• Generic support

Constant-time operations

It is possible to have "all" of the operations be O(k). (The word "all" is in quotes because it is not necessary to have the "debug" methods be O(k). So, capacity, size, and toString can be O(N) and still be acceptable for Challenge points.) Make sure that the implementation for each method is O(k) for the challenge option, with the noted exclusion.

Hint: Refer to the Wikipedia articles listed above for a technique to make the methods O(k).

Generic support

Make the stack and queue interfaces and implementations generic. It should not affect the usefulness of your JUnit test cases. They will "default" to java.lang.Object, if the generic formal type is omitted. However, you are welcome to update the JUnit test cases for generics.

However, implementing the generic data structures adds a little wrinkle. Because of language limitations, one cannot instantiate an array of the generic type, the type given by the parameter. For a full discussion, see the generic tutorial on the Oracle website.

So, there will be a warning issued when the implementation is compiled. The warning message from the compiler should be suppressed using the annotation, @SuppressWarnings. If this annotation is used, it should be applied to the most limited scope and as infrequently as possible. For more information, check the tutorial on annotations or ask in the forum.