If we use two queues data queue and working queue to implement a stacks by the...

Transcribed Image Text:

If we use two queues "data queue" and "working queue" to implement a stacks by the following way. Suppose that both queues have no size limit. s.push(item) 1. enQueue the item into the data queue. s.pop() 1. move all the items except the last one from the data queue to the working queue 2. deQueue from the data queue and return 3. now the names of the data queue and the working queue are swapped. That is, working queue -> data queue and data queue -> working queue Suppose that we would like to analyze the amortized costs using the accounting method. Assume there are k items in the stack before the i-th operation. If the i-th operation is a pop operation and we assign 2(k-1) amortized cost to it, then how much amortized cost for a push operation should be assigned? Justify your answer. If we use two queues "data queue" and "working queue" to implement a stacks by the following way. Suppose that both queues have no size limit. s.push(item) 1. enQueue the item into the data queue. s.pop() 1. move all the items except the last one from the data queue to the working queue 2. deQueue from the data queue and return 3. now the names of the data queue and the working queue are swapped. That is, working queue -> data queue and data queue -> working queue Suppose that we would like to analyze the amortized costs using the accounting method. Assume there are k items in the stack before the i-th operation. If the i-th operation is a pop operation and we assign 2(k-1) amortized cost to it, then how much amortized cost for a push operation should be assigned? Justify your answer.

Answer rating: 100% (QA)

For a pop operation you assign 2k1 amortized cost to it where k is the number of items in the stack ... View the full answer