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