java数据结构之栈的详解

时间:2022-11-05 23:43:28

一、栈

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