赞
踩
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈
顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据在栈顶。
类似于子弹装在弹夹里,先压进去的,总是最后出来,栈也是这样,遵从先进后出的原则。
目录
这是一道选择题,需要注意的是题目为进栈的过程可以出栈。
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满足。
这道题需要注意的是,他是依次入栈,再依次出栈。
依次入栈,再从栈顶依次出栈,顺序则为EDCBA54321,此题选B。
比如:逆序打印链表
- //递归方式
- public void printList(ListNode head){
- if(head.next!=null){
- printList(head.next);
- }
- System.out.print(head.val+" ");
- }
递归方式很简单,条件为head.next不为空,就递归到head.next,直到走到最后一个开始打印,然后往回打印。
- public void pintList(ListNode head){
- ListNode cur=head;
- Stack<ListNode> stack=new Stack<>();
- //依次入栈
- while(cur!=null){
- stack.push(cur);
- cur=cur.next;
- }
- //出栈且打印
- while (!stack.empty()){
- System.out.print(stack.pop().val+" ");
- }
- }
如果用栈来解决,首先将链表都遍历一遍,全部依次入栈,最后一个元素正好在栈顶,然后在依次出栈并打印即可,这样就将递归改做了循环,用栈来实现。
运行结果
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- public boolean isValid(String s) {
- Stack<Character> stack=new Stack<>();
- for(int i=0;i < s.length();i++){
- char ch=s.charAt(i);
- if(ch=='('||ch=='['||ch=='{'){
- stack.push(ch);
- }
- else{
- if(stack.empty()){
- return false;
- }
- if(ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['
- ||ch=='}'&&stack.peek()=='{'){
- stack.pop();
- }
- else{
- return false;
- }
- }
- }
- if(stack.empty()){
- return true;
- }
- return false;
- }
有了以上的分析结果,我们首先定义栈,遍历字符串拿到的是字符,所以类型应该定义为Character。接着我们便利字符串,进入循环,我们定义ch用来接收取到的字符,用charAt()转换为字符,接着判断是否为左括号(‘(’ ‘[’ '{'),如果是,直接入栈,不是我们再进行那四种结果的判断,如果此时栈空了,则说明右括号多了,如果此时左右括号匹配我们就出栈,如果不匹配,栈也没空就说明左右括号不匹配。走完循环说明字符串已经便利完成,且之前的都匹配成功,我们在判断栈是否为空,如果为空,说明此时正好都匹配成功,如果不为空就说明左括号多了。
逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。
根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
- public int evalRPN(String[] tokens) {
- Stack <Integer>stack=new Stack<>();
- for (String x:tokens){
- if(!isSymbol(x)){
- stack.push(Integer.parseInt(x));
- }
- else{
- //为+-*/
- int num2=stack.pop();
- int num1=stack.pop();
- switch(x){
- case "+":
- stack.push(num1+num2);
- break;
- case "-":
- stack.push(num1-num2);
- break;
- case "*":
- stack.push(num1*num2);
- break;
- case "/":
- stack.push(num1/num2);
- break;
- }
- }
- }
- return stack.peek();
-
- }
- private boolean isSymbol(String x){
- if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
- return true;
- }
- return false;
- }
根据分析结果 ,我们首先定义栈,由于是数字运算,只有数字入栈,我们将栈定义为Integer类型,接着我们用for each来遍历字符串数组,进入循环,我们要判断此时的x为数字还是运算符,这里我写了一个private修饰的方法来判断。判断后,如果是数字我们就将它入栈,如果不是数字就是运算符,我们应该switch语句进行匹配,匹配到哪个运算符就执行哪个运算符的操作。将运算结果在入栈,循环走完,说明数组遍历完成,最后栈中的数据就为最终中缀表达式的计算结果。
注意:
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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 的所有数字均不相同
- public boolean IsPopOrder(int [] pushA,int [] popA) {
- Stack<Integer> stack=new Stack<>();
- int j=0;
- for(int i=0;i<pushA.length;i++){
- stack.push(pushA[i]);
- while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){
- stack.pop();
- j++;
- }
- }
- if(stack.empty()){
- return true;
- }
- return false;
- }
思路,有了我们先遍历pushA数组将其中数据依次入栈,入栈一个,进入循环,再对栈顶的值与popA[]中的元素比较,如果等于就出栈一个。j从0开始,由于可能会连续匹配到,连续出栈,所以得用循环,如果前一个匹配到了,才能对popA中下一个值进行匹配。因此循环条件应该为:
j<popA.length&&!stack.empty()&&stack.peek()==popA[j]
首先数组不能越界,还有栈中也不能为空,接着就要与栈顶值进行比较,匹配了出栈顶值,j++。
最后两个循环走完看栈是否空,如果空,说明都匹配到了,如果不为空,说明还有未匹配到的说明次序不对。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。