SA-6, due Oct 9

Assignment

We have seen how to implement a queue using an array and using a linked list. It is also possible to implement a queue using two stacks. This may sound like a silly thing to do, but it is actually the most efficient way to implement a queue in a functional language like Haskell, where data is immutable. Lists are represented as linked lists. It is fast to add or remove an item at the front of a list - just link it to the list or return the rest of the list. Therefore stacks are easy to implement efficiently. Because it is not possible to modify the last item in a list the only way to add or remove an element at the end of a list is to rebuild the entire list.

The basic idea is to use two stacks, the inStack and the outStack. Things that are to be enqueued are always pushed onto the inStack. Things that are to be dequeued are always popped from the outStack. If the outStack is empty but the inStack is not, then the next item that should be dequeued is the thing on the inStack that was added earliest. Unfortunately, that item is on the bottom of the inStack. However, by popping each item off of the inStack and pushing it onto the outStack that item ends up on the top of the outStack. Furthermore, all of the things on the outStack are now in the correct order to be popped when dequeueing. (Pushing a number of items onto a stack and then popping them off reverses their order.)

Create a class StacksQueue that implements the CS10Queue interface using two stacks. You may use the ArrayListStack that implements CS10Stack, the Java Stack class, or the Java Deque class (as long as you use only the addFirst, removeFirst, peekFirst, and isEmpty operations from the Deque). Methods dequeue and front should return null if called on an empty queue.

Efficiency of this Implementation

The enqueue and isEmpty operations require Θ(1) time. But what about dequeue and front?

Note that if you have enqueued n things and then do a dequeue, for that single dequeue you must do n pops from the inStack and n pushes onto the outStack, followed by a single pop from the outStack. Thus a single dequeue can take Θ(n) time. However, each item that is enqueued and later dequeued will be pushed once on the inStack and once on the outStack and popped once from the inStack and once from the outStack, so there will be a total of 2n pushes and 2n pops when doing some interleaving of n enqueues and n dequeues. This is a total of Θ(n) operations, and the amortized time for dequeue is Θ(1).

Testing

Test your code on the following main method (which you should include in StacksQueue.java):

/** * A testing program */ public static void main (String [] args) { CS10Queue<String> q = new StacksQueue<String>(); System.out.println("Is it empty? : " + q.isEmpty()); q.enqueue("cat"); q.enqueue("dog"); q.enqueue("bee"); System.out.println("Is it empty? : " + q.isEmpty()); System.out.println("Front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Is it empty? : " + q.isEmpty()); q.enqueue("eagle"); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Is it empty? : " + q.isEmpty()); System.out.println("dequeue of empty stack: " + q.dequeue()); q.enqueue("bear"); q.enqueue("beaver"); System.out.println("front is: " + q.dequeue()); q.enqueue("cat"); q.enqueue("dog"); q.enqueue("sheep"); q.enqueue("cow"); q.enqueue("eagle"); q.enqueue("bee"); q.enqueue("lion"); q.enqueue("tiger"); q.enqueue("zebra"); q.enqueue("ant"); System.out.println("Bigger example:"); System.out.println("front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Next front is: " + q.dequeue()); System.out.println("Is it empty? : " + q.isEmpty()); System.out.println("Next front is: " + q.dequeue()); }

Submission

Submit via Blackboard the zip file of a folder that contains (1) all java files, including the interface files, that are needed to run your program, and (2) the output from the test run.