SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Queue Using Two Stacks Visualizer

New values go on the in stack. To dequeue, take from the out stack; if it is empty, pour the whole in stack into it first. Pouring reverses the order, so the oldest value ends up on top.

Start the Queue Using Two Stacks simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(1)*
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Two stacks, drawn bottom to top: in takes new values, out hands them back.
  2. enqueue(1): push it on in.
  3. enqueue(2): push it on in.
  4. enqueue(3): push it on in.
  5. out is empty, so pour in into out. This reverses the order.
  6. Move 3 from in to out.
  7. Move 2 from in to out.
  8. Move 1 from in to out.
  9. dequeue() pops 1 from out: the oldest value still in the queue.
  10. enqueue(4): push it on in.
  11. dequeue() pops 2 from out: the oldest value still in the queue.
  12. dequeue() pops 3 from out: the oldest value still in the queue.
  13. enqueue(5): push it on in.
  14. out is empty, so pour in into out. This reverses the order.
  15. Move 5 from in to out.
  16. Move 4 from in to out.
  17. dequeue() pops 4 from out: the oldest value still in the queue.
  18. Done. Values came out in the order they went in: 1, 2, 3, 4. 5 moves in total.

Try it with your own input →

Queue using two stacks in Java, Python, C++, C and JavaScript

class MyQueue {
  Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
  void push(int x) { in.push(x); }
  int pop() {
    if (out.isEmpty())
      while (!in.isEmpty()) out.push(in.pop());
    return out.pop();
  }
}
class MyQueue:
    def __init__(self):
        self.inp, self.out = [], []
    def push(self, x):
        self.inp.append(x)
    def pop(self):
        if not self.out:
            while self.inp:
                self.out.append(self.inp.pop())
        return self.out.pop()
class MyQueue {
  stack<int> in, out;
public:
  void push(int x) { in.push(x); }
  int pop() {
    if (out.empty())
      while (!in.empty()) { out.push(in.top()); in.pop(); }
    int x = out.top(); out.pop();
    return x;
  }
};
#define CAP 1000
typedef struct {
  int in[CAP], out[CAP], nIn, nOut;
} MyQueue;

void push(MyQueue* q, int x) { q->in[q->nIn++] = x; }
int pop(MyQueue* q) {
  if (q->nOut == 0)
    while (q->nIn > 0) q->out[q->nOut++] = q->in[--q->nIn];
  return q->out[--q->nOut];
}
class MyQueue {
  in = []; out = [];
  push(x) { this.in.push(x); }
  pop() {
    if (this.out.length === 0)
      while (this.in.length > 0) this.out.push(this.in.pop());
    return this.out.pop();
  }
}

In an interview

LeetCode 232, Implement Queue using Stacks: first in, first out, using only push and pop.

One dequeue can cost O(n), but every value is moved at most once, so the average (amortised) cost is O(1). Only pour when out is empty, or the order breaks.

More lists, stacks & queues