首页 > 基础资料 博客日记
【Java--数据结构】栈的应用
2024-08-04 06:00:06基础资料围观168次
文章【Java--数据结构】栈的应用分享给大家，欢迎收藏Java资料网，专注分享技术知识
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
将递归转化为循环
把递归代码实现为非递归代码
比如：逆序打印链表
// 递归方式
void printList(Node head){
if(null != head){
printList(head.next);
System.out.print(head.val + " ");
}
}
// 循环方式
void printList(Node head){
if(null == head){
return;
}
Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中
Node cur = head;
while(null != cur){
s.push(cur);
cur = cur.next;
}逆波兰表达式
也叫后缀表达式（运算符在操作数的后面）,好处是：忽略运算符的优先级
我们平时运算加减乘除的式子其实是 中缀表达式
比如式子a+b*c+(d*e+f)*g转成逆波兰表达式 abc*+de*f+g*+
逆波兰表达式的运算规则：
- 将操作数压入栈中
- 遇到运算符弹出操作数（分别作为右操作数和左操作数）计算
- 将计算的结果压入栈中
比如式子1+2*3+（4*5+6）*7
逆波兰表达式1 2 3*4 5*6 +7 *+
- 将1 2 3压入栈内，
- 遇到*，取出2和3，计算2*3得6
- 将6压入栈
- 又遇到+，取出6和1，计算6+1得7
……
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。oj链接
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack=new Stack<>();
for(int i=0;i<tokens.length;i++){
String tmp=tokens[i];
if(!isOperation(tokens[i])){
Integer val=Integer.valueOf(tmp);//将字符转化为整形
stack.push(val);
}else{
Integer val2=stack.pop();//val2作为右操作数
Integer val1=stack.pop();
switch(tmp){
case "+":
stack.push(val1+val2);
break;
case "-":
stack.push(val1-val2);
break;
case "*":
stack.push(val1*val2);
break;
case "/":
stack.push(val1/val2);
break;
}
}
}
return stack.pop();
}
//判断字符是否是 运算符
public boolean isOperation(String s){
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
return true;
}
return false;
}
}有效的括号
括号匹配：栈最终为空，且字符串已经遍历完了
不匹配：
- 左括号与右括号不匹配 [ ( ] )
- 字符串没有遍历完，遇到了右括号，但栈为空 ( ) ）））
- 字符串遍历完，但栈里还有左括号（（（ ）
- 右括号在前面 ）（（
class Solution {
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;//栈为空，没有左括号与之匹配
}else{
//取栈顶元素左括号 看与当前右括号是否匹配
char chL=stack.peek();
if(chL=='('&&ch==')'
||chL=='['&&ch==']'
||chL=='{'&&ch=='}'){
stack.pop();//说明当前这个括号匹配，所以要扔出去
}else{
return false;
}
}
}
}
return stack.empty();//如果循环走完，栈为空，返回真
}
}栈得压入、弹出系列
1. 遍历pushV数组，入栈，每次入栈后判断和popV数组的下标j是否一致
2.不一样,继续i++（继续进栈）；
一样,出栈，j++
3.出栈时，若一直一样就一直出，遇到不一样的，i++继续入栈；
注意：
- j的条件：不能越界（超过popV的长度）
- 栈不能为空
stack.peek()==popV[j] 引用类型时要用equals判断，这里为简单类型int.
public boolean IsPopOrder (int[] pushV, int[] popV) {
// write code here
Stack<Integer> stack=new Stack<>();
int j=0;
for(int i=0;i<pushV.length;i++){
stack.push(pushV[i]);
while(j<popV.length&&!stack.empty()&&
stack.peek()==popV[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
}最小栈
分别创建两个栈：普通栈 和 最小栈
push存放元素的过程：
- 如果是第一次存放元素，普通栈和最小栈都得存放元素；
- 如果不是第一次存放，普通栈里放，需要比较的普通栈的栈顶元素和最小栈的，只有小于等于才能放入最小栈里。
pop取元素的过程（返回值是普通站的元素）：
每次pop元素时需要判断出栈的元素是不是和最小栈的栈顶元素一样，若一样，最小栈也得pop
top瞄一眼（相当于peek，返回的是普通栈的值）
getMin获取最小栈的栈顶元素
import java.util.Stack;
class MinStack {
public Stack<Integer> stack;
public Stack<Integer> minStack;
public MinStack() {
stack=new Stack<>();
minStack=new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.empty()){
minStack.push(val);
}else{
Integer peekVal=minStack.peek();
if(val<=peekVal){
minStack.push(val);
}
}
}
public void pop() {
if (stack.empty()) {
return;
}
int popVal=stack.pop();
if(popVal==minStack.peek()){
minStack.pop();
}
}
public int top() {
if(stack.empty()){
return -1;
}
return stack.peek();
}
public int getMin() {
if(minStack.empty()){
return -1;
}
return minStack.peek();
}
}文章来源:https://blog.csdn.net/2301_80898480/article/details/140416057
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
相关文章
最新发布
点击排行
本站推荐
