Due Monday 26 Mar. 2001 11:59 PM.
In class, we discussed the
IStack and
IQueue interfaces and some
possible implementations.
In this assignment, you will provide several implementations of each.
Provide an implementation of a stack using an array.
An implementation of a queue using an array was given to you, so you don't need to do that.
Provide an implementation of a stack and a queue each
using a immutable lists (AList).
The queue implementation uses a simple, but non-obvious idea with two lists. The queue's contents, from front-to-back are the first list's contents followed by the second list's reversed contents. When enqueuing an element, you add it to the second list. When dequeuing an element, you get it from the first list, if it contains any elements. If no element is immediately available, you create a new first list from the reversal of the second list; the new second list is empty.
Provide an implementation of a stack and a queue each
using a mutable list (LRStruct).
Since a LRStruct
can be accessed and modified at the
end as well as the front, the two-list idea for queues is not
necessary.
Provide an implementation of a queue using a circular
doubly-linked list (CList).
Doubly-linked lists will be described in class and lab.
An implementation of stacks using doubly-linked lists wouldn't be essentially different from either list version above, so you don't need to implement that.
In addition, you should comment each interface-specified method with its "big-Oh" worst-case time complexity. This should include a sentence or two of explanation.
Your homework directory should contain the standard files
(well-written Java source code including a client to thoroughly test it all,
README,
UML diagram, Javadoc documentation) and be submitted with the command
turnin -c comp212 -p hw-stacks_queues your-homework-directory-name