面试题31. 栈的压入、弹出序列

刺骨的言语ヽ痛彻心扉 2023-02-11 04:46 2阅读 0赞

# 题目： #

[面试题31. 栈的压入、弹出序列][31.]  
[946. 验证栈序列][946.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：辅助栈 #

![在这里插入图片描述][20200521211432734.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][2020052121150387.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][2020052121163655.png]

# 代码：辅助栈 #

import java.util.*;
    
    public class 面试题31 { 
    
        public static boolean validateStackSequences(int[] pushed, int[] popped) 
        { 
            Stack<Integer> stack = new Stack<>();
            int k = 0;
            for(int i = 0; i < pushed.length; i++)
            { 
                stack.push(pushed[i]); // pushed[i] 入栈
                while(!stack.empty() && stack.peek() == popped[k]) // 循环判断与出栈
                { 
                    stack.pop();
                    k++;
                }
            }
            if(stack.empty())
            { 
                return true;
            }
            else
            { 
                return false;
            }
        }
    
        public static void main(String[] args) { 
            int pushed1[] = {  1, 2, 3, 4, 5 };
            int popped1[] = {  4, 5, 3, 2, 1 };
            boolean res1 = validateStackSequences(pushed1, popped1);
            System.out.println(res1);
    
            int pushed2[] = {  1, 2, 3, 4, 5 };
            int popped2[] = {  4, 3, 5, 1, 2 };
            boolean res2 = validateStackSequences(pushed2, popped2);
            System.out.println(res2);
        }
    }

# 参考： #

1.  [面试题31. 栈的压入、弹出序列（模拟，清晰图解）][31. 1]
2.  [图解 模拟入栈操作，贪心算法][Link 1]
3.  [验证栈序列][Link 2]

[31.]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[946.]: https://leetcode-cn.com/problems/validate-stack-sequences/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521211323106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200521211432734.png]: https://img-blog.csdnimg.cn/20200521211432734.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521211446108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[2020052121150387.png]: https://img-blog.csdnimg.cn/2020052121150387.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521211514292.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200521211557502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[2020052121163655.png]: https://img-blog.csdnimg.cn/2020052121163655.png
[31. 1]: 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/
[Link 1]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/tan-xin-by-z1m/
[Link 2]: https://leetcode-cn.com/problems/validate-stack-sequences/solution/yan-zheng-zhan-xu-lie-by-leetcode/