A queue can be built from two stacks: push arrivals onto one, and when the other is empty, pour everything across. One dequeue then costs n, and the whole sequence still costs at most three per arrival, because each element is pushed once, moved once and popped once. The expensive dequeue does not go away; it is paid for in advance.
Core ideas
The structure is four lines long and the analysis is the point. What is new is not the queue; it is that a bound over a sequence can be proved by charging each element in advance.
A stack touches one end and a queue touches two, and that is the entire reason both are constant-time on every operation while a general sequence is not. Neither can answer “what is at position 7” at all. Cheapness here is bought by refusing questions, which is the trade this whole course is about.
In EEEDDD the fourth operation costs 4 while the other five cost 1. The amortised bound does not say that dequeue was fast. It says the six operations together cost 9, which is 3 per arrival, and it is silent about which of them paid. A reader who cannot point at the expensive operation has read the bound as “always fast”.
Nothing in the code stores credit. The argument charges 3 for each enqueue, spends 1 on the push and banks 2; a dequeue spends from the bank. If the balance is never negative then the charges covered the real costs, so the real total is at most the charged total. The structure is unchanged; only the bookkeeping is new.
The material
The construction, the sequence where one dequeue costs four, and why the total is nevertheless bounded by three per arrival.
A stack supports push and pop at one end: the element removed is the one most recently added. A queue supports enqueue at one end and dequeue at the other: the element removed is the one least recently added. Neither supports access by position, and that restriction is what makes every operation on both of them cost 1 on an array or on a list.
Keep two stacks, IN and OUT. To enqueue, push onto IN. To dequeue: if OUT is empty, pop every element of IN and push it onto OUT, which reverses the order; then pop OUT. Because a stack reverses and two reversals restore, the element that comes off OUT is the oldest one still in the queue.
Charge one for each push, each pop and each move. Then an enqueue costs 1 always. A dequeue costs 1 when OUT is not empty, and k + 1 when OUT is empty and IN holds k elements — k moves and then the pop. So the worst single dequeue costs as much as the number of elements in the queue, and that is a genuine Θ(n) operation that a reader is entitled to be unhappy about.
The sequence E E E D D D costs 1, 1, 1, 4, 1, 1, adding to 9. The 4 is the first dequeue: three moves to pour IN into OUT, then one pop. The two dequeues after it cost 1 each, because OUT already holds their elements. One operation out of six cost four times what the others did, and the sequence total is 9 for three arrivals — exactly 3 each.
The technique is the accounting method of Discrete Mathematics’ “Recursion Trees and Amortised Analysis”, applied to a structure rather than to a loop. Give every enqueue a budget of 3: one for the push that happens now, one to pay for the move this element will make later, and one to pay for the pop that will finally remove it. Nothing else in the structure ever touches an element.
Over any sequence of operations containing m enqueues, the total cost of the two-stack queue is at most 3m.
Every element enters exactly once, is moved from IN to OUT at most once, and is popped from OUT at most once — once it has been moved it is never pushed back, because elements only ever travel from IN to OUT. So the three units charged at its enqueue cover every operation performed on it, for ever. Summing over the m elements gives 3m, and the real total cannot exceed the charged total.
Formally, let the credit after an operation be the charged total so far minus the real total so far. An enqueue is charged 3 and costs 1, so the credit rises by 2. A dequeue is charged 0 and costs k + 1 or 1, so the credit falls by that much.
The credit is never negative. Each element of IN carries 2 unspent units and each element of OUT carries 1, so before a dequeue that must pour k elements across, the bank holds at least 2k — and the dequeue costs k + 1 ≤ 2k for k ≥ 1. A dequeue on a non-empty OUT costs 1 and that element’s own unspent unit pays for it.
Since the credit is the charged total minus the real total and it is never negative, the real total is at most the charged total, which is 3m. The lab prints the credit balance after every step for exactly this reason: if it ever went negative the argument would be wrong, and watching it stay non-negative is watching the proof run.
□
On E E E D D D the lab reports a total of 9 and a bound of 9: the two agree, because every element that arrived was also served, so each one really did pay all three of its charges. On E D E D E D E D the total is 12 and the bound is 12, for the same reason. On the twelve-operation sequence E E D E E D E E D D D D the total is 18 with one dequeue costing 5, and the bound is again 18.
That the two keep coinciding is informative and it is not the theorem. A sequence that enqueues and never dequeues costs m against a bound of 3m, so the bound is loose there; the coincidence above happens when the queue is drained. What no sequence can do is establish the bound, because the bound quantifies over sequences and a run is one sequence. Type in a pattern that makes the expensive dequeue as expensive as you can — the cumulative line will approach the 3m line and, by the argument above, never cross it.
Interactive
Every element crosses once, so every element costs three
Method
Cost it first, then account for it. Doing the accounting first is how a bound gets asserted rather than proved.
Write IN and OUT side by side and update them. The state of the queue alone cannot tell you what the next dequeue costs, because the cost depends entirely on whether OUT happens to be empty.
Enqueue 1. Dequeue 1 if OUT is non-empty, k + 1 if it is empty and IN holds k. Keep a running total in its own column, and mark the operations that poured — those are the only interesting ones.
There is one in almost every sequence, and the point of the exercise is that you can name it and quote its cost. An amortised bound you cannot point at the expensive step of has been read as a worst case.
Add a credit column: +2 on each enqueue, minus the real cost on each dequeue. If it is ever negative the charge was too small. If it never is, the total is at most 3m, and you have proved something about the whole sequence rather than measured one.
Six operations, three arrivals. The first column is what the structure did; the last is the argument that bounds it.
Step 4 is the lesson. It cost 4 where every other step cost 1, and it did so because OUT was empty and IN held three elements: three moves and a pop. Nothing about the amortised bound makes that step cheap. What the bound says is that the six steps together cost 9, and they did.
The credit column is where the 3 comes from. Each enqueue banked 2 after paying for its own push, so 6 was in the bank when the expensive dequeue arrived; it spent 4 and left 2, and the two cheap dequeues spent the rest. The balance reached 0 and never went below, which is precisely the condition the theorem needs.
For a faded rehearsal, take E E D E E D E E D D D D. The supplied first move is that the dequeue at step 3 pours two elements and costs 3, and the dequeue at step 6 finds OUT non-empty and costs 1. Carry the table to the end, find the one dequeue that costs 5, and check that the total is 18 against a bound of 3 × 6. Then say, in one sentence, why running a second sequence would not make the bound any more established than running the first.
You should be able to run an enqueue/dequeue sequence keeping both stacks, quote the cost of the dequeue that pours, carry a credit column that never goes negative, and explain why 3 is the right charge per arrival in terms of what happens to one element over its whole life in the structure.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.