Implement Queue using Stacks

Easy
2037.

Implement Queue using Stacks

Implement Queue using Stacks is an easy coding problem on stack and queue, asked in Amazon, Microsoft, Bloomberg and Apple interviews.

Implement a first-in-first-out (FIFO) queue using only stacks. Write the class MyQueue:

  • MyQueue() creates an empty queue.
  • void push(int x) adds x to the back of the queue.
  • int pop() removes the element at the front of the queue and returns it.
  • int peek() returns the element at the front of the queue without removing it.
  • boolean empty() returns true if the queue is empty, false otherwise.

Your queue may use only the standard stack operations: push to the top, peek at or pop from the top, size, and is-empty. (In a language without a stack type, a list used only through those operations is fine.)

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for push.

Example 1

Input
["MyQueue","push","push","peek","pop","empty"] [[],[3],[8],[],[],[]]
Output
[null,null,null,3,3,false]
Explanation
3 arrives before 8, so it is at the front: peek and pop both give 3, and 8 is still queued.

Example 2

Input
["MyQueue","push","pop","push","push","peek","pop","pop","empty"] [[],[6],[],[2],[5],[],[],[],[]]
Output
[null,null,6,null,null,2,2,5,true]
Explanation
6 leaves at once; then 2 and 5 come out in arrival order and the queue is empty.

Constraints

  • 1 <= x <= 9
  • At most 100 calls are made to push, pop, peek and empty
  • Every call to pop and peek is made on a non-empty queue

Follow-up: Can you make every operation amortized O(1) — n operations in O(n) total time, even if one of them takes longer?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var MyQueue = function() {
    
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    
};

Sign in to run your own test cases

Sign in

Implement Queue using Stacks — Problem & Solution

Implement Queue using Stacks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Implement Queue using Stacks is an easy coding problem on stack and queue, asked in Amazon, Microsoft, Bloomberg and Apple interviews.

  • Difficulty: Easy
  • Topics: Stack, Queue
  • Asked at: Amazon, Microsoft, Bloomberg, Apple
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Implement a first-in-first-out (FIFO) queue using only stacks. Write the class MyQueue:

  • MyQueue() creates an empty queue.
  • void push(int x) adds x to the back of the queue.
  • int pop() removes the element at the front of the queue and returns it.
  • int peek() returns the element at the front of the queue without removing it.
  • boolean empty() returns true if the queue is empty, false otherwise.

Your queue may use only the standard stack operations: push to the top, peek at or pop from the top, size, and is-empty. (In a language without a stack type, a list used only through those operations is fine.)

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for push.

Example 1

Input: ["MyQueue","push","push","peek","pop","empty"]
[[],[3],[8],[],[],[]]
Output: [null,null,null,3,3,false]
Explanation: 3 arrives before 8, so it is at the front: peek and pop both give 3, and 8 is still queued.

Example 2

Input: ["MyQueue","push","pop","push","push","peek","pop","pop","empty"]
[[],[6],[],[2],[5],[],[],[],[]]
Output: [null,null,6,null,null,2,2,5,true]
Explanation: 6 leaves at once; then 2 and 5 come out in arrival order and the queue is empty.

Constraints

  • 1 <= x <= 9
  • At most 100 calls are made to push, pop, peek and empty
  • Every call to pop and peek is made on a non-empty queue

Follow-up: Can you make every operation amortized O(1) — n operations in O(n) total time, even if one of them takes longer?

Hints for Implement Queue using Stacks

  1. Hint 1

    Pouring one stack into another reverses the order of its elements — and reversed LIFO order is FIFO order.

  2. Hint 2

    Use an in stack that takes every push, and an out stack that serves pops and peeks.

  3. Hint 3

    Only when out is empty, move everything from in to out. Each element is moved at most once, so the cost averages out to O(1).

How to solve Implement Queue using Stacks

Two stacks make a queue: new elements land on in; the front of the queue is the top of out. When out runs dry, pouring in into it reverses those elements so the oldest ends on top.

Approach

  1. push(x): push x onto in.
  2. pop() / peek(): if out is empty, pop every element of in and push it onto out. Then pop / read the top of out.
  3. empty(): the queue is empty when both stacks are.

Why it works

Every element in out is older than every element in in, because out is only refilled when empty, from elements that were all pushed earlier than anything pushed afterwards. Within out the order is reversed arrival order, so its top is the oldest element overall — the queue's front.

Complexity

  • Time — amortized O(1) per operation
  • Space — O(n)

Pitfalls

  • Pouring in into out while out still holds elements breaks the order — only transfer when out is empty.
  • empty() must check both stacks.

Reference solution

Python

class MyQueue:

    def __init__(self):
        self.inbox = []
        self.outbox = []

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def _shift(self) -> None:
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        self._shift()
        return self.outbox.pop()

    def peek(self) -> int:
        self._shift()
        return self.outbox[-1]

    def empty(self) -> bool:
        return not self.inbox and not self.outbox

Java

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();

    public MyQueue() {
    }

    public void push(int x) {
        in.push(x);
    }

    private void shift() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
    }

    public int pop() {
        shift();
        return out.pop();
    }

    public int peek() {
        shift();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

C++

class MyQueue {
    stack<int> in, out;

    void shift() {
        if (out.empty()) while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    MyQueue() {}

    void push(int x) {
        in.push(x);
    }

    int pop() {
        shift();
        int x = out.top();
        out.pop();
        return x;
    }

    int peek() {
        shift();
        return out.top();
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};

JavaScript

var MyQueue = function() {
    this.inbox = [];
    this.outbox = [];
};

MyQueue.prototype.push = function(x) {
    this.inbox.push(x);
};

MyQueue.prototype.shiftStacks = function() {
    if (this.outbox.length === 0) while (this.inbox.length > 0) this.outbox.push(this.inbox.pop());
};

MyQueue.prototype.pop = function() {
    this.shiftStacks();
    return this.outbox.pop();
};

MyQueue.prototype.peek = function() {
    this.shiftStacks();
    return this.outbox[this.outbox.length - 1];
};

MyQueue.prototype.empty = function() {
    return this.inbox.length === 0 && this.outbox.length === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 111 stack problems · the whole catalogue

Learn the technique: Stack Data Structure · Queues and Deques