《剑指offer》之用两个栈来实现一个队列

喜欢ヅ旅行 2023-07-03 03:16 28阅读 0赞

# 前言 #

今天刷的一道题是用两个栈来表示一个队列。  
我们知道栈和队列的主要区别在于：  
栈：后进先出  
队列：先进先出。

# 题目 #

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

# 分析 #

需要通过两个后进先出的栈实现一个先进先出的队列。如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]  
假设往栈stack1 中压入 1，2，3，4，5，6，7 这几个数据，如果直接从stack1中取的话，就是7，6，5，4，3，2，1.与我们想要你的先进先出不符合。所以我们将stack1的数据依次出栈并压入栈stack2 中，这样再从stack2 中出栈的数据就是1，2，3，4，5，6，7了。  
但是，上面的这些只考虑了先进栈后压栈。那如果是进栈出栈交替呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]  
比如初始，向stack1 中压入 1，2，3.然后，将stack1 中的数据出栈入栈到stack2 中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]  
那这个时候，再往stack1 中进栈的话，该怎么压入栈stack2 中呢？  
这里其实大家应该注意到，如果stack2 中存在数据，那这些数据应该是最先出栈的，所以直接出栈就好了，不用管stack1 中的数据，因为那些是后来的数据，肯定是是后出栈的。当栈stack2 中没有数据的时候，再将stack1 中的数据都出栈压入stack2 中。这样就可以实现一个队列的先进先出啦。

# 解法 #

进队列，直接将数据压入栈stack1 中就好了。

public void push(int node){
            stack1.push(node);
        }

出队列,先判断stack2 中是否有数据，有的话，直接从stack2 中出栈。  
如果没有，就将stack1 中的数据压入栈stack2 中。然后再从stack2 中出栈。

public int pop(){
            if(!stack2.isEmpty()){
                return stack2.pop();
            }
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

不过上面的代码还可以简化一下，毕竟两个return stack2.pop(); 有点不舒服。

public int pop(){
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

# 源代码： #

public class Solution {
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
    
        public static void main(String[] args) {
            Solution solution= new Solution();
            solution.push(0);
            solution.push(1);
            solution.push(2);
            solution.push(3);
            solution.push(4);
            solution.push(5);
            System.out.print(solution.pop()+"\t");
            System.out.print(solution.pop()+"\t");
            System.out.print(solution.pop()+"\t");
            solution.push(6);
            solution.push(7);
            solution.push(8);
            System.out.print(solution.pop()+"\t");
            System.out.print(solution.pop()+"\t");
            System.out.print(solution.pop()+"\t");
        }
    
        public void push(int node){
            stack1.push(node);
        }
    
        public int pop(){
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
    
            return stack2.pop();
        }
    }

# 测试 #

![在这里插入图片描述][20200201135810926.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200201133551176.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020020113454386.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200201134748883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[20200201135810926.png]: https://img-blog.csdnimg.cn/20200201135810926.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200201135833937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9xdWVsbGFuYW4uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70