首页 > itarticle > [leetcode] problem 225 – implement stack using queues

[leetcode] problem 225 – implement stack using queues

admin 11月 13, 2020 0

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

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   
stack.pop();   
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

private Queue<Integer> queue1;
private Queue<Integer> queue2;
private int top;

public () {
    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();
}