Implement a queue using two stacks.
/* uses the array stack from above */
typedef struct { astack_t in, out; } squeue_t;
bool sq_push(squeue_t *q, int v) { return as_push(&q->in, v); }
bool sq_pop(squeue_t *q, int *v)
{
if (q->out.top == 0) { /* refill only when out is empty */
int x;
while (as_pop(&q->in, &x)) as_push(&q->out, x);
}
return as_pop(&q->out, v);
}
Points: pushing everything from in to out reverses the order, so the oldest element ends up on top of out. Each element moves at most twice, so operations are amortised O(1) (a single pop can be O(n)).