当前位置:   article > 正文

栈的应用场景(高频面试题)

栈的应用场景

概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈
顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据在栈顶watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16

类似于子弹装在弹夹里,先压进去的,总是最后出来,栈也是这样,遵从先进后出的原则。

目录

概念

1.改变元素的序列

2. 将递归转化为循环

3. 括号匹配 

4. 逆波兰表达式求值

题目描述

5. 出栈入栈次序匹配

题目描述


 

1.改变元素的序列

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16

这是一道选择题,需要注意的是题目为进栈的过程可以出栈

A选项为1,4,3,2,第一个出的为1,我们要把1先入栈然后在出栈,第二个为4,我们要把2,3,4依次入栈,然后依次出栈,从顶部出,正好为4,3,2,。因此A满足。

B选项为2,3,4,1,第一个出的为2,我们要把1,2依次入栈,然后才能出一个2,此时栈内还有一个1,第二个出的为3,我们要把3入栈再出栈,第三个为4,把4入栈再出栈1最后把1出栈。因此B满足。

C选项为3,1,4,2,第一个出的为3,我们就要把1,2,3,依次入栈,然后出一个3,第二个出的为1,但此时在栈顶的为2,且1比2先入栈,所以1不能先出栈。因此C不满足,此题选C。

D选项为3,4,2,1,第一个出的为3,我们把1,2,3依次入栈,然后出一个3,此时1,2还在栈中,第二个出的为4,我们把4入栈在出栈,接着为2,1我们把栈内的1,2从栈顶出栈就能得到。因此D满足。


watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16 这道题需要注意的是,他是依次入栈,再依次出栈。

依次入栈,再从栈顶依次出栈,顺序则为EDCBA54321,此题选B。


2. 将递归转化为循环

比如:逆序打印链表

  1. //递归方式
  2. public void printList(ListNode head){
  3. if(head.next!=null){
  4. printList(head.next);
  5. }
  6. System.out.print(head.val+" ");
  7. }

递归方式很简单,条件为head.next不为空,就递归到head.next,直到走到最后一个开始打印,然后往回打印。

  1. public void pintList(ListNode head){
  2. ListNode cur=head;
  3. Stack<ListNode> stack=new Stack<>();
  4. //依次入栈
  5. while(cur!=null){
  6. stack.push(cur);
  7. cur=cur.next;
  8. }
  9. //出栈且打印
  10. while (!stack.empty()){
  11. System.out.print(stack.pop().val+" ");
  12. }
  13. }

如果用栈来解决,首先将链表都遍历一遍,全部依次入栈,最后一个元素正好在栈顶,然后在依次出栈并打印即可,这样就将递归改做了循环,用栈来实现。

运行结果

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_19,color_FFFFFF,t_70,g_se,x_16


3. 括号匹配
 

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  1. public boolean isValid(String s) {
  2. Stack<Character> stack=new Stack<>();
  3. for(int i=0;i < s.length();i++){
  4. char ch=s.charAt(i);
  5. if(ch=='('||ch=='['||ch=='{'){
  6. stack.push(ch);
  7. }
  8. else{
  9. if(stack.empty()){
  10. return false;
  11. }
  12. if(ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['
  13. ||ch=='}'&&stack.peek()=='{'){
  14. stack.pop();
  15. }
  16. else{
  17. return false;
  18. }
  19. }
  20. }
  21. if(stack.empty()){
  22. return true;
  23. }
  24. return false;
  25. }

  watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16

有了以上的分析结果,我们首先定义栈,遍历字符串拿到的是字符,所以类型应该定义为Character。接着我们便利字符串,进入循环,我们定义ch用来接收取到的字符,用charAt()转换为字符,接着判断是否为左括号(‘(’ ‘[’ '{'),如果是,直接入栈,不是我们再进行那四种结果的判断,如果此时栈空了,则说明右括号多了,如果此时左右括号匹配我们就出栈,如果不匹配,栈也没空就说明左右括号不匹配。走完循环说明字符串已经便利完成,且之前的都匹配成功,我们在判断栈是否为空,如果为空,说明此时正好都匹配成功如果不为空就说明左括号多了


4. 逆波兰表达式求值

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

题目描述

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

  1. public int evalRPN(String[] tokens) {
  2. Stack <Integer>stack=new Stack<>();
  3. for (String x:tokens){
  4. if(!isSymbol(x)){
  5. stack.push(Integer.parseInt(x));
  6. }
  7. else{
  8. //为+-*/
  9. int num2=stack.pop();
  10. int num1=stack.pop();
  11. switch(x){
  12. case "+":
  13. stack.push(num1+num2);
  14. break;
  15. case "-":
  16. stack.push(num1-num2);
  17. break;
  18. case "*":
  19. stack.push(num1*num2);
  20. break;
  21. case "/":
  22. stack.push(num1/num2);
  23. break;
  24. }
  25. }
  26. }
  27. return stack.peek();
  28. }
  29. private boolean isSymbol(String x){
  30. if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
  31. return true;
  32. }
  33. return false;
  34. }

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16

根据分析结果 ,我们首先定义栈,由于是数字运算,只有数字入栈,我们将栈定义为Integer类型,接着我们用for each来遍历字符串数组,进入循环,我们要判断此时的x为数字还是运算符,这里我写了一个private修饰的方法来判断判断后,如果是数字我们就将它入栈,如果不是数字就是运算符,我们应该switch语句进行匹配,匹配到哪个运算符就执行哪个运算符的操作。将运算结果在入栈,循环走完,说明数组遍历完成,最后栈中的数据就为最终中缀表达式的计算结果。

注意:

  1. 判断是否为运算符时要用equals()方法。
  2. 入栈时要用Integer.parseInt(x)将字符串转为整形。
  3. 最终结果就为栈中最后的数据。

5. 出栈入栈次序匹配

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

  1. public boolean IsPopOrder(int [] pushA,int [] popA) {
  2. Stack<Integer> stack=new Stack<>();
  3. int j=0;
  4. for(int i=0;i<pushA.length;i++){
  5. stack.push(pushA[i]);
  6. while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){
  7. stack.pop();
  8. j++;
  9. }
  10. }
  11. if(stack.empty()){
  12. return true;
  13. }
  14. return false;
  15. }

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Zi_5ouJ6JW-d2po,size_20,color_FFFFFF,t_70,g_se,x_16

 

思路,有了我们先遍历pushA数组将其中数据依次入栈,入栈一个,进入循环,再对栈顶的值与popA[]中的元素比较,如果等于就出栈一个。j从0开始,由于可能会连续匹配到,连续出栈,所以得用循环,如果前一个匹配到了,才能对popA中下一个值进行匹配。因此循环条件应该为:  
j<popA.length&&!stack.empty()&&stack.peek()==popA[j]

首先数组不能越界,还有栈中也不能为空,接着就要与栈顶值进行比较,匹配了出栈顶值,j++。
最后两个循环走完看栈是否空,如果空,说明都匹配到了,如果不为空,说明还有未匹配到的说明次序不对。

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/868984
推荐阅读
相关标签
  

闽ICP备14008679号