【数据结构】栈与队列的“双向奔赴”

前言

什么是栈？

栈（stack）是一种特殊的线性数据集合，只允许在栈顶按照后进先出LIFO（Last In First Out）进行数据操作；

为什么使用栈？

常见应用场景：浏览器的前进与回退操作、虚拟机栈等；

如何使用栈？

栈的实现结构可以是一维数组或链表实现
用数组实现的栈叫做顺序栈。在Java中，顺序栈使用java.util.Stack类实现
用链表实现的栈叫做链式栈。在Java中，链式栈使用java.util.LinkedList类实现；
入栈（push）：将新元素放入栈顶，只允许从栈顶一侧放入元素，类似于弹匣装弹，只能从弹匣口依次压入弹匣内；

出栈（pop）：只有栈顶元素才允许出栈，类似于枪射出子弹时，子弹从弹匣口依次进入枪体射出；

时间复杂度：

访问指定位置的元素：O(n) ——>需要依次遍历所有元素，所需元素可能在栈底
入栈和出栈：O(1) ——>只涉及栈顶

什么是队列？

队列（queue）是一种线性数据结构，队列中的元素按照先入先出的规则从队尾进入，队头出队；按照实现机制分为：单队列、循环队列；

为什么使用队列？

常见应用场景：KTV点歌列表、阻塞队列、线程池的任务队列等；

如何使用队列？

队列的实现结构可以是数组或链表实现
用数组实现的队列叫做顺序队列。在Java中，顺序队列使用java.util.ArrayDeque类实现；
用链表实现的队列叫做链式队列。在Java中，链式队列使用java.util.LinkedList类实现；
入队（enqueue）：只允许从队尾的位置放入元素，类似于银行取号等待叫号办理业务；

出队（dequeue）：只允许从队头的位置移出元素；

假溢出：使用数组实现队列，执行出队操作时，指向队头和队尾的指针会向后移，队尾指针移动到最后的时候，无法添加数据，即使数组中之前出队的位置还要空闲空间，这种现象就是“假溢出”。

1. 使用“栈”检查符号是否成对出现

 public static boolean isValid(String s ){
        
        HashMap<Character, Character> mappings = new HashMap<>();
        mappings.put('}','{');
        mappings.put(')','(');
        mappings.put(']','[');

        Stack<Character> stack = new Stack<>();

        for(int i=0;i<s.length();i++){

            char c =s.charAt(i);

            if(mappings.containsKey(c)){
                //当前字符是“右括号”
                char topElement = stack.isEmpty() ? '#' :stack.pop();
                char left = mappings.get(c);

                if(left != topElement){
                    return false;
                }

            }else {
                //当前字符是"左括号"
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

解读：

创建一个HashMap mappings，用于存储右括号和对应的左括号的映射关系；
创建一个Stack stack，用于存储遍历过程中遇到的左括号，以便后续进行匹配检查；
进入for循环，遍历输入的字符串s。在循环中，取出字符串中的每个字符c；
如果当前字符c存在于 mappings 中，即为右括号，那么就从栈中弹出栈顶元素，然后检查该右括号对应的左括号是否与弹出的左括号匹配，如果不匹配则返回false；
如果当前字符c不存在于 mappings 中，即为左括号，将其压入栈中；
循环结束后，检查栈是否为空，如果栈为空则说明所有的括号都匹配，返回true，否则返回false；

测试用例

   public static void main(String[] args) {
        String str ="{[(!)]}";
        System.out.println(isValid(str));
    }

测试结果

2. 使用“栈”实现字符串反转

public static void main(String[] args) {
        String str ="just do it";

        StringBuilder stringBuilder = new StringBuilder(str);
        //使用栈实现字符串反转
        Stack<Character> stringStack = new Stack<>();

        //入栈
        for(int i=0;i<str.length();i++){
            stringStack.push(str.charAt(i));
        }

        //出栈

        while (!stringStack.empty()){
            str +=stringStack.pop();
        }
        System.out.println(stringBuilder);
    }

解读：

创建一个Stack stringStack，用于存储字符串中的字符；
进入for循环，遍历输入的字符串str，将字符串中的每个字符依次压入栈中；
使用while循环，当栈不为空时，依次从栈中弹出字符，并将其拼接到原字符串str的末尾；
循环结束后，str中存储的就是原字符串str的反转结果；

测试结果

3. 使用“队列”实现“栈”

public class MyStack{
    private Queue<Integer> queue1; //出栈队列
    private Queue<Integer> queue2; //入栈队列
    
    public MyStack(){
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }

    public void push(int x){
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop(){
        return queue1.poll();
    }

    public int top(){
        return queue1.peek();
    }

    public boolean empty(){
        return queue1.isEmpty();
    }

    @Override
    public String toString() {
        return queue1.toString();
    }
}

解读：

定义了一个名为 MyStack 的类，其中包含两个私有属性 queue1 和 queue2，分别表示出栈队列和入栈队列，并在构造函数中对它们进行了初始化；
push 方法用于入栈操作，将元素加入 queue2 中，然后通过循环将 queue1 中的元素逐个转移到 queue2 中，以确保新入栈的元素位于队列的头部（因为队列的特性是先进先出）。最后交换 queue1 和 queue2 的引用，使得 queue1 始终指向当前栈中的元素所在的队列；
pop 方法用于出栈操作，直接从 queue1 中弹出元素即可；
top 方法用于获取栈顶元素，直接返回 queue1 的头部元素；
empty 方法用于判断栈是否为空，直接返回 queue1 是否为空的结果；

用两个队列模拟栈的基本操作，通过不断在两个队列之间转移元素，使得栈的操作可以在队列上进行；

测试用例

 public static void main(String[] args) {
        MyStack myStack = new MyStack();
        //入栈
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        System.out.println("入栈后"+myStack);
        System.out.println("入栈后栈顶元素:"+myStack.top());
        //出栈
        myStack.pop();

        myStack.pop();

        myStack.pop();

        myStack.pop();
        myStack.pop();
        System.out.println("出栈后"+myStack);
        System.out.println("出栈后栈是否为空:"+myStack.empty());
    }

测试结果

4. 使用“栈”实现“队列”

public class Queue{
    //入队栈
    private Stack<Integer> inStack = new Stack<>();
    
    //出队栈
    private Stack<Integer> outStack = new Stack<>();

    //入队
    public void offer(int item){
        while(!outStack.empty()){
            inStack.push(outStack.pop());
        }

        //新元素入队
        inStack.push(item);
    }


    //出队
    public int poll(){

        while(!inStack.empty()){
            outStack.push(inStack.pop());
        }
        return outStack.pop();
    }

    //判断是否为空
    public boolean empty(){
        return outStack.size() == 0 && inStack.size() == 0;
    }

    @Override
    public String toString() {
        return inStack.toString();
    }
}

解读：

offer 方法用于向队列中添加元素。首先，它会将 outStack 中的元素逐个弹出并压入 inStack 中，这样可以确保之前入队的元素在 inStack 的底部，新的元素可以被放在队列的末尾，接着，将新元素直接入栈到 inStack 中，表示将新元素放入队列中。
poll 方法用于从队列中取出元素。首先，它会将 inStack 中的元素逐个弹出并压入 outStack 中，这样可以确保队列的头部元素位于 outStack 的栈顶，然后，从 outStack 中弹出栈顶元素，并作为出队操作的结果返回。
empty 方法用于检查队列是否为空。只有当 inStack 和 outStack 都为空时，才表示整个队列为空；

基于两个栈实现队列的方法称为双栈法，通过巧妙地利用栈的特性，可以实现队列的先进先出（FIFO）功能。在实际应用中，双栈法可以用于需要频繁进行队列操作的场景，同时也可以作为栈和队列之间的一个有趣的数据结构转换方式。

测试用例

 public static void main(String[] args) {
        Queue myQueue = new Queue();

        //入队
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(4);
        myQueue.offer(5);
        System.out.println("入队后:"+myQueue);

        //出队
        myQueue.poll();
        myQueue.poll();
        myQueue.poll();
        myQueue.poll();
        myQueue.poll();
        System.out.println("出队后是否为空:"+myQueue.empty());

    }