Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

Algorithm

Basic Implementation

basic.c 
#include <stdio.h>

void print_values(int values[], int count) {
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(" -> ");
        printf("%d", values[i]);
    }
    printf("\n");
}

int main(void) {
    int in_stack[3], out_stack[3], removed[3];
    int in_top = 0, out_top = 0, count = 0;
    int values[] = {10, 20, 30};
    for (int i = 0; i < 3; i++) in_stack[in_top++] = values[i];
    while (in_top > 0) out_stack[out_top++] = in_stack[--in_top];
    while (out_top > 0) removed[count++] = out_stack[--out_top];
    print_values(removed, count);
    return 0;
}

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • Keep the explicit stack/queue operations. Library shortcuts that only produce the final list hide the data-structure behavior this lesson is meant to replay.
  • The final output uses a deterministic a -> b -> c format for cross-language comparison.
input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.