Stacks and Queues

Queue from Two Stacks

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

Algorithm

The replay uses the same three values in every language, so this C DSA implementation can be compared directly with the rest of the DSA track.

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

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.