LeetCode 每日一题 [12] 用队列实现栈

LeetCode 用队列实现栈 [简单]

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

题目分析

用一个队列可以模拟栈，但是要两个栈才能模拟一个队列

方法1：

使用两个队列实现，始终保留一个为空，然后转移过去

方法2：

使用一个队列实现，利用队列的特征

代码实现

public class LeetCode_12_ImplementStackUsingQueues {

    public static void main(String[] args) {
        MyStack2 myStack = new MyStack2();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }
}

class MyStack2 {
    private LinkedList<Integer> queue = new LinkedList<>();

    public MyStack2() {
    }

    public void push(int x) {
        queue.offer(x);
    }

    public int pop() {
        return queue.pollLast();
    }


    public int top() {
        int top = pop();
        queue.offer(top);
        return top;
    }

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

class MyStack {

    private LinkedList<Integer> queue1 = new LinkedList<>();
    private LinkedList<Integer> queue2 = new LinkedList<>();

    public MyStack() {
    }

    public void push(int x) {
        if (queue1.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    public int pop() {
        if (queue1.isEmpty()) {
            while (queue2.size() > 1) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        } else {
            while (queue1.size() > 1) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }
    }


    public int top() {
        int top = pop();
        if (queue1.isEmpty()) {
            queue2.offer(top);
        } else {
            queue1.offer(top);
        }
        return top;
    }

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