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.