A FIFO queue implemented with two stacks

Challenge

Build a FIFO queue whose internals are two LIFO stacks.

Task

Implement a fixed-capacity int queue backed internally by two stacks (in_stack and out_stack):

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);

Enqueue pushes onto in_stack. Dequeue pops from out_stack; if out_stack is empty, first drain all of in_stack into out_stack (which reverses the order so the oldest item ends up on top), then pop. The two stacks share one capacity budget: the total stored items must never exceed capacity.

Input

• capacity: the maximum number of items held at once (capacity > 0).
• v: the value to enqueue.
• out: where tsq_dequeue writes the removed value.

Output

• tsq_enqueue: 0 on success, -1 if the queue is full.
• tsq_dequeue: 0 on success (writing the oldest value through out), -1 if empty.
• tsq_size: the current number of items across both stacks.

Example

tsq_create(3)
enqueue 1, 2, 3          (queue full)
tsq_enqueue(4)   ->   -1
tsq_dequeue(&v)  ->   0, v == 1   (drain triggered, oldest comes out first)
tsq_dequeue(&v)  ->   0, v == 2
tsq_enqueue(5)   ->   0
tsq_dequeue(&v)  ->   0, v == 3
tsq_dequeue(&v)  ->   0, v == 5
tsq_dequeue(&v)  ->   -1          (empty)

Edge cases

• Dequeue from an empty queue returns -1.
• Filling exactly to capacity, then mixing enqueues and dequeues, must preserve FIFO order.

Rules

• O(1) amortised per operation: only drain in_stack into out_stack when out_stack is empty, never on every dequeue.

Why this matters

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.

Input format

capacity > 0; v to enqueue; out receives the dequeued value.

Output format

enqueue/dequeue return 0 on success or -1 (full/empty); dequeue writes through out; size returns the total count.

Constraints

O(1) amortised enqueue/dequeue. Both stacks share the capacity budget.

Starter code

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);

Common mistakes

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.

Edge cases to handle

Dequeue from empty; fill exactly to capacity; mix enqueues and dequeues.

Complexity

O(1) amortised — every element is moved between stacks at most twice.

Background lessons

• Stacks
• Queues (FIFO)

Up next

• Fixed-capacity circular queue
• Min-heap priority queue