[剑指offer][JAVA]面试题第[31]题[栈的压入、弹出序列][栈]

曾经终败给现在 2023-02-20 02:35 100阅读 0赞

#### 【问题描述】\[中等\] ####

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
    
     
    
    示例 1：
    
    输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出：true
    解释：我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
    示例 2：
    
    输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出：false
    解释：1 不能在 2 之前弹出。
     
    
    提示：
    
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。

#### 【解答思路】 ####

###### 栈 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(N)**

class Solution { 
        public boolean validateStackSequences(int[] pushed, int[] popped) { 
            Stack<Integer> stack = new Stack<>();
            //入栈数组的指针，必须维护，才知道此时应该是哪个数入栈
            int pushIndex = 0;
            //遍历要出栈的数组,如果可以全部出栈成功，那么返回TRUE
            for (int poppedIndex = 0; poppedIndex < popped.length; ++poppedIndex) { 
                //这个条件很关键，当 还有数可以入栈 && (栈为空，那么直接入栈，或者栈顶元素与要弹出的数不一样，那么继续入栈)
                while (pushIndex < pushed.length && (stack.empty() || stack.peek() != popped[poppedIndex]))
                    stack.push(pushed[pushIndex++]);
                //能走到这里，要么没有数可以继续入栈了，要么此时的栈顶元素和要弹出的数一致
                //如果栈顶元素和要弹出的数不一致，那么直接返回FALSE，因为正如上面所说，能走到这里还可能是因为没有数可以继续入栈了
                if (stack.peek() != popped[poppedIndex])
                    return false;
                //如果一致，那么出栈
                else
                    stack.pop();
            }
            //走到这里说明全部出栈成功，那么返回TRUE
            return true;
        }
    }

**优化**

class Solution { 
        public boolean validateStackSequences(int[] pushed, int[] popped) { 
            Stack<Integer> stack = new Stack<>();
            int i = 0;
            for(int num : pushed) { 
                stack.push(num); // num 入栈
                while(!stack.isEmpty() && stack.peek() == popped[i]) {  // 循环判断与出栈
                    stack.pop();
                    i++;
                }
            }
            return stack.isEmpty();
        }
    }

**使用 Deque 双端队列来代替 Stack**

public boolean validateStackSequences(int[] pushed, int[] popped) { 
            Deque<Integer> stack = new LinkedList<>();
            int idx = 0;
            for (int num : pushed) { 
                stack.offerFirst(num);
                while (!stack.isEmpty() && stack.peekFirst() == popped[idx]) { 
                    stack.pollFirst();
                    idx++;
                }
            }
            return stack.isEmpty();
        }

#### 【总结】 ####

###### 1.边界问题 注意越界 栈 先入先出 边入边出思想 辅助栈思想 ######

###### 2. 使用 Deque 双端队列来代替 Stack ######

基于 Vector 实现的栈 Stack底层是数组 扩容开销大  
Java并不推荐使用java.util.stack来进行栈的操作，而是推荐使用一个双端队列deque  
详情链接：https://www.cnblogs.com/cosmos-wong/p/11845934.html

###### 3.Stack 的常用方法： ######

push( num) 入栈
    pop() 栈顶元素出栈
    empty() 判定栈是否为空
    peek() 获取栈顶元素
    search(num) 判端元素num是否在栈中，如果在返回1，不在返回-1。    
    
    注意pop()和peek()的区别。pop()会弹出栈顶元素并返回栈顶的值，peek()只是获取栈顶的值，但是并不会把元素从栈顶弹出来

###### 4.Queue ######

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2][]  
Queue是在两端出入的List，所以也可以用数组或链表来实现。

*  add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
 *  remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
 *  element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
 *  offer 添加一个元素并返回true 如果队列已满，则返回false
 *  poll 移除并返问队列头部的元素 如果队列为空，则返回null
 *  peek 返回队列头部的元素 如果队列为空，则返回null
 *  put 添加一个元素 如果队列满，则阻塞
 *  take 移除并返回队列头部的元素 如果队列为空，则阻塞

###### 注意 ######

*  remove、element、offer 、poll、peek 其实是属于Queue接口。
 *  add remove element操作在队满或者队空的时候会报异常。
 *  offer poll peek 在队满或者队空的时候不会报异常。
 *  put take操作属于阻塞操作。队满队空均会阻塞。

###### 5.LinkedList ######

*  以双向链表实现的LinkedList既是List，也是Queue。
 *  它是唯一一个允许放入null的Queue。

转载链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/

参考链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/javazhan-shi-xian-yi-ji-zhi-zhen-mo-ni-zhan-liang-/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622112053269.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020062211210148.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200401235750547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70