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

什么是栈和队列？

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

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

设计思路

具体的实现是，一个栈作为压入栈，在压入数据时只往这个栈中压入，几位stackPush，另一个栈作为弹出栈，在弹出数据时，只从这个栈中弹出，记为stackPop。
因为数据压入栈的时候，顺序是先进后出的。那么只要把 stackPush的数据再压入stackPop中，顺序就变回来了。例如,将1-5依次压入 stackPush，那么从stackIn的栈顶到栈底为 5-1，此时依次再将5-1倒入stackPop，那么从stackOut的栈顶到栈底就变成了1~5。再从 stackPop弹出时，顺序就像队列一样。

听起来虽然简单,实际上必须做到以下两点。
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());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57