Make a first in, first out queue using nothing but two last in, first out stacks.
What to build
A queue made from two array stacks, which counts how many items it moves between them.
Requirements
enqueue xpushesxonto the first stack.dequeuepops from the second stack. If the second stack is empty, first move every item from the first stack to the second, one at a time.dequeueprints the item, oremptyif both stacks are empty.- After all the commands, print
moves M, whereMis the number of items moved from the first stack to the second.
Input
The first line has q. Each of the next q lines has one command.
Output
One line for each dequeue, then the moves line.
Constraints
1 ≤ q ≤ 1000.
Example
Input:
6
enqueue 1
enqueue 2
dequeue
enqueue 3
dequeue
dequeue
Output:
1
2
3
moves 3
Why it works
Pouring one stack into another reverses the order, so the oldest item comes out first. Each item is moved at most once, so n operations cost O(n) in total, even though one dequeue can be slow.
Examples
Example 1 · Input
6 enqueue 1 enqueue 2 dequeue enqueue 3 dequeue dequeue
Expected output
1 2 3 moves 3
Example 2 · Input
2 dequeue enqueue 4
Expected output
empty moves 0
Hints
Hint 1
Push every new item onto the first stack.
Hint 2
To dequeue, look at the second stack. Only if it is empty, pop everything from the first stack and push it onto the second.
Hint 3
Moving the items reverses them, so the oldest item ends up on top of the second stack.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
int inbox[1000], outbox[1000];
int in_top = -1, out_top = -1;
int main(void) {
int q, moves = 0;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "enqueue") == 0) {
int x;
scanf("%d", &x);
inbox[++in_top] = x;
} else {
if (out_top == -1) {
while (in_top >= 0) {
outbox[++out_top] = inbox[in_top--];
moves++;
}
}
if (out_top == -1) printf("empty\n");
else printf("%d\n", outbox[out_top--]);
}
}
printf("moves %d\n", moves);
return 0;
}