data-structures · intermediate · ~30 min
Amortised O(1) queue from two LIFO stacks — and ownership of the drain trick.
Implement a fixed-capacity int queue using two stacks internally:
typedef struct ts_queue ts_queue_t;
ts_queue_t *tsq_create(int capacity);
int tsq_enqueue(ts_queue_t *q, int v); /* 0 ok, -1 full */
int tsq_dequeue(ts_queue_t *q, int *out); /* 0 ok, -1 empty */
int tsq_size(ts_queue_t *q);
void tsq_destroy(ts_queue_t *q);
Internally, the queue has two stacks (in_stack and out_stack):
in_stack.out_stack. If out_stack is empty, drain in_stack into out_stack (reversing order — now the oldest item is on top), then pop.Total stored items must never exceed capacity. Both stacks share that budget.
tsq_create(3)
tsq_enqueue(q, 1) // [in: 1] [out: ]
tsq_enqueue(q, 2) // [in: 1, 2] [out: ]
tsq_enqueue(q, 3) // [in: 1, 2, 3] [out: ]
tsq_enqueue(q, 4) -> -1 // full
int v;
tsq_dequeue(q, &v) -> 0, v == 1 // drain triggered: out becomes [3, 2, 1], pop 1
tsq_dequeue(q, &v) -> 0, v == 2
tsq_enqueue(q, 5) -> 0 // [in: 5] [out: 3]
tsq_dequeue(q, &v) -> 0, v == 3
tsq_dequeue(q, &v) -> 0, v == 5
tsq_dequeue(q, &v) -> -1 // empty
The two-stack queue is a classic interview puzzle — and also a real engineering trick. Building a queue out of two stacks gives O(1) amortised enqueue/dequeue without circular-buffer wraparound.
Capacity + ops.
See API.
O(1) amortised enqueue/dequeue.
typedef struct ts_queue ts_queue_t;
ts_queue_t *tsq_create(int capacity);
int tsq_enqueue(ts_queue_t *q, int v);
int tsq_dequeue(ts_queue_t *q, int *out);
int tsq_size(ts_queue_t *q);
void tsq_destroy(ts_queue_t *q);
Draining in_stack to out_stack on every dequeue, not just when out_stack is empty — that breaks the amortisation. Forgetting to free both stack arrays in destroy.
Dequeue from empty; fill exactly to capacity; mix enqueues and dequeues.
O(1) amortised — every element is moved between stacks at most twice.
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.