《剑指Offer》栈&队列全题——妙解思路，难度由浅入深

刺骨的言语ヽ痛彻心扉 2024-04-08 10:28 101阅读 0赞

**目录**

JZ9 用两个栈实现队列

JZ30 包含min函数的栈

JZ31 栈的压入、弹出序列

JZ73 翻转单词序列

JZ59 滑动窗口的最大值

--------------------

## JZ9 用两个栈实现队列 ##

> 思路（蓄水池）：创建两个栈，入栈时先入栈一，出栈时，先检测栈二是否为空，若为空，将栈一所有元素全部弹出并压入栈二，若不为空，则直接将栈二元素弹出即可。
> 
> 以下链接是博主早已整理出画图理解，包括两个栈如何实现队列？两个队列如何实现栈？快来看看吧！
> 
> [http://t.csdn.cn/vyc3o][http_t.csdn.cn_vyc3o]

Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) {
            if(stack2.isEmpty()){
                stack1.push(node);
            }else{
                while(!stack2.isEmpty()){
                    stack1.push(stack2.pop());
                }
                stack1.push(node);
            }
        }
        
        public int pop() {
            int ret = 0;
            if(!stack2.isEmpty()){
                ret = stack2.pop();
            }else{
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                ret = stack2.pop();
            }
            return ret;
        }

--------------------

## JZ30 包含min函数的栈 ##

> 思路（此题是头条的笔试题）：建立两个栈，一个是主栈，一个是最小栈，每次压栈主栈都会进行压栈，而最小栈只有为空或是压栈元素小于最小栈栈顶元素即可；出栈时主栈每次必须出栈并在出栈时检测是否与最小栈栈顶元素相等，若相等则一起弹出，若不相等，则不用弹出~

Stack<Integer> stack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();
        public void push(int node) {
            //最小栈为空直接放数据
            if(minStack.isEmpty()){
                minStack.push(node);
            }else if(minStack.peek() >= node){//小于等于最小栈栈顶元素都要放入
                minStack.push(node);
            }
            //主栈必须放
            stack.push(node);
        }
        
        public void pop() {
            //检测主栈元素是否等于最小栈栈顶元素，若等于也需要pop
            //这里要注意pop和peek操作返回的都是泛型类，没有整数比较时需要强制类型转化
            if((int)stack.pop() == (int)minStack.peek()){
                minStack.pop();
            }
        }
        
        public int top() {
            return stack.peek();
        }
        
        public int min() {
            return minStack.peek();
        }

--------------------

## JZ31 栈的压入、弹出序列 ##

> 思路：创建一个栈，将所给入栈序列一个一个入栈，同时将每个入栈元素与弹出序列的元素进行比较，若相等就弹出，不相等则继续压栈，往复操作，直到遍历完为止

public boolean IsPopOrder(int [] pushA,int [] popA) {
            Stack<Integer> stack = new Stack<>();
            int count = 0;//计数：与压栈数据匹配则加一
            for(int i = 0; i < pushA.length; i++){
                if(pushA[i] == popA[count]){
                    //先压栈，再判断
                    stack.push(pushA[i]);
                    while(stack.peek() == popA[count]){
                        stack.pop();
                        count++;
                        //popA遍历完说明正确
                        if(count == pushA.length){
                            return true;
                        }
                        /**
                        *弹出栈后，可能一个元素也不剩，这时再到while里判断，
                        *有可能能造成对空指针的解引用操作
                        */
                        if(stack.empty()){
                            break;
                        }
                    }
                }
                else{
                    stack.push(pushA[i]);
                }
            }
            return false;
        }

--------------------

## JZ73 翻转单词序列 ##

此题给出了进阶要求：空间复杂度 O(n) ，时间复杂度 O(n) ，栈解决依然符合要求

> 思路：先将所给字符串分割放入数组中，创建一个栈，直接压栈出栈即可得到反转单词（注意空格），是不是很妙~

![d5f60e754a8942fe885ed47c6f6c784a.gif][]

public String ReverseSentence(String str) {
            Stack<String> stack = new Stack<>();
            //每个单词用空格分开
            String[] strArr = str.split(" ");
            StringBuilder ret = new StringBuilder();
            //压栈
            for(int i = 0; i < strArr.length; i++){
                //注意空格隔开
                if(i != 0){
                    stack.push(" ");
                }
                stack.push(strArr[i]);
            }
            //出栈
            while(!stack.isEmpty()){
                ret.append(stack.pop());
            }
            return ret.toString();
        }

--------------------

## JZ59 滑动窗口的最大值 ##

> 解法一（双指针法，若不考虑时间复杂度，则可以通过）：通过双指针来维护滑动窗口，并且每次遍历小的滑动窗口，比较出最大值后放入顺序表，往复操作即可~

public ArrayList<Integer> maxInWindows(int [] num, int size) {
            ArrayList<Integer> array = new ArrayList<>();
            //假定最大值
            for(int i = 0; i < num.length - size + 1; i++){
                int left = i;
                int right = left + size - 1;
                //求最大值
                int max = num[left];//假定最大值
                for(int j = left; j <= right; j++){
                    if(num[j] > max){
                        max = num[j];
                    }
                }
                array.add(max);
            }
            return array;
        }

> 解法二（双端队列）：创建一个双端队列，保持对头存放数组最大值下标，窗口滑动每滑动一次，就要判断当前最大值是否还是真的最大值，同时新增元素从队尾开始比较，比他小的全部出队，往复操作即可~

public static ArrayList<Integer> maxInWindows(int [] num, int size){
            ArrayList<Integer> array = new ArrayList<>();
            //长度为零直接返回空表
            if(size == 0) {
                return array;
            }
            int begin = 0;
            //双端队列用来存放下标
            Deque<Integer> deque = new LinkedList<>();
            for(int i = 0; i < num.length; i++){
                //制造虚拟滑动窗口起点
                begin = i - size + 1;
                //若为空，先放入元素假定为最大值
                if(deque.isEmpty()){
                    deque.add(i);
                }
                else if(begin > deque.peekFirst()){
                    deque.pollFirst();
                }
                //队尾开始比较，把比他小的都出队
                while((!deque.isEmpty()) && num[deque.peekLast()] <= num[i]){
                    deque.pollLast();
                }
                deque.add(i);
                if(begin >= 0){
                    array.add(num[deque.peekFirst()]);
                }
            }
            return array;
        }

--------------------

![45d85f033ca746ff9d1843de8bc30b3b.gif][]

[http_t.csdn.cn_vyc3o]: http://t.csdn.cn/vyc3o
[d5f60e754a8942fe885ed47c6f6c784a.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d6407de744e44f1cb7c18eb3491accf1.gif
[45d85f033ca746ff9d1843de8bc30b3b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b227c6b3c3014bf081c76285949fa4e4.gif