Algorithms homework related to exam 3
Hw7
1. Recall from your data structures course that a queue supports two operations, enqueue and dequeue, and a stack supports two operations, push and pop.
(a) Show how to simulate a queue using two stacks.
(b) What is the worst-case time complexity for the two queue operations, in your simulated queue from part (a)?
(c) What is the amortized time complexity of your queue operations, assuming you start with an empty structure?
If you didn’t solve this problem and want to keep working on it, here’s a hint:
Draw the stacks back-to-back, horizontally, with the open ends at the extreme left and right. The queue process will move elements from left to right in general; into one stack, then transfer to the other, then out of the other. Maintain the invariant that at all times the left-to-right (or right-to-left) order of items represents queue order.
Answer:
Visualize the stacks set up back-to-back. For instance, let them be drawn horizontally, with one stack L open to the left, and the other stack R open to the right. Let R handle enqueuing, and let L handle dequeuing. If it weren’t for the “closed” ends of the stacks, items would enter on the right and emerge on the left. A problem only occurs when L is empty and we need to dequeue. Suppose some set of items has been enqueued in R, and that L is empty. We can incrementally pop everything and push into L, which sets up the correct order for these items to be dequeued whenever necessary. In other words, instead of the standard enqueue-dequeue phases when using a regular queue, items go through an enqueue-transition-dequeue process with two stacks. This transition phase has to be charged to either pushing or popping. Notice that we cannot simply push a new item into R and send it over to L immediately, if L is non-empty. This would violate the queue order. So, one way or another, either pushing or popping will have a worst-case time of O(n).
Now we will see how to get constant amortized time complexity per operation. While L is not empty, just enqueue and dequeue in constant time, as required. As soon as L becomes empty, transfer everything from R over to L, using a pop and a push for each element. This may cost O(n) time, but we can also count it as O(1) per item moved. Every item will be involved in a transition precisely once. When we complete a transition, R is empty, which is great; it is ready to accept new items. On the other side, L is now ready to go through several constant-time dequeues. So the higher the cost of any particular transition, the more we will wait until another transition occurs. In other words, such a transition will occur rarely.
You can use the accounting method to charge 3 units of time for every enqueue; 1 of those units will pay for pushing into R, and the other two get stored along with the element in R. Eventually they will pay for its eventual transfer over to L, whenever that happens. Dequeueing (popping) from R just gets charged 1 unit. Our maximum amortized cost per operation is 3.
For the potential method, let equal twice the number of items in R. Thus is always non- negative, and it starts out as zero. Whenever we enqueue (push into R), = 2, so the amortized cost is 3. When we dequeue, the pop from L generates = 0, so the amortized cost is just 1 if L was not empty. But if L was empty, the transition of k items from R to L creates = 2k, which perfectly o↵sets the actual transition cost. Thus the contribution of this expensive step to the amortized cost is zero. Our maximum amortized cost per operation is 3.
2. An extended queue supports the two standard queue operations, but has one extra operation, called Q-pop, through which we access and remove the item that has been enqueued most recently. Show how to simulate an extended queue, using three stacks, such that the amortized cost of each extended queue operation is constant.
You can only use stack operations, and you should not duplicate (copy) elements.
Hint: Let the third stack be temporary. Before and after each operation it should be empty.
Answer:
Setup:
With two stacks we can’t handle all three operations of an extended queue, in sub-linear amortized time per operation. Alternating dequeue and Q-pop would require moving everything back and forth each time. But with a third stack, C, we can operate as follows.
Enqueueing is handled by pushing onto stack A. We will always handle Q-pop by standard pop from A. This means that we will make sure that if the data structure is non-empty, then the last-inserted element is at the top of A. So far, only A is needed and both operations take O(1) worst-case time, so things get interesting only if we need to dequeue.
Setup, part 2:
Now suppose that we need to dequeue, when B is empty and A contains k items. We pop half of the items from A and push them onto C. (I’ll assume we can divide by 2 here; this is just a detail). Then we pop the other half of A and push onto B. So far the cost is 2k. Finally we pop all of C and push back onto A. So the total cost is 3k. The e↵ect is that the bottom half of A is transferred to B, and the top half of A just slides down within A. This means that we can keep enqueuing in constant time (push A), we can dequeue in constant time (pop B), and we can Q-pop in constant time (pop A), until A or B become empty again. If B becomes empty and we need to dequeue, we transfer half of A over to B as just described. But if A becomes empty and we need to Q-pop, we transfer half of B over to A in a similar way. The cost is always 3 times the number of elements, so of course in the worst case this is linear.
Intuition for amortization:
The linear cost of the first transfer can be charged to the linear number of enqueues that must have preceded it. In general when A or B become empty, we use C as an intermediate to split the remaining elements among A and B again. The linear transfer cost in either scenario can always be “shared” by the linear number of O(1)-time operations that must have preceded. In other words, after every transfer we know that there will be a proportional number of operations until we need another transfer.
Accounting method, focusing on the first transfer:
Suppose that we pretend that every enqueue costs 7 units instead of 1. One unit pays for the push. We store 6 units with every item in A. (Why 6? That is based on the calculation that follows in this paragraph; we could have used a variable and figured this out algebraically.) If we Q-pop, we use 1 of the item’s 6 units and burn the other 5. Now suppose that A contains k items and we need to make a transfer to B, because we want to dequeue. We have calculated the total true cost of this transfer to be 3k. We are left with k/2 items in A, and we want them to maintain the invariant of each having 6 saved units. So essentially the k/2 items that are no longer in A must contribute their savings to pay for the entire transfer. They initially had 3k units tied to them, so that’s enough. But we will need to address the fact that the items in B do not have any credits.
Accounting method, more generally:
Now that we have the same number of items in A and B, we generalize our approach. Our invariant will be that the stack containing more elements holds all the savings, specifically 6 units per item in that stack. If both stacks contain the same number of units, arbitrarily use one to hold all the
savings. So for example if we want to Q-pop and B is about to have one more item than A, we move all of the savings from A to B, including the 6 units belonging to the item that is about to be Q-popped. Note that transferring units of savings is free, it is not an algorithmic operation, we are just analyzing. Now if we keep Q-popping while A has fewer items, we can burn the savings of what is Q-popped, because every item in B already has 6 units saved. In fact for every enqueue we don’t need to save anything (until A reaches the size of B, of course). Similarly for every dequeue that occurs while B is larger, we can just burn the savings. But if a dequeue will make B have one item less than A, we move all of the saved units back over to A.
The result of this generalized approach is that whenever one stack becomes empty, the other one has 6 units stored per item, and that is exactly enough to pay for the cost of a transfer, while maintaining the generalized invariant. Thus every operation has an amortized cost of at most 7.
Potential method, unsuccessfully:
First, consider what changes a lot when we have an expensive operation (i.e., a transfer). Clearly, one answer is the number of items in A (or B). But we need that change to be negative as well, when there is an expensive operation. If we use the number of items in A, this will change a lot but positively, after a transfer triggered by a Q-pop (i.e., A was empty beforehand). Similarly if we use the number of items in B, this will change a lot, positively, after a transfer triggered by a dequeue. This means we need to find something else that changes a lot.
Potential method, correctly:
For a transfer to be triggered, either A or B must have been empty. After the transfer, A and B hold the same number of items. So the absolute value of the di↵erence between the sizes of A and B changes a lot, and in fact negatively. Accordingly we will define = 3 · |A B|. The factor of 3 was determined by recalling that the true cost of a transfer is 3k if the non-empty stack contains k items. So i 1 = 3k, and i = 0, which means = 3k. Thus the amortized cost of any transfer is zero: our main objective is accomplished, that is, the expensive operation has a small amortized cost. Now we check that there are no undesired side-e↵ects: For any enqueue, dequeue or Q-pop, the true cost is 1, and = ±3, so the amortized cost is at most 4. The parity depends on the relative sizes of A and B. We conclude that the amortized cost of any operation is at most 4.
Back to accounting:
The potential method result seems better than what we got with the accounting method, but in fact the accounting strategy can be modified to get an amortized cost of at most 4 as well. The invariant can change as follows: suppose that one stack contains c more items than the other. Then that stack must store 3c units. That means that when we begin by enqueuing (push into A), we pretend that the cost is 4 instead of 1. The first transfer from A to B will use up all of our savings (specifically 3k, as described earlier). Then if we enqueue again we pretend that the cost is 4. If instead we Qpop, we pretend that the cost is 4 and we save 3 units in B instead of A, because B would now have one more item than A. Similarly if we were to dequeue when A and B hold the same number of items, we pretend that the cost of popping from B is 4, and save 3 units in A. Any time that we remove an item from the stack containing more items, we can burn 3 units to preserve our nice invariant. It is now clear that when one stack ends up empty, the other one has enough to pay for a transfer, so the amortized cost of the transfer is zero and we re- set the total savings to zero as well. In conclusion the highest amortized cost of every operation is 4.
Final note: This extended queue structure, which also has a stack operation, is called a Quack.