剑指offer-5、两个栈实现⼀个队列
<h2 id="题描述">题⽬描述</h2><p>⽤两个栈来实现⼀个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。</p>
<h2 id="思路及解答">思路及解答</h2>
<ul>
<li>栈的特性是先进后出</li>
<li>队列的特性是先进先出</li>
</ul>
<p>有两个栈 stack1 , stack2 ；</p>
<ul>
<li>如果有新的数据进⼊，那么我们可以直接 push 到 stack1 ；</li>
<li>如果需要取出数据，那么我们优先取出 stack2 的数据，如果 stack2 ⾥⾯数据是空的，那么我们需要把所有的 stack1 的数据倒⼊ stack2 。再从 stack2 取数据。</li>
</ul>
<p>例如：</p>
<ol>
<li>push 1 --> push 2</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161709874.png" alt="" loading="lazy"></p>
<ol start="2">
<li>pop 1</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161709866.png" alt="image-20250316170844217" loading="lazy"></p>
<ol start="3">
<li>push 3 --> push 4</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161709847.png" alt="" loading="lazy"></p>
<ol start="4">
<li>pop 2</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503161709761.png" alt="" loading="lazy"></p>
<pre><code class="language-java">import java.util.Stack;
public class Solution {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
/** Initialize your data structure here. */
public MyQueue() {
stackIn = new Stack<>(); // 负责进栈
stackOut = new Stack<>(); // 负责出栈
}
/** Push element x to the back of queue. */
public void push(int x) {
stackIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
dumpstackIn();
return stackOut.pop();
}
/** Get the front element. */
public int peek() {
dumpstackIn();
return stackOut.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
private void dumpstackIn(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
</code></pre>
<h2 id="扩展-两个队列实现栈">扩展-两个队列实现栈</h2>
<p><strong>队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。</strong></p>
<p>所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。</p>
<p>但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！</p>
<pre><code class="language-java">class MyStack {
Queue<Integer> queue1; // 和栈中保持一样元素的队列
Queue<Integer> 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());
}
Queue<Integer> 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();
}
}
</code></pre>
<ul>
<li>时间复杂度: pop为O(n)，其他为O(1)</li>
<li>空间复杂度: O(n)</li>
</ul>
<p>优化：</p>
<p>其实这道题目就是用一个队列就够了。</p>
<p><strong>一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。</strong></p>
<pre><code class="language-java">class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.add(x);
}
public int pop() {
rePosition();
return queue.poll();
}
public int top() {
rePosition();
int result = queue.poll();
queue.add(result);
return result;
}
public boolean empty() {
return queue.isEmpty();
}
public void rePosition(){
int size = queue.size();
size--;
while(size-->0)
queue.add(queue.poll());
}
}
</code></pre>
<ul>
<li>时间复杂度: pop为O(n)，其他为O(1)</li>
<li>空间复杂度: O(n)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18942348
頁:
[1]