algorithm - Implementing queue using stack -

this question homework:

implement fifo queue using 2 stacks.

the total running time of enqueue , dequeue functions should o(n) in worst case scenario. also, analyze running time of algorithm.

what did:

void enqueue(t *value) { s1.push(value); }  t *dequeue() {     if (s2.size > 0)         return s2.pop();     else if (s1.size > 0)     {         (int = 0; < s1.size; i++)             s2.push(s1.pop());          return s2.pop();     }     else return null; } 

analysis of algorithm:

running time of 1 enqueue theta(1). total running time of enqueue functions n * theta(1) = theta(n).

running time of dequeue in worst case scenario theta(n) (when call after last enqueue, i.e. when items inserted). in other cases running time theta(1).

so, total running time is: o(n) + o(n) + n * o(1) = 3 * o(n) = o(n)

is correct?

so, total running time is: o(n) + o(n) + n * o(1) = 3 * o(n) = o(n)

you're in right direction, don't analyze "total running time", split amortized average, worst case, , best case - , analyze each operation.

in algorithm, easy see that:

• enqueue() runs in theta(1) cases.
• dequeue() runs in theta(n) worst case , theta(1) best case.

noe, tricky part - need analyzed dequeue() amortised analysis.

first, note before each theta(n) (worst case), dequeue() must have emptied list, , inserted n elements.
this means, in order worst case happen, must have done @ least n enqueue() operations, each theta(1).

this gives amortised time of:

t(n) = (n*const1      +    const2*n)             /(n+1)           ^                 ^                      ^      n enqueues      1 "espansive" dequeue        #operations 

it easy see t(n) in theta(1), giving theta(1) amortized time complexity.

---

tl;dr:

enqueue: theta(1) cases
dequeue: theta(1) amortized, theta(n) worst case