Consider a queue data structure, where the two operations of interest are enqueu
ID: 3570449 • Letter: C
Question
Consider a queue data structure, where the two operations of interest are enqueue (at the back of the queue) and dequeue (from the front of the queue). A queue is thus a FIFO (first in-first out) structure. Suppose we implement a queue by using two stacks, A and B, which support operations of push and pop, as follows: enqueue(x): push x onto stack A dequeue: if B is not empty return x = pop B if B is empty repeat until A is empty x=popA push x onto stack B return x = pop B a) This implementation seems to correctly emulate a queue. Illustrate (by drawing the two stacks) how it works for the following sequence of enqueue and dequeue operations: enqueue 5 enqueue 7 dequeue enqueue 3 enqueue 6 enqueue 9 dequeue dequeue dequeue dequeue b) The actual cost of a push or a pop operation is 1. What is the worst-case single operation possible after a sequence of n enqueue and dequeue operations, and what is its cost? c) Explain how a simplistic worst-case analysis would lead to the conclusion that this algorithm would be 0(n^2).Explanation / Answer
a>
STACK A -
STACK B -
enqueue 5
STACK A - 5,
STACK B -
enqueue 7
STACK A - 5, 7
STACK B -
dequeue
STACK A -
STACK B - 7,
5 is popped out
enqueue 3
STACK A - 3
STACK B - 7
enqueue 6
STACK A - 3, 6
STACK B - 7
enqueue 9
STACK A - 3, 6, 9
STACK B - 7
dequeue
STACK A - 3, 6, 9
STACK B -
7 popped
dequeue
STACK A -
STACK B - 9, 6
3 popped
dequeue
STACK A -
STACK B - 9
6 popped
dequeue
STACK A -
STACK B -
9 popped
__________________________________________________________
b> in worst case each element is pushed and popped twice for enqueue + dequeue
So, for n enqueue and dequeue operations max cost = 4n
__________________________________________________________
c> In normal case one would think that the nth element in worst case could take total 2n operations of push + 2n of pop. Hence total number of operations = 4n(n-1) = O(n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.