一、栈
栈的特性就是先进后出,常用方法是入栈(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