A stack built from queues

Scenario

A job runner offers one tool for holding work: a first-in, first-out queue. A new feature needs the opposite: it must hand back the newest job first, like an undo history.

You must build that stack behaviour out of queues, and replay a list of commands against it. The tests check the answers, so a plain list would also pass. Use only queue operations, because that is the practice.

Your task

Write run_stack_commands(commands, values).

commands is a list of words: push, pop, top or empty. values[i] belongs to commands[i]. It is the number to push for a push, and it is ignored for the other commands.
push puts a number on the stack. pop removes the newest number. top reads the newest number without removing it. empty asks whether the stack is empty.
Return one answer for every pop, top and empty command, in order. For pop and top, the answer is the number, or -1 when the stack is empty. For empty, the answer is 1 when the stack is empty and 0 when it is not. A push gives no answer.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["push", "push", "top", "pop", "empty"], values = [1, 2, 0, 0, 0]
Output: [2, 2, 0]

Step	Command	Queue after (front is the stack's top)	Answer
1	`push 1`	`1`	none
2	`push 2`	`2` `1` (`2` joined at the back, then `1` rotated behind it)	none
3	`top`	`2` `1`	2
4	`pop`	`1`	2
5	`empty`	`1`	0

The newest number, 2, is on top. After it is popped, 1 remains, so the stack is not empty.

Example 2#

text2 lines

Input:  commands = ["pop", "empty"], values = [0, 0]
Output: [-1, 1]

Pop on an empty stack answers -1.

Example 3#

text2 lines

Input:  commands = ["push", "pop", "pop"], values = [9, 0, 0]
Output: [9, -1]

The second pop finds the stack empty.

Constraints

1 ≤ length of commands ≤ 5000
commands has the same length as values
each command is push, pop, top or empty
0 ≤ values[i] ≤ 10^6

What does n ≤ 5000 tell you?

With one queue, each push rotates the queue once round, which costs up to n steps. So n pushes cost up to n^2 / 2 steps. For 5,000 commands that is 12.5 million, which is fast enough.

That is why the limit is lower than in other problems: this design trades a slow push for an easy pop. You can also make pop slow and push fast. Either way, one of them costs O(n).

Scenario

A job runner offers one tool for holding work: a first-in, first-out queue. A new feature needs the opposite: it must hand back the newest job first, like an undo history.

Your task

Write run_stack_commands(commands, values).

commands is a list of words: push, pop, top or empty. values[i] belongs to commands[i]. It is the number to push for a push, and it is ignored for the other commands.
push puts a number on the stack. pop removes the newest number. top reads the newest number without removing it. empty asks whether the stack is empty.
Return one answer for every pop, top and empty command, in order. For pop and top, the answer is the number, or -1 when the stack is empty. For empty, the answer is 1 when the stack is empty and 0 when it is not. A push gives no answer.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["push", "push", "top", "pop", "empty"], values = [1, 2, 0, 0, 0]
Output: [2, 2, 0]

Step	Command	Queue after (front is the stack's top)	Answer
1	`push 1`	`1`	none
2	`push 2`	`2` `1` (`2` joined at the back, then `1` rotated behind it)	none
3	`top`	`2` `1`	2
4	`pop`	`1`	2
5	`empty`	`1`	0

The newest number, 2, is on top. After it is popped, 1 remains, so the stack is not empty.

Example 2#

text2 lines

Input:  commands = ["pop", "empty"], values = [0, 0]
Output: [-1, 1]

Pop on an empty stack answers -1.

Example 3#

text2 lines

Input:  commands = ["push", "pop", "pop"], values = [9, 0, 0]
Output: [9, -1]

The second pop finds the stack empty.

Constraints

1 ≤ length of commands ≤ 5000
commands has the same length as values
each command is push, pop, top or empty
0 ≤ values[i] ≤ 10^6

What does n ≤ 5000 tell you?

With one queue, each push rotates the queue once round, which costs up to n steps. So n pushes cost up to n^2 / 2 steps. For 5,000 commands that is 12.5 million, which is fast enough.

That is why the limit is lower than in other problems: this design trades a slow push for an easy pop. You can also make pop slow and push fast. Either way, one of them costs O(n).