新乡辉县网站建设,怎么做p2p网站,wordpress修改后台登录,做网站的成本作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;本文已收录至 Github《小白学算法》系列#xff1a;https://github.com/vipstone/algorith之前我们讲过《用两个栈实现一个… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone本文已收录至 Github《小白学算法》系列https://github.com/vipstone/algorith之前我们讲过《用两个栈实现一个队列》而今天我们要讲的是「用队列实现栈」它们都属于常见的面试题而我们今天要用多种方法来实现队列到栈的“转变”。老规矩先来回顾一下栈Stack和队列Queue的特性和常见方法。栈是后进先出LIFO的数据结构常见方法如下push()入栈方法向栈顶添加元素pop()出栈方法将栈顶的元素移除并返回元素peek()查询栈顶元素并不会移除元素。队列是先进先出FIFO的数据结构常见方法如下offer()入队方法向队尾添加元素poll()出队方法从队头移除并返回元素peek()查询队头元素并不会移除元素。知道了这些基础内容之后就来看今天的问题吧。题目描述使用队列实现栈的下列操作push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空注意:你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的你所使用的语言也许不支持队列。你可以使用 list 或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可你可以假设所有操作都是有效的例如, 对一个空的栈不会调用 pop 或者 top 操作。LeetCode 225https://leetcode-cn.com/problems/implement-stack-using-queues/题目解析这道题的题目很好理解只需要将先进先出的队列转换为后进先出的“栈”就可以了我们可以从多个方向入手来实现此功能比如使用两个队列插入并交换的方式或者是一个队列插入再交换的方式或双端队列的方式来实现此功能具体实现方法和代码如下。实现方法 1两个队列实现栈之前我们用两个栈实现了一个队列的文章中主要使用的是「负负得正」的思想那么当看到此道题时首先应该想到的是用两个队列来实现一个栈但这里的实现思路和用栈实现队列的思路又略有不同因为队列都是先进先出的我们可以把它理解为「正数」那么也就不能用「负负得正」的思想了我们这里使用两个队列来实现栈主要的操作思路是先将元素插入一个临时队列中然后再将另一个队列的所有元素插入到临时队列的尾部从而实现后进先出功能的具体的实现步骤如下。步骤一添加首个元素入列到临时队列 queue2步骤二因为正式队列中无元素因此无需将 queue1 中的元素移动到临时队列 queue2 的尾部直接将临时队列和正式队列互换即可步骤三添加第二个元素先入列到临时队列 queue2步骤四再将 queue1 中的元素移动到 queue2 的尾部如下所示步骤五再将 queue1 和 queue2 进行互换步骤六执行出队操作最终效果从最终的效果图我们可以看出通过两个队列已经实现了后进先出的特性也就是完成了从队列到栈的转换实现代码如下import java.util.Queue;class MyStack {QueueInteger queue1;QueueInteger queue2;public MyStack() {queue1 new LinkedBlockingQueue();queue2 new LinkedBlockingQueue();}/*** 入栈*/public void push(int x) {// 1.入列临时队列二queue2.offer(x);// 2.将队列一的所有元素移动到队列二while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}// 3.队列一和队列二互换QueueInteger temp queue1;queue1 queue2;queue2 temp;}/*** 出栈并返回此元素*/public int pop() {return queue1.poll();}/*** 查询栈顶元素*/public int top() {return queue1.peek();}/*** 判断是否为空*/public boolean empty() {return queue1.isEmpty();}
}
我们在 LeetCode 中提交以上测试代码执行结果如下此方法很稳竟然击败了 100% 的用户。实现方法 2一个队列实现栈那我们可以不可以用一个队列来实现栈呢答案是肯定的。我们只需要执行以下两个步骤就可以实现将队列转换为栈了具体实现步骤如下将元素入列到队尾再将除队尾之外的所有元素移除并重写入列。这样操作之后最后进入的队尾元素反而变成了队头元素也就实现了后进先出的功能了如下图所示。步骤一元素 1 入列步骤二元素 2 入列步骤三将最后一个元素之前的所有元素也就是元素 1出列重新入列步骤四执行出队操作最终效果以上思路的实现代码如下import java.util.Queue;class MyStack {QueueInteger queue1;public MyStack() {queue1 new LinkedBlockingQueue();}/*** 入栈*/public void push(int x) {// 获取原队列长度要移动的次数int count queue1.size();// 将元素放入队尾queue1.offer(x);// 将除最后一个元素外其他的元素重新入队for (int i 0; i count; i) {System.out.println(for);queue1.offer(queue1.poll());}}/*** 出栈并返回此元素*/public int pop() {return queue1.poll();}/*** 查询栈顶元素*/public int top() {return queue1.peek();}/*** 判断是否为空*/public boolean empty() {return queue1.isEmpty();}
}
我们把以上代码在 LeetCode 中提交执行结果如下此方法依旧很稳也是同样的击败了 100% 的用户只不过此方法在内存方面有更好的表现。实现方法 3双端队列实现栈如果觉得以上方法比较难的话最后我们还有一个更简单的实现方法我们可以使用 Java 中的双端队列 ArrayDeque 来实现将元素可以插入队头或队尾同样移除也是那么这样我们就可以从队尾入再从队尾出从而就实现了栈的功能了。双端队列结构如下我们来演示一下用双端队列实现栈的具体步骤。步骤一元素 1 入队步骤二元素 2 入队队尾步骤三再从队尾出队最终效果以上思路的实现代码如下import java.util.ArrayDeque;class MyStack {ArrayDequeInteger deque;public MyStack() {deque new ArrayDeque();}/*** 入栈*/public void push(int x) {deque.offer(x);}/*** 出栈并返回此元素*/public int pop() {return deque.pollLast();}/*** 查询栈顶元素*/public int top() {return empty() ? -1 : deque.peekLast();}/*** 判断是否为空*/public boolean empty() {return deque.isEmpty();}
}
我们把以上代码在 LeetCode 中提交执行结果如下总结本文我们用 3 种方法实现了将队列转换为栈其中最简单的方法是用 Java 中自带的双端队列 ArrayDeque 从队尾入并从队尾出就实现了栈 其他两个方法使用的是普通队列通过入队之后再移动元素到入队元素之后的方法从而实现了栈的功能。小伙伴们你学会了吗
往期推荐
算法图解如何用两个栈实现一个队列真不错图解Java中的5大队列小白学算法买卖股票的最佳时机关注我每天陪你进步一点点
