java數(shù)據(jù)結構之棧的詳解

更新時間：2021年08月16日 10:12:55 作者：caiyec

這篇文章主要為大家詳細介紹了Java數(shù)據(jù)結構的棧的應用，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助

一、棧

棧的特性就是先進后出，常用方法是入棧（push()）,出棧(pop()),棧空（empty()）,看棧頂元素（peek()）;

1.棧的應用

1.1括號匹配

 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+

轉換方式就是每一個表達式用括號括起，將兩個表達式中間的運算符放到括號外，加括號的順序就是先乘除后加減

逆波蘭表達式求值：這里是后綴表達式，所以減法就是后出的減先出的，除法也是。利用棧的特性來實現(xiàn)后綴表達式

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用棧實現(xiàn)隊列

用棧模擬出隊列的push(),pop(),peek(),empty() 方法

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最小棧

class MinStack {
    //定義雙棧來實現(xiàn)最小棧
    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棧的壓入和彈出序列

先看題目要求：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，第二個序列表示棧的彈出序列，請判斷是否為合法的出棧序列

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();
    }