PYTHON QUESTION Suppose you are given a (strange) computer that can only perform

Question

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?

Explanation / Answer

We know that queue follows first in first out order.So we can achieve this with two stacks(stk1, stk2).Have a look at algorithm as shown in image.

Algorithm:

1. enqueue(i) operation of the queue
Push i to the stk1
2.dequeue(i) operation of queue
If both the stacks are empty,
it means no elements left in the queue.

If stk2 is empty
Push all the elements to stk2 from stk1
return the top element of stk2.

Code:

Output:
5 inserted!
4 inserted!
3 inserted!
2 inserted!
1 inserted!
dequeued element 5
dequeued element 4
dequeued element 3
dequeued element 2
dequeued element 1
dequeued element None

2. Worst case of dequeue operation is when stk1 is filled with n elements and we want dequeue operation, So we have to push all the elements from stk1 to stk2 and the pop the top element.
This process takes O(n) time.

3. Operation n enqueues followed by n dequeues
n sequential dequeues will require x pop operation as first deque operation we have to pop x elements of stack1.This x is equal to the number of elements in stack1 at the time of first dequeue request. This is the worst case, so we have to perform x pop from stack1 the n pop for each dequeue operation.

So total pop operation = x + n
As enqueue operation requires no pop operation.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.