DATA STRUCTURES PROGRAM • QUEUES & DEQUES
Implement a Queue Using Two Stacks
Learn how to implement a queue using two stacks using a clear C program.
PROBLEM UNDERSTANDING
Input and expected output
Sample input
No input required
Sample output
10 20 30
COMPLETE C PROGRAM
Complete C implementation
#include <stdio.h>
#include <stdlib.h>
struct Stack { int values[20]; int top; };
struct Queue { struct Stack input; struct Stack output; };
void push(struct Stack *stack, int value) { stack->values[++stack->top] = value; }
int pop(struct Stack *stack) { return stack->values[stack->top--]; }
void enqueue(struct Queue *queue, int value) { push(&queue->input, value); }
int dequeue(struct Queue *queue)
{
if (queue->output.top < 0)
while (queue->input.top >= 0) push(&queue->output, pop(&queue->input));
if (queue->output.top < 0) exit(EXIT_FAILURE);
return pop(&queue->output);
}
int main(void)
{
struct Queue queue = {{{0}, -1}, {{0}, -1}};
enqueue(&queue, 10); enqueue(&queue, 20); enqueue(&queue, 30);
int first = dequeue(&queue);
int second = dequeue(&queue);
int third = dequeue(&queue);
printf("%d %d %d\n", first, second, third);
return 0;
}CURRENT STEP
SELECTED LINE
EXPECTED OUTPUT FOR THE SAMPLE
10 20 30
Step 0 of 0
PROGRAM EXPLANATION
Algorithm and explanation
- Read the required input values.
- Transfer input-stack values only when the output stack is empty to expose FIFO order.
- Display the computed result.
Transfer input-stack values only when the output stack is empty to expose FIFO order.
EFFICIENCY
Time and space complexity
Time complexity
Amortized O(1)
Auxiliary space
O(n)
DEBUGGING CHECKLIST
Common mistakes
Check this
Use the correct format specifier for every variable.
Check this
Initialize variables before using their values.
Check this
Check braces, semicolons and input order carefully.
Try it yourself
Practice: Run the program with the sample input, predict its output, and then test one boundary case of your own.
