[LeetCode] Problem 225 - Implement Stack using Queues

Posted on | In ,

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.

Example

1
2
3
4
5
6
7
MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes

  • You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private Queue<Integer> queue1;
private Queue<Integer> queue2;
private int top;

public MyStack() {
    queue1 = new LinkedList<>();
    queue2 = new LinkedList<>();
}

public void push(int x) {
    queue1.offer(x);
    top = x;
}

public int pop() {
    while (queue1.size() > 1) {
        top = queue1.remove();
        queue2.offer(top);
    }

    int num = queue1.poll();

    while (!queue2.isEmpty())
        queue1.offer(queue2.remove());

    return num;
}

public int top() {
    return top;
}

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