关阿姨带你横扫LeetCode系列之用队列实现栈

关阿姨正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

首先跟大家阐明一点就是，每道算法题都有多种解法，我们只讲LeetCode上几种优秀的解题思路~，希望

可以帮助到大家，那我们先来看下题目描述吧~

一、题目描述：

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

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

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

二、思路分析：

用队列实现栈，那我们要先了解队列和栈的特性，栈是先进后出的数据结构，而队列是先进先出的数据结构。要想用队列实现先进后出，那么我们把队列中先添加的元素放到后面不就好了~ 而且，队列中也有获取、删除第一个元素的操作，所以我们重点应该是在添加元素的时候，如何将先添加的元素放到后面。让我们来看看实现吧：

三、代码演示

class MyStack {
    Queue<Integer> queue;
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
   //添加元素
    public void push(int x) {
        //先获取队列中已有的元素个数
        int n = queue.size();
        //然后添加新元素
        queue.offer(x);
        //再将新元素之前的重新添加到队列，保证先添加的元素在后面，即先进后出
        for(int i=0; i<n; i++){
            queue.offer(queue.poll());
        }
    }
    //删除队列的第一个元素，即删除栈顶的元素
    public int pop() {
        return queue.poll();
    }
    //获取队列的第一个元素，即获取栈顶元素
    public int top() {
        return queue.peek();
    }
    //判断队列是否为空，即可判断栈是否为空
    public boolean empty() {
        return queue.isEmpty();
    }
}
复制代码