Amortize cost analyse

[Etchira]

Hi,

I'm really stuck with this analyse of amortize cost exercise :
---------------
Show how to implement a queue with two stacks such that both Enqueue and Dequeue
takes amortized time
O(1)

Can you help me please?

Thanks

[weaknessforcats]

A stack is a queue. Particularly, it is a LIFO (last-in-first-out) queue.

You PUSH onto the top of the stack. This is the enqueue.

You POP from the top of the stack. This is the dequeue.

You PEEK to view the top of the stack, leaving the element there.

So if you want to calculate A+B you use two stacks. An operand stack for the values A and B and an operator stack for the +.

1) push A onto the operand stack
2) push + onto the operator stack
3) push B onto the operand stack
Then:
4) pop the + from the operator stack.
5) Since + needs two operands, pop two values from the operand stack.
6) add the values
7) push the sum onto the operand stack.
8) at this point the operator stack is empty and the sum of A and B is the top entry in the operand stack.

You can use this scheme with Polish notation also.

[jitsceait]

http://algorithmsandme.blogspot.in/2...ng-stacks.html