【LeetCode刷题日记】225.用队列实现栈--三招实现栈操作（多种思维）

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本文探讨了用队列实现栈操作的三种方法。重点分析了双队列实现方案通过que2作为辅助队列在push操作时将que1元素转移到que2后交换队列确保新元素始终位于队首栈顶实现先进后出特性。该方法push操作需O(n)时间pop/top操作仅需O(1)时间。文章还对比了单向队列与双端队列的实现差异指出双端队列可通过旋转操作更高效地实现栈功能。最后给出了Java实现的三种代码示例包括双队列、单队列和双端队列方案并比较了不同队列接口的操作特点及异常处理机制。题目背景用队列实现栈可直达使用队列实现栈的下列操作push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空注意:你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的例如, 对一个空的栈不会调用 pop 或者 top 操作。题目解析单向队列实现有的同学可能疑惑这种题目有什么实际工程意义其实很多算法题目主要是对知识点的考察和教学意义远大于其工程实践的意义所以面试题也是这样刚刚做过栈与队列我用栈来实现队列怎么样 (opens new window)的同学可能依然想着用一个输入队列一个输出队列就可以模拟栈的功能仔细想一下不行队列模拟栈其实一个队列就够了那么我们先说一说两个队列来实现栈的思路。队列是先进先出的规则把一个队列中的数据导入另一个队列中数据的顺序并没有变并没有变成先进后出的顺序。所以用栈实现队列 和用队列实现栈的思路还是不一样的这取决于这两个数据结构的性质。但是依然还是要用两个队列来模拟栈只不过没有输入和输出的关系而是另一个队列完全用来备份的如下面动画所示用两个队列que1和que2实现队列的功能que2其实完全就是一个备份的作用把que1最后面的元素以外的元素都备份到que2然后弹出最后面的元素再把其他元素从que2导回que1。如图所示我们利用了两个队列来实现栈的操作一个队列是与栈中保持相同元素的队列另一个是辅助队列。我们先把元素放到辅助队列的队尾中然后下面进行判断如果是第一个队列不是空的就把第一个队列的头部取出放到第二个队列的尾部这是个while循环不是仅仅处理一个元素可以说是把第一个队列的所有元素都放到第二个队列的尾部依次添加。之后进行交换把队列2的元素转移到队列1然后队列2 为空经过这种操作对于新添加的元素就自然而然地放在了队列1的队首了也就实现类栈的先进后出后进先出的逻辑了。流程解析假设当前queue1 [栈底 ... 栈顶] [a, b, c]队首 a队尾 c。queue2先放x进队尾 →queue2 [x]队首 x队尾 x。把queue1全部出队并入队到queue2出队 a入queue2→ [x, a]出队 b入queue2→ [x, a, b]出队 c入queue2→ [x, a, b, c]交换后queue1 [x, a, b, c]队首 x 是栈顶队尾 c 是栈底queue2变空。这样每次push后queue1的队首就是最新元素栈顶poll()就是栈的pop()。pop()queue1.poll()—— 队首出队即栈顶元素。top()queue1.peek()—— 查看队首元素但不删除。empty()queue1.isEmpty()—— 队列为空则栈为空。初始 queue1 []push(1): queue2[1], queue1 空 → 交换 → queue1[1], queue2[]push(2): queue2[2], 移 queue1 到 queue2 → queue2[2,1], 交换 → queue1[2,1]队首 2 是栈顶push(3): queue2[3], 移 queue1 → queue2[3,2,1], 交换 → queue1[3,2,1]pop(): 队首 3 出队 → queue1[2,1], 返回 3top(): peek → 2输出符合栈顺序。pushO(n)因为要把 queue1 中 n 个元素搬到 queue2。pop/topO(1)。emptyO(1)。✅ 优点只用标准队列操作offer/poll/peek逻辑清晰。❌ 缺点push消耗 O(n)不是最优实现可以用一个队列做到 O(1) push 和 O(n) pop。双端队列实现主要思想是就是把队尾的元素旋转到队尾que1.addLast(que1.peekFirst()); // 1. 把队首元素复制一份添加到队尾 que1.pollFirst(); // 2. 删除原来的队首元素具体执行过程队列 [1, 2, 3]操作队列状态说明初始[1, 2, 3]栈底→栈顶size3, size--2第1次循环[2, 3, 1]把 1 移到队尾第2次循环[3, 1, 2]把 2 移到队尾循环结束[3, 1, 2]队首 3 是栈顶pollFirst()[1, 2]返回 3 ✅pollFirst() 的特点方法作用队列空时pollFirst()删除并返回队首返回nullremoveFirst()删除并返回队首抛出异常peekFirst()只看不删返回nullgetFirst()只看不删抛出异常对比java QueueInteger queue1 new LinkedList(); QueueInteger queue2 new LinkedList();Queue接口只支持一端进、另一端出的单向操作从队尾添加offer()/add()从队首删除poll()/remove()查看队首peek()/element()没有直接操作队尾的方法如peekLast()或pollLast()java DequeInteger que1 new ArrayDeque();Deque接口支持双端操作Double-Ended Queue可以在队首/队尾两端进行添加、删除、查看方法如addFirst()、addLast()、pollFirst()、pollLast()、peekLast()等特性Queue单向队列Deque双端队列操作方向仅一端进、一端出两端都可进可出查看队尾❌ 不支持✅peekLast()从队尾删除❌ 不支持✅pollLast()从队首添加❌ 不支持✅addFirst()栈实现方式需要两个队列配合一个 Deque 就够了补充说明但是需要注意的是单向队列我们也可以仅仅通过一个队列来实现栈主要的逻辑就是通过循环把队列的队首依次拿出来放到队尾这样我们新添加的元素就到了队首也就是实现了栈。题目答案单向队列两个Queueclass MyStack { QueueInteger queue1; // 和栈中保持一样元素的队列 QueueInteger queue2; // 辅助队列 /** Initialize your data structure here. */ public MyStack() { queue1 new LinkedList(); queue2 new LinkedList(); } /** Push element x onto stack. */ public void push(int x) { queue2.offer(x); // 先放在辅助队列中 while (!queue1.isEmpty()){ queue2.offer(queue1.poll()); } QueueInteger queueTemp; queueTemp queue1; queue1 queue2; queue2 queueTemp; // 最后交换queue1和queue2将元素都放到queue1中 } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue1.poll(); // 因为queue1中的元素和栈中的保持一致所以这个和下面两个的操作只看queue1即可 } /** Get the top element. */ public int top() { return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty(); } }双向队列一个Dequeclass MyStack { // Deque 接口继承了 Queue 接口 // 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst DequeInteger que1; /** Initialize your data structure here. */ public MyStack() { que1 new ArrayDeque(); } /** Push element x onto stack. */ public void push(int x) { que1.addLast(x); } /** Removes the element on top of the stack and returns that element. */ public int pop() { int size que1.size(); size--; // 将 que1 导入 que2 但留下最后一个值 while (size-- 0) { que1.addLast(que1.peekFirst()); que1.pollFirst(); } int res que1.pollFirst(); return res; } /** Get the top element. */ public int top() { return que1.peekLast(); } /** Returns whether the stack is empty. */ public boolean empty() { return que1.isEmpty(); } }单向队列一个Queueclass MyStack { QueueInteger queue; public MyStack() { queue new LinkedList(); } //每 offer 一个数A进来都重新排列把这个数A放到队列的队首 public void push(int x) { queue.offer(x); int size queue.size(); //移动除了 A 的其它数 while (size-- 1) queue.offer(queue.poll()); } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }