摘要:压栈栈的插入数据操作叫做进栈,压栈,入栈。入数据在栈顶出栈栈的删除操作叫做出栈。栈区是线程私有的,存放的是函数调用相关信息,主要是栈帧,它是按照数据结构中栈的特性来实现的栈帧一种结构,与函数调用相关。
目录
栈是一种特殊的线性表,它只能在固定的一端进行插入和删除操作,进行数据插入和删除的一端为栈顶,另一端为栈底。栈中的元素遵循后进先出(LIFO)(Last In First Out)的原则。
压栈:栈的插入数据操作叫做进栈,压栈,入栈。入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据在栈顶
方法 | 功能说明 |
Stack() | 构造一个空栈 |
E push(E e) | 将e入栈并返回e |
E pop() | 将栈顶元素出栈并返回 |
E peek() | 获取栈顶元素 |
int size() | 获取栈中有效元素的个数 |
boolean empty() | 检测栈是否为空 |
将上述方法进行代码展示:
public class TestStack { public static void main(String[] args) { Stack s = new Stack<>(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); s.pop(); System.out.println(s.peek()); if(s.empty()){ System.out.println("栈空"); }else{ System.out.println("栈不空,元素个数为:"+s.size()); } }//结果: 4 3 栈不空,元素个数为:3
使用栈将递归转化为循环:
// 递归方式 void printList(Node node){ if(null != node){ printList(node.next); System.out.print(node.val + " "); } } // 循环方式 void printList(Node node){ if(null == node){ return; } Stack s = new Stack<>();// 将链表中的结点保存在栈中 Node cur = node; while(null != cur){ s.push(cur); cur = cur.next; }// 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); } }
1. 括号匹配(LeetCode20)有效的括号
可以进入上面链接查看题目
方法:
1. 依次拿到字符串的元素,如果该元素是左括号,则入栈
2. 如果不是左括号,先判断栈是否为空,如果为空则返回false,如果不为空则进行后续操作
3. 拿到栈顶的元素与前面所拿到字符串的元素作比较,如果括号匹配,则栈顶元素出栈,结束当前循环,继续进行后续比较,如果括号不匹配,则返回false
4. 当字符串的元素比较完后,判断栈是否有剩余,如果有剩余,则返回false,无剩余则返回true
参考代码:
class Solution { public boolean isValid(String s) { Stack stack = new Stack<>(); for(int i=0;i
2.逆波兰表达式求值(LeetCode150)逆波兰表达式求值
可以进入上面链接查看题目
方法:
1. 依次将字符串入栈,如果字符串不是算数符号,则入栈
2. 当字符串是算数符号的时候,取栈顶的两个元素进行算数运算
3. 将运算的结果继续入栈
4. 依次进行上述循环
5. 最后返回栈顶元素的值,即所求逆波兰表达式的值
参考代码:
class Solution { public int evalRPN(String[] tokens) { Stack s = new Stack<>(); for(String e : tokens){ if(!(e.equals("+")||e.equals("-")||e.equals("*")||e.equals("/"))){ s.push(Integer.parseInt(e));//将字符e转为整型 }else{ int right = s.pop(); int left = s.pop(); switch(e) { case "+": s.push(left+right); break; case "-": s.push(left-right); break; case "*": s.push(left*right); break; case "/": s.push(left/right); break; } } } return s.peek(); }}
3. 出栈入栈次序匹配(JZ31)栈的压入、弹出序列
方法:
1. 当入栈序列的元素小于出栈序列的第一个元素,将入栈序列的元素依次入栈
2. 每入栈一个元素,入栈序列的下标加1
3. 当入栈序列的元素与出栈序列的元素相等时,进行出栈,并且出栈序列下标加1
4. 当出栈序列的元素遍历完后,返回true
参考代码:
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack s = new Stack<>(); int inIndex = 0; int outIndex = 0; while(outIndex
public class MyStack { E[] array; int size; public MyStack(){ array = (E[])new Object[3]; } public E push(E e){ ensureCapacity(); array[size++] = e; return e; } public E pop(){ E e = peek(); size--; return e; } public E peek(){ if(empty()){ throw new RuntimeException("栈为空,无法获取栈顶元素"); } return array[size-1]; } public int size(){ return size; } public boolean empty(){ return 0 == size; } private void ensureCapacity(){ if(size == array.length){ array = Arrays.copyOf(array, size*2); } }}
栈:一种后进先出的数据结构,继承自Vector
虚拟机栈:具有特殊作用的一块内存空间。栈区:是线程私有的,存放的是函数调用相关信息,主要是栈帧,它是按照数据结构中栈的特性来实现的
栈帧:一种结构,与函数调用相关。内部:局部变量表,操作数栈。每个方法运行时JVM会创建一个栈帧,然后将栈帧压到虚拟机栈中,调用结束时,该方法对应的栈帧会从虚拟机栈中出栈。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123153.html
摘要:题目根据逆波兰表示法,求表达式的值。给定逆波兰表达式总是有效的。逆波兰表达式又叫做后缀表达式。解题思路可以看出逆波兰表达式中的每一个运算符属于该运算符前的两个数字间的运算。如如波兰表达式则加号前两个数字为。 题目: 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 Evaluate the value of...
摘要:小鹿题目根据逆波兰表示法,求表达式的值。给定逆波兰表达式总是有效的。算法思路仔细观察上述的逆波兰表达式,可以发现一个规律就是每遇到一个操作符,就将操作符前的两个操作数进行运算,将结果保存到原位置。 Time:2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 题目:Evaluate ...
摘要:一实现一个栈类基于堆栈的特性,可以用数组做线性表进行存储。出栈出栈同样是利用数组的方法,在数组尾部推出数据。聚合最后,将所有功能聚合后,如下所示,一个堆栈的数据结构就搞定了。堆栈的经典算法应用,首推就是汉诺塔。 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。 一、实现一个栈类Stack 基于堆...
阅读 924·2021-11-23 09:51
阅读 1097·2021-11-12 10:35
阅读 893·2021-10-18 13:31
阅读 3629·2021-09-23 11:20
阅读 2562·2021-09-22 16:06
阅读 3797·2021-09-10 11:19
阅读 2083·2019-08-29 17:04
阅读 277·2019-08-29 10:55