Implement Stack Using Queues

1. Define the problem

A queue only lets you add to the back and remove from the front. A stack does the opposite: the last value you put in is the first one that comes out . Build stack behaviour using nothing but a queue. The trick is that right after you add a new value to the back of the queue, you move every older value from the front around to the back, one by one. After that rotation the newest value is sitting at the front , so removing from the front of the queue removes the newest value, exactly like a stack. To keep the input simple to type, this function takes a list of operation names and a matching list of arguments, and returns the list of results. A push produces null because it has no result.

Constraints

1 ≤ x ≤ 9
At most 100 operations in total
pop and top are only called when the stack is not empty
Only standard queue operations are allowed: add to back, remove from front, read the front, read the size

Example

Inputoperations = ['push', 'push', 'top', 'pop', 'empty'], values = [[1], [2], [], [], []]

Output[null, null, 2, 2, false]

Explanation Push 1, then push 2. Because the queue was rotated after the second push, 2 is now at the front, so top returns 2 and pop removes 2. One value is left, so empty returns false.

2. Know the words first

In plain terms

Queue: A line of values where you only add at the back and only remove from the front, like people queuing at a till. Also called first in, first out.
Stack: A pile of values where you add and remove at the same end, like a stack of plates. The last one added is the first one taken off.
Front and back: The front is the end you remove from. The back is the end you add to. Every queue operation touches one of these two ends.
Rotate: Taking a value off the front of the queue and putting it straight back on the back. Doing this repeatedly spins the whole queue around without losing anything.

3. Visualize the solution

One row of cells is the queue buffer: slot 0 is the front, the last filled slot is the back

0—

1—

2—

3—

Statusinit

The queue starts empty, so every slot is a dash.

What happens in this step

queue = [] (all four slots empty)
front = nothing, back = nothing

The stack object holds exactly one queue and no other storage.
Everything a stack can do has to be built from adding at the back and removing at the front.

Step 1 of 8

Steps to visualize

The row below is the single queue. Empty slots show a dash.
Adding a value always puts it in the first free slot on the right, the back of the queue.
After each add, every older value is moved from the front around to the back, one at a time.
That rotation leaves the newest value at the front, so a normal front removal behaves like a stack pop.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the queue buffer: slot 0 is the front, the last filled slot is the back

0—

1—

2—

3—

Statusinit

The queue starts empty, so every slot is a dash.

What happens in this step

queue = [] (all four slots empty)
front = nothing, back = nothing

The stack object holds exactly one queue and no other storage.
Everything a stack can do has to be built from adding at the back and removing at the front.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function myStack(operations, values) {
  class Stack {
    constructor() {
      this.queue = [];
    }

    push(x) {
      this.queue.push(x);

      for (let i = 0; i < this.queue.length - 1; i++) {
        this.queue.push(this.queue.shift());
      }
    }

    pop() {
      return this.queue.shift();
    }

    top() {
      return this.queue[0];
    }

    empty() {
      return this.queue.length === 0;
    }
  }

  const stack = new Stack();
  const output = [];

  for (let i = 0; i < operations.length; i++) {
    const name = operations[i];
    const arg = values[i];

    if (name === 'push') {
      stack.push(arg[0]);
      output.push(null);
    } else if (name === 'pop') {
      output.push(stack.pop());
    } else if (name === 'top') {
      output.push(stack.top());
    } else {
      output.push(stack.empty());
    }
  }

  return output;
}

Time: O(n) per push, O(1) for pop, top and empty
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`operations = ['push', 'push', 'top', 'pop', 'empty'], values = [[1], [2], [], [], []]`	`[null, null, 2, 2, false]`	example from the docstring
`operations = ['empty'], values = [[]]`	`[true]`	nothing pushed yet, the smallest possible case
`operations = ['push', 'pop', 'empty'], values = [[5], [], []]`	`[null, 5, true]`	a single push and pop leaves the stack empty again
`operations = ['push', 'push', 'push', 'pop', 'pop', 'pop'], values = [[1], [2], [3], [], [], []]`	`[null, null, null, 3, 2, 1]`	values come out in the exact reverse of the order they went in
`operations = ['push', 'push', 'top', 'pop', 'top'], values = [[7], [7], [], [], []]`	`[null, null, 7, 7, 7]`	the same value pushed twice still pops the right number of times
`operations = ['push', 'push', 'pop', 'push', 'top'], values = [[1], [2], [], [3], []]`	`[null, null, 2, null, 3]`	pushing again after a pop still keeps the newest value on top

Implement Stack Using Queues