Dynamic table and implement queue using 2 stacks, the amortized cost When you ar
ID: 3545674 • Letter: D
Question
Dynamic table and implement queue using 2 stacks, the amortized cost
When you are using Vector in STL, you don't have to worry about the size of the vector. That is because the "dynamic table" technique is used; whenever you need one more space in the vector and there are no more spaces, a new double size vector is allocated, old items are copied to the new vector, and the old space is deleted.
Implementing a queue by using 2 stacks, enqueue and dequeue. Dequeue operation, similar to the copying operation in dynamic table, could take a long time. But the "amortized cost" for each operation, i.e., inserting item into dynamic table, and enqueue, dequeue in Queue operation, take constant amount of average time.
How to show/proof the amortized cost is constant?
PS. Don't care about deletion.
Explanation / Answer
The queue could be implemented using 2 stacks in the following way.
Say, you have two stacks, Stack A and Stack B. Keep the stack A for enqueue and B for dequeue.
While you want to enqueue, Push the elements onto stack A.
When you want to dequeue, pop the elements from stack A and push them to stack B. Now, popping the elements from stack B is your dequeue function. Any new element can be then enqueued(that is stacked) to stack A. Later for dequeue, you can again transfer the elements from A to B when necessary.
In short words, as a pseudo code, what happens here is,
enQueue(q, x)
1) Push x to stackA (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stackB is empty
While stackB is not empty, push everything from stackA to stackB.
3) Pop the element from stack2 and return it.
Now, talking about the amortised cost, note that we are inserting the element only once, that is in stack A. Thus the cost would be O[1].
But for any element when we want to dequeue, we are first pushing it to another stack (stack B) then we are popping it out. This happens for all the elements.
Here, the cost would be
1. moving from stack A to stack B.
2. Popping from stack B.
Thus the amortised cost comes to be O[2], that is two units of computaion per element.
Thus, as we found out, using two stacks for a queue, the amortised cost are O[1] for enqueue and O[2] for dequeue, which are constants.
Hope, this answers your question. If you have any doubt, leave a comment.
Cheers!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.