PYTHON QUESTION

Suppose you are given a (strange) computer that can only perform the following instructions (in addition to if and while):

S = create_stack() create stack makes a new stack S

i = S.pop() removes the top item from stack S and places it in variable i

S.push(i) makes item i the top item in stack S

Solve the following problems and justify your answers:

1. Show how you can use these operations to implement a queue (operations Q = create_queue(), enqueue(i), i = dequeue()) A picture might help to explain your answer Hint: take a look at the following image: (image from http://www.algoqueue.com/algoqueue/members/get_uploaded_image.load/149)

2. What's the worst case running time of your dequeue implementation?

3. Over a series of n enqueues followed by n dequeues, how many pop() operations does your implementation perform?