【算法】简单讲解如何使用两个栈实现一个队列

「爱情、让人受尽委屈。」 2024-03-16 09:38 20阅读 0赞

#### 文章目录 ####

*  什么是栈和队列？
 *  设计思路
 *  代码实现

## 什么是栈和队列？ ##

栈和队列其实大家基本都知道是什么，或者说，最基本的，他们的特性我们是知道的。  
栈是一种FILO先进后出的数据结构，队列是一种FIFO先进先出的数据结构。

那么其实他们两个是反过来的，那么，我们其实就可以通过两个栈，实现一个队列，下面是一个简单的代码，包含了add，poll，peek方法。

## 设计思路 ##

具体的实现是，一个栈作为压入栈，在压入数据时只往这个栈中压入，几位stackPush，另一个栈作为弹出栈，在弹出数据时，只从这个栈中弹出，记为stackPop。  
因为数据压入栈的时候，顺序是先进后出的。那么只要把 stackPush的数据再压入stackPop中，顺序就变回来了。例如,将1-5依次压入 stackPush，那么从stackIn的栈顶到栈底为 5-1，此时依次再将5-1倒入stackPop，那么从stackOut的栈顶到栈底就变成了1~5。再从 stackPop弹出时，顺序就像队列一样。  
![在这里插入图片描述][7ac67259bd4b4d34a96ae3e93c7e26d6.png]  
听起来虽然简单,实际上必须做到以下两点。  
1.如果 stackPush要往是stackPop中压入粉据.那么必须一次性把 stackPush中的数据全部压  
2．如果stackPop不为空,sctarkPuch绝对不能向 stackPop中压入数  
违反了以上两点都会发生错误。  
违反1的情况举例：  
1-5依次压入 stackPush，stackPush的栈顶到栈底为5~1，从stackPush压入stackPop时，只将5和4压入了 stackPop，stackPush还剩下1、2、3没有压入。此时如果用户想进行弹出操作，那么4将最先弹出,与预想的队列顺序就不一致  
违反2的情况举例：  
1-5依次压入 stackPush，stackPush将所有的数据压入stackPop，此时从 stackPop的栈顶到栈底就变成了1-5。此时又有6-10依次压入 stackPush，stackPop不为空，stackPush不能向其中压入数据。如果违反2压入了stackPop，从 stackPop 的栈顶到栈底就变成了6-10、1~5。那么此时如果用户想进行弹出操作，6将最先弹出，与预想的队列顺序就不一致。  
上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢?  
这个选择的时机可以有很多，调用add、poll和 peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点，就不会出错。具体实现请参看如下的代码，代码比较简单

## 代码实现 ##

package com.base.learn.stack;
    
    import com.sun.org.apache.bcel.internal.generic.PUSH;
    
    import java.util.Stack;
    
    /**
     * @author: 张锦标
     * @date: 2023/5/27 14:43
     * StackMakeQueue类
     * 使用两个栈形成一个队列
     * 支持队列的add poll peek
     */
    public class StackMakeQueue {
        
        private Stack<Integer> stackPush = new Stack<>();
        private Stack<Integer> stackPop = new Stack<>();
    
        public void add(int num){
        
            stackPush.push(num);
            inToOut();
        }
        private void inToOut(){
        
            //只有空的时候才能把in的数据放入到out,不然顺序就乱了
            if (stackPop.empty()){
        
                while (!stackPush.empty()){
        
                    stackPop.push(stackPush.pop());
                }
            }
        }
        public int poll(){
        
            if (stackPop.isEmpty() && stackPush.isEmpty()){
        
                throw new RuntimeException("栈中并没有数据");
            }
            //如果说in栈中有数据 但是out栈中没有 那么把数据移动到out栈中
            inToOut();
            return stackPop.pop();
        }
    
        public int peek(){
        
            if (stackPop.isEmpty() && stackPush.isEmpty()){
        
                throw new RuntimeException("栈中并没有数据");
            }
            //如果说in栈中有数据 但是out栈中没有 那么把数据移动到out栈中
            inToOut();
            return stackPop.peek();
        }
         public static void main(String[] args) {
        
            StackMakeQueue stackMakeQueue = new StackMakeQueue();
            stackMakeQueue.add(1);
            stackMakeQueue.add(2);
            stackMakeQueue.add(3);
            System.out.println(stackMakeQueue.poll());
            System.out.println(stackMakeQueue.poll());
            System.out.println(stackMakeQueue.poll());
        }
    }

[7ac67259bd4b4d34a96ae3e93c7e26d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ec3ee83110fb481e95f6ae4318714ff1.png