Implement Stack using Queues

Easy
2036.

Implement Stack using Queues

Implement Stack using Queues is an easy coding problem on stack and queue, asked in Amazon, Microsoft and Bloomberg interviews.

Implement a last-in-first-out (LIFO) stack using only queues. Write the class MyStack:

  • MyStack() creates an empty stack.
  • void push(int x) pushes x onto the top of the stack.
  • int pop() removes the element on the top of the stack and returns it.
  • int top() returns the element on the top of the stack without removing it.
  • boolean empty() returns true if the stack is empty, false otherwise.

Your stack may use only the standard queue operations: push to the back, peek at or pop from the front, size, and is-empty. (In a language without a queue type, a list or deque 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
["MyStack","push","push","top","pop","empty"] [[],[4],[7],[],[],[]]
Output
[null,null,null,7,7,false]
Explanation
After pushing 4 then 7, the top is 7; pop removes 7, leaving 4, so the stack is not empty.

Example 2

Input
["MyStack","empty","push","push","push","pop","top","pop","pop","empty"] [[],[],[1],[9],[5],[],[],[],[],[]]
Output
[null,true,null,null,null,5,9,9,1,true]
Explanation
The stack starts empty. 1, 9, 5 are pushed; they come off in the order 5, 9, 1, after which the stack is empty again.

Constraints

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

Follow-up: Can you implement the stack with only one queue?

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

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

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

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    
};

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

Sign in to run your own test cases

Sign in

Implement Stack using Queues — Problem & Solution

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

Implement Stack using Queues is an easy coding problem on stack and queue, asked in Amazon, Microsoft and Bloomberg interviews.

  • Difficulty: Easy
  • Topics: Stack, Queue
  • Asked at: Amazon, Microsoft, Bloomberg
  • 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 last-in-first-out (LIFO) stack using only queues. Write the class MyStack:

  • MyStack() creates an empty stack.
  • void push(int x) pushes x onto the top of the stack.
  • int pop() removes the element on the top of the stack and returns it.
  • int top() returns the element on the top of the stack without removing it.
  • boolean empty() returns true if the stack is empty, false otherwise.

Your stack may use only the standard queue operations: push to the back, peek at or pop from the front, size, and is-empty. (In a language without a queue type, a list or deque 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: ["MyStack","push","push","top","pop","empty"]
[[],[4],[7],[],[],[]]
Output: [null,null,null,7,7,false]
Explanation: After pushing 4 then 7, the top is 7; pop removes 7, leaving 4, so the stack is not empty.

Example 2

Input: ["MyStack","empty","push","push","push","pop","top","pop","pop","empty"]
[[],[],[1],[9],[5],[],[],[],[],[]]
Output: [null,true,null,null,null,5,9,9,1,true]
Explanation: The stack starts empty. 1, 9, 5 are pushed; they come off in the order 5, 9, 1, after which the stack is empty again.

Constraints

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

Follow-up: Can you implement the stack with only one queue?

Hints for Implement Stack using Queues

  1. Hint 1

    A queue hands elements back oldest first, a stack newest first. Arrange the queue so that its front is always the newest element.

  2. Hint 2

    When a new element is pushed to the back of the queue, every older element is in front of it.

  3. Hint 3

    After pushing x, rotate the queue size - 1 times (pop from the front, push to the back). Now x is at the front, so pop and top are ordinary front operations.

How to solve Implement Stack using Queues

Keep one queue in stack order — newest element at the front. A push appends the new element and then rotates every older element behind it; after that, pop, top and empty are plain queue operations.

Approach

  1. push(x): enqueue x, then repeat size - 1 times: dequeue the front element and enqueue it again.
  2. pop(): dequeue and return the front element.
  3. top(): return the front element without removing it.
  4. empty(): return whether the queue is empty.

Why it works

By induction the queue, read front to back, is the stack from top to bottom. Pushing x puts it last; rotating the size - 1 older elements from the front to the back moves them behind x in their existing order, so x is now first and the rest keep their stack order.

Complexity

  • Time — push O(n); pop, top and empty O(1)
  • Space — O(n)

Pitfalls

  • Rotating size times instead of size - 1 puts the new element back at the end.
  • The two-queue version (move all but the last element across on each pop) is also accepted; it makes pop the O(n) operation instead of push.

Reference solution

Python

from collections import deque

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):  # bring x to the front
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

Java

class MyStack {
    private Queue<Integer> q = new ArrayDeque<>();

    public MyStack() {
    }

    public void push(int x) {
        q.offer(x);
        for (int i = 1; i < q.size(); i++) q.offer(q.poll()); // bring x to the front
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

C++

class MyStack {
    queue<int> q;
public:
    MyStack() {}

    void push(int x) {
        q.push(x);
        for (size_t i = 1; i < q.size(); i++) { q.push(q.front()); q.pop(); } // bring x to the front
    }

    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

JavaScript

var MyStack = function() {
    this.q = [];
};

MyStack.prototype.push = function(x) {
    this.q.push(x);
    for (var i = 1; i < this.q.length; i++) this.q.push(this.q.shift()); // bring x to the front
};

MyStack.prototype.pop = function() {
    return this.q.shift();
};

MyStack.prototype.top = function() {
    return this.q[0];
};

MyStack.prototype.empty = function() {
    return this.q.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