This section extends the existing two-stack queue lesson, which already proves FIFO and the basic amortized bound. It adds an internal transfer invariant, front observers, implementation details and backend-cost qualifications.
A stack removes its newest element, while a queue must remove its oldest waiting element. Two stacks can implement a queue because transferring a whole stack to another reverses its order. The difficult part is not the reversal itself: it is knowing when a reversal preserves the order of old and newly arriving elements.
This implementation also gives a small but complete example of amortized analysis. One queue operation may transfer many elements, yet a long sequence of operations needs only linear total stack work. We will prove both claims, including the sometimes surprising fact that inspecting the front can reorganize the representation without changing the abstract queue.
Give the two stacks an exact sequence interpretation
Definition 2.3.1
(Incoming, outgoing and the abstract FIFO sequence)
Let be the incoming stack and the outgoing stack. Write each stack as a sequence from bottom to top, with its top at the right. The queue sequence, from oldest to newest, is
where denotes sequence concatenation. Both stacks are initially empty. Each enqueued occurrence appears in exactly one of them, and their combined length is the queue length.
enqueue(x) appends to the queue. On a nonempty queue, front() returns its oldest value without removing it, while dequeue() returns and removes that value. Both operations report an error on an empty queue.
The order convention matters. If and , the queue is , not . The outgoing top is the oldest waiting element; the incoming bottom is the oldest of the arrivals that have not yet been transferred.
Concept lensStructural
One sequence with a movable cut
Write the queue as and let . Then holds with on top, and holds with on top. Enqueue lengthens the sequence at the right and leaves the cut alone; dequeue deletes and lowers ; a transfer moves the cut to the right end, . The potential used later is .
Common mistake
(Reading the outgoing stack from the wrong end)
With and , writing the queue as treats the outgoing bottom as the oldest element, and a dequeue would then wrongly return 7. The outgoing top is the oldest: the queue is , and a dequeue returns 4.
Transfer only when the outgoing stack is empty
Enqueue always pushes onto . Before reading or removing the front, use this rule: if is empty, repeatedly pop and push that value onto until is empty. If is already nonempty, do not transfer anything.
Theorem 2.3.2
(Two stacks implement a FIFO queue)
Start from two empty stacks, enqueue by pushing onto , and transfer only when is empty before a front or dequeue. After every public operation, is the sequence of the abstract queue: enqueue appends, front returns the oldest element, and dequeue removes and returns it.
Proof
(Each public operation preserves the FIFO sequence)
Enqueue changes to , so the represented queue becomes , exactly the required append.
If is nonempty, its top is the first element of and therefore of . Reading that top returns the front; popping it removes precisely the first queue element.
If is empty and the old incoming sequence is , transferring it completely gives and . The new abstract sequence is , equal to the old queue. We may then read or remove the outgoing top by the previous argument. Thus enqueue, front and dequeue all implement their stated sequence contracts.
Counterexample mode
Pouring new arrivals onto a nonempty outgoing stack breaks FIFO
Start with and , representing queue . If we transfer 9 onto the nonempty outgoing stack, it becomes with . Its represented queue is now .
The newest item has jumped ahead of older waiting items. The condition “outgoing is empty” is a correctness condition, not merely a performance optimization.
A transfer has its own loop invariant
The simple public abstraction need not describe the old queue during a partially completed reversal. We need a separate loop invariant rather than reading an answer too early.
Lemma 2.3.3
(The transfer loop invariant)
Let be the incoming sequence before a transfer, with empty. At every iteration of the transfer loop, ; the loop ends after iterations with and .
Proof
(The old incoming sequence splits into untransferred and transferred parts)
Let the incoming sequence before a transfer be , with outgoing initially empty. During the loop, split , where and . Equivalently,
Initially and . Popping the last element of and pushing it onto extends the transferred suffix by that element at its front, preserving the split. Each iteration decreases by one, so the loop terminates.
At termination , so and the public queue interpretation is restored. The code completes this internal transfer before returning a front value or completing a dequeue.
Counterexample mode
The first element moved is the newest, not the front
For and , moving only one element gives , . Reading the outgoing top at this intermediate point would return 9, although the queue's front is 4.
The loop invariant still remembers the old sequence as . It does not justify using the public formula as the old queue until the transfer finishes. An internal intermediate representation must not be mistaken for a completed operation.
Trace arrivals while older elements are still waiting
Worked example 2.3.4
(Two transfers serve several front and dequeue operations)
Every stack in the table is written bottom to top. A dash in the return column means that an enqueue returns no queue element.
| Operation | Incoming I afterwards | Outgoing O afterwards | Return | Abstract queue afterwards |
|---|---|---|---|---|
| Enqueue 4 | — | |||
| Enqueue 7 | — | |||
| Front | ||||
| Enqueue 9 | — | |||
| Dequeue | ||||
| Enqueue 2 | — | |||
| Dequeue | ||||
| Front | ||||
| Dequeue |
The first front reverses two items; the second reverses the two later arrivals. Neither front call changes the abstract queue sequence. Arrivals 9 and 2 wait in the incoming stack until the older outgoing group has been consumed.
Worked example 2.3.5
(One expensive front call, charged exactly)
Enqueue into an empty queue, so , and . Calling front pops , , from and pushes them onto , giving and , then reads the top, which is . The counted work is pops, pushes and read, that is with . The potential falls from to , so the amortized charge is . A second front call right afterwards costs and changes no potential.
Worked example 2.3.6
(An empty queue and the value None)
On a new queue, front() calls _prepare_front, which does nothing because the incoming list is empty. The outgoing list is also empty, so IndexError is raised, no stack has changed, and the work is constant. After enqueue(None), front() transfers the single item, so _outgoing == [None]. The test not self._outgoing is false for this nonempty list, so the call returns None and the queue length is still . The exception, not the returned value, distinguishes an empty queue from a stored None.
The front is therefore an observer of the abstract queue, but need not leave its internal representation unchanged. Once an outgoing group exists, repeated front calls just inspect the same top. A client using the queue operations observes the same values and length, irrespective of which internal stack currently holds them.
Charge work to each occurrence's one-way journey
For a precise first cost model, charge one unit for each stack push, stack pop or top read. A dequeue uses one pop that returns the value, not a separate top read and pop. Other control and length checks add constant work per loop iteration or public call and do not change the asymptotic conclusion. Assume successful storage operations.
An enqueued occurrence is pushed onto once. It may later be popped from and pushed onto once, and may eventually be popped from once. It never travels back to . Distinct occurrences are counted separately, even when their values are equal.
If an empty-start sequence has enqueues, successful dequeues and successful front calls, its counted stack work is at most
The first pays for incoming pushes, at most pays for transfers, and pays for outgoing pops and reads. This is an aggregate argument: some enqueued items may remain in or , so the bound need not be attained.
Prove the same bound with a potential function
Define the state potential . It is nonnegative and is zero in the initial empty state. Define an operation's amortized charge as its counted actual work plus the change in potential.
| Successful operation | Actual work c | Potential change | Amortized charge |
|---|---|---|---|
| Enqueue | |||
| Front or dequeue, outgoing nonempty | |||
| Front or dequeue, transfer k incoming items first |
Here in the transfer row. Each arrival stores enough potential to pay for its eventual pop from and push onto . The implementation stores no such balance: potential is a mathematical accounting tool.
Theorem 2.3.7
(Linear total work from an empty start)
Starting from the empty state, any legal sequence with enqueues, successful dequeues and successful front calls has total counted work at most .
Proof
(Potential changes telescope over any legal sequence)
For states indexed , let be actual counted work and . Summing gives
With an empty start, and , so actual total work is at most the total amortized charge . If analysis begins with items already in the incoming stack, retain the initial-potential term rather than silently using the empty-start bound.
Proof X-ray
Why the potential is twice the incoming size
The coefficient in is forced by the transfer row. Each of the transferred items is popped once and pushed once, so the transfer costs about and must be paid by a drop of potential of about . With the drop would be only , and the amortized charge of a transfer would be , which is not constant. The same coefficient makes each enqueue deposit two units, which gives its charge . Nonnegativity of and are what turn the telescoped identity into an upper bound on the actual work. The proof counts abstract stack primitives only, so it says nothing about the resizing of the backing arrays.
In the worked trace there are four incoming pushes, eight transfer primitives, three outgoing pops and two top reads: total 17. The bound gives , and the final incoming stack is empty, so no potential remains unused.
One operation can still be expensive. Enqueue items and then call front: that call alone performs counted primitives, or work. Its amortized charge is one because it releases potential accumulated by the previous enqueues. Amortized constant time describes a total-sequence guarantee, not a constant latency promise for every call and not an average over random inputs.
Common mistake
(Reading amortized constant as constant for every call)
After enqueues, a single front call performs counted primitives. Its amortized charge is only because the enqueues have already deposited units of potential. The whole sequence of enqueues and one front costs primitives, which is linear, but the one call is not constant-time. An application that needs a bound on every call needs a different design.
Length and emptiness queries, and rejected front/dequeue calls on an empty queue, add only constant work per call and leave the potential unchanged. They can be included separately when counting the total number of public calls.
A direct implementation using two end-access stacks
The Python lists below express stacks with their tops at the right. Only the public queue operations belong to the client interface; directly editing the internal lists would invalidate the proof. Empty front/dequeue calls raise IndexError and leave the abstract queue empty. Values such as None are ordinary elements, so an exception distinguishes an empty queue from a successful call returning None.
class TwoStackQueue:
def __init__(self):
self._incoming = []
self._outgoing = []
def __len__(self):
return len(self._incoming) + len(self._outgoing)
def is_empty(self):
return not self._incoming and not self._outgoing
def enqueue(self, value):
self._incoming.append(value)
def _prepare_front(self):
if not self._outgoing:
while self._incoming:
self._outgoing.append(self._incoming.pop())
def front(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("front of an empty queue")
return self._outgoing[-1]
def dequeue(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("dequeue from an empty queue")
return self._outgoing.pop()
For example, enqueueing 4 and 7, calling front(), enqueueing 9, and then calling dequeue() three times returns 4 from the front call and then from removals. Length is the sum of stack lengths; it does not require transferring elements.
The exact potential table counts abstract stack primitives. It does not prove that each machine-level list operation is worst-case constant-time: a dynamic-array stack may resize. To obtain a runtime bound for that backend, combine the linear number of primitive calls with the stacks' own amortized resizing analysis. If those primitive calls have total stack cost, the queue still has linear total runtime, up to constant per-call overhead. The queue potential alone is not a separate proof of the arrays' resizing costs.
There are live stored occurrences, split between the two stacks. Additional backing-array capacity depends on the stack implementation's growth/shrink policy; it is distinct from the logical element count. A linked-stack implementation has different allocation behavior but the same FIFO and one-way-transfer reasoning. A circular-array or linked queue can avoid this particular bulk reversal and has its own representation and latency analysis.
Exercises and worked solutions
Quick check
(1. Read the two stacks in the correct directions)
Incoming is and outgoing is , both bottom to top. What is the abstract queue? What do one dequeue and then one front return, and how are the stacks arranged afterwards?
Solution · Solution 1
The queue is . Dequeue returns 7 and leaves outgoing empty. Front transfers both incoming items, giving incoming and outgoing , and returns 9. The queue after the front call remains .
Quick check
(2. Diagnose an unnecessary transfer)
For incoming and outgoing , why must front read the current outgoing top instead of transferring the new item first? Give the old and incorrectly changed abstract sequences.
Solution · Solution 2
The old sequence is , so the front is 4. Transferring 9 onto outgoing gives there and represents , placing the newest arrival first. Transfer only when outgoing is empty.
Quick check
(3. Use the internal transfer invariant rather than an early answer)
Start with incoming and outgoing empty. After moving only 9, how does the loop invariant recover the old queue? Why is reading the outgoing top then invalid as the completed front result?
Solution · Solution 3
The loop interpretation is . The outgoing top is 9, but the correct front is 4. Only after completing the reversal does the public interpretation again represent the old queue.
Quick check
(4. Compute the charge of a five-item transfer)
Outgoing is empty and incoming contains five items. A successful front call transfers them. Give actual counted work, potential before and after, and amortized charge.
Solution · Solution 4
Five incoming pops and five outgoing pushes, followed by one top read, cost 11. Potential drops from ten to zero, so the amortized charge is . The actual call still performs all eleven primitives.
Quick check
(5. Keep the initial state in a suffix analysis)
An analysis begins after k items have already been enqueued into incoming, with outgoing empty. It counts only the next front call. Why would applying the empty-start bound to that one-call suffix be wrong?
Solution · Solution 5
The suffix costs , not just one. It begins with initial potential , so telescoping gives actual cost equal to the amortized charge one plus that initial potential: . The earlier enqueues accumulated the credit; omitting them from the operation sequence does not make their stored work disappear.
Quick check
(6. Separate occurrence accounting from stack resizing)
Does enqueueing the same value ten times count as one item journey or ten? Does the bound on abstract stack primitives by itself prove every Python list append has constant worst-case runtime?
Solution · Solution 6
There are ten separate enqueued occurrences, each with its own one-way journey and two units of transfer potential. Equal values do not merge queue items. The primitive count does not prove worst-case list-operation time; a dynamic-array backend needs its own resizing analysis. Combining its total-cost bound with the queue's linear primitive count gives the corresponding amortized runtime guarantee.