一、栈
栈的特性就是先进后出，常用方法是入栈（push()）,出栈(pop()),栈空（empty()）,看栈顶元素（peek()）;
1.栈的应用
1.1括号匹配
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public boolean isValid(String s) { //有效括号时隔4个月后重新打卡 看看栈学的怎么样 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 ch1=stack.peek(); if(ch1=='{'&&ch=='}'||ch1=='['&&ch==']'||ch1=='('&&ch==')'){ stack.pop(); }else{ return false; } } } } if(!stack.empty()){ return false; } return true; } |
1.2后缀表达式
a+b 这是我们最常见的表达式
前缀表达式就是+ab
后缀表达式就是ab+
转换方式就是每一个表达式用括号括起，将两个表达式中间的运算符放到括号外，加括号的顺序就是先乘除后加减
逆波兰表达式求值：这里是后缀表达式，所以减法就是后出的减先出的，除法也是。利用栈的特性来实现后缀表达式
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public int evalRPN(String[] tokens) { Stack <Integer> stack=new Stack<>(); int num1=0; int num2=0; for(String str:tokens){ if(str.equals("+")){ num1=stack.pop(); num2=stack.pop(); stack.push(num1+num2); }else if(str.equals("-")){ num1=stack.pop(); num2=stack.pop(); stack.push(num2-num1); }else if(str.equals("*")){ num1=stack.pop(); num2=stack.pop(); stack.push(num1*num2); }else if(str.equals("/")){ num1=stack.pop(); num2=stack.pop(); stack.push(num2/num1); }else{ stack.push(Integer.parseInt(str)); } } return stack.pop(); } |
1.3用栈实现队列
用栈模拟出队列的push(),pop(),peek(),empty() 方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class MyQueue { public Stack<Integer> stack1; public Stack<Integer> stack2; /** Initialize your data structure here. */ public MyQueue() { stack1 =new Stack<>(); stack2 =new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } /** Get the front element. */ public int peek() { if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.empty()&&stack2.empty(); }}/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */ |
1.4最小栈
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class MinStack { //定义双栈来实现最小栈 public Deque<Integer> stack1; public Deque<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack1=new LinkedList<Integer>(); minStack=new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack1.push(val); minStack.push(Math.min(val,minStack.peek())); } public void pop() { stack1.pop(); minStack.pop(); } public int top() { return stack1.peek(); } public int getMin() { return minStack.peek(); }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */ |
1.5栈的压入和弹出序列
先看题目要求：输入两个整数序列，第一个序列表示栈的压入顺序，第二个序列表示栈的弹出序列，请判断是否为合法的出栈序列
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public boolean validateStackSequences(int []pushed,int []popped){ Stack <Integer> stack=new Stack<>(); int i=0; for(int num:pushed){ stack.push(num); while(!stack.isEmpty()&&stack.peek()==popped[i]){ i++; stack.pop(); } } return stack.isEmpty(); } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/weixin_51601437/article/details/119218948
