==============================================================================
     CSC 263                 Tutorial 6              Winter 2019
==============================================================================

In this tutorial, we explore a well-known trick that uses two Stacks S1 and S2
to simulate the operations of a Queue Q. Consider the following implementations
of Enqueue and Dequeue.


def Enqueue(Q, x):
    if Size(S1) >= 12 and IsEmpty(S2):
        while not IsEmpty(S1): 
            Push(S2, Pop(S1))
    Push(S1, x)
    return


def Dequeue(Q):
    if IsEmpty(S2):
        if IsEmpty(S1):
            error "Dequeuing from an empty queue!"
        else:
            while not IsEmpty(S1):
                Push(S2, Pop(S1))
    return Pop(S2)


For your analysis, assume that each Push operation takes 2 units of time, and
each Pop operation takes 3 units of time. Each IsEmpty or Size operation takes
0 units of time. The time taken by any other pseudo-code operation is ignored.

(a) First, convince yourself and your partners that this is a correct
implementation of the Queue ADT. Trace some examples.

(b) Consider the sequence of operations that consists of 50 Enqueue operations
followed by 50 Dequeue operations. Use the aggregate method to compute the
amortized cost per operation for this sequence.

(c) Now consider any sequence of m Enqueue and Dequeue operations. Use the
accounting method to derive an upper-bound on the amortized cost per
operation.