We have seen how to efficiently implement a queue using a linked list. It is also possible to efficiently implement a queue using two stacks, even if the stacks are implemented with ArrayList
objects. That's what you will do in this assignment.
To implement a queue using two stacks, let's call the two stacks the inStack
and the outStack
. To enqueue an element, push it onto the inStack
. To dequeue, remove an element from the outStack
. Ah, but what if the outStack
is empty? If outStack
is empty but the inStack
is not, then the next element that should be dequeued is the one on the inStack
that was least recently enqueued. Unfortunately, that item is on the bottom of the inStack
. No problem: pop each element from the inStack
and push it onto the outStack
, and then that least-recently enqueued element ends up on the top of the outStack
. Furthermore, all elements on the outStack
are now in the correct order to be popped when dequeueing. (Pushing a number of elements onto a stack and then popping them off reverses their order.)
Download the files CS10Stack.java, CS10Queue.java, ArrayListStack.java, and StacksQueue.java. You will edit StacksQueue.java to fill in the missing method bodies. Do not make any changes to the other three files. You may write private helper methods in StacksQueue.java if you wish. Make sure that the dequeue
and front
methods return null
if the queue is empty.
Clearly, the isEmpty
operation requires Θ(1) time (assuming that the size
method of ArrayList
takes constant time, which is a valid assumption). The enqueue
operation should also take Θ(1) time, because it just pushes an item onto inStack
, which takes constant time (constant amortized time, anyway, even if the ArrayList must be expanded).
What about the dequeue
and front
methods? Suppose you start with an empty queue and then call enqueue
n times, followed by a call to dequeue
. For that single dequeue
operation, you need to pop the n elements from inStack
and push each of these n elements onto outStack
, finishing up with a single pop from outStack
. Therefore, a single dequeue
operation can take Θ(n) time on a queue with n elements. That's not very good. But notice that once you've pushed an element onto outStack
, it stays there until it's popped. So, for a given element, it is pushed onto inStack
once, and it is popped from inStack
, pushed onto outStack
, and popped from outStack
at most once. That makes for a total of at most 2n pushes and pops per element over the entire time that the queue operates. Therefore, the amortized time per opertion is Θ(1).
Test your code with the main
method included in StacksQueue.java.
Via Canvas, submit your StacksQueue.java file and the console output from testing. You don't need to submit CS10Stack.java, CS10Queue.java, or ArrayListStack.java, since they are provided and you won't be changing them.