目錄

一、堆疊的基本概念區分

二、堆疊的常見操作以及常見題型考查

一、堆疊的基本概念區分

什么是堆疊？

堆疊實際上是一種資料結構，特點是后進先出

什么是Java虛擬堆疊 ？

此時，Java虛擬機堆疊只是JVM中的一塊記憶體，該記憶體一般用來存放，例如：區域變數

什么是堆疊幀 ？

呼叫函式的時候，我們會為這個函式在JVM虛擬機堆疊中開辟一塊記憶體叫做堆疊幀

二、堆疊的常見操作以及常見題型考查

1.堆疊的常見操作

1.對常見操作進行測驗：

import java.util.*;

public class TestDemo {
    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        //入堆疊
        stack.push(1);
        stack.push(2);
        System.out.println(stack);
        //查看堆疊頂元素
        System.out.println(stack.peek());
        System.out.println(stack);
        //出堆疊
        System.out.println(stack.pop());
        System.out.println(stack);
        System.out.println(stack.isEmpty());
    }

}

注意：stack.pop() 的操作是出堆疊堆疊頂元素，此后堆疊頂元素將不復存在

而stack.peek()的操作是查看堆疊頂元素，此后該堆疊頂元素依舊存在

2.自己動手操作實作堆疊

由原始碼判斷出堆疊的底層為陣列：

import java.util.*;

//自己實作堆疊
public class MyStack {
public int[] elem;
//判斷放入的個數，即容量的大小
public int usedSize;
public MyStack(){
    this.elem=new int[5];
}
//關于入堆疊
public void push(int val){
    //第一步，判斷是否滿堆疊
    if(isFull()){
        //擴容
        Arrays.copyOf(this.elem,2*this.elem.length);
    }
    this.elem[this.usedSize]=val;
    this.usedSize++;
}
public boolean isFull(){
    return this.usedSize==this.elem.length;
}
//出堆疊
public int pop(){
    if(isEmpty()){
        throw new RuntimeException("堆疊為空")；
    }
    int oldVal=this.elem[usedSize-1];
    this.usedSize--;
    return oldVal;
}
//獲取堆疊頂元素
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("堆疊為空");
        }
        return this.elem[usedSize-1];
    }
    public boolean isEmpty(){
    return this.usedSize==0;
}
}

在出堆疊時注意是參考還是非參考型別

第一類：關于入堆疊和出堆疊的題目

決議要點：

①第一步查看首元素，確定入堆疊序列

②不熟悉地話建議畫出堆疊圖進行理解

代碼解決：堆疊的壓入、彈出序列_牛客題霸_牛客網 (nowcoder.com)https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer>stack=new Stack<>();
        int j=0;
      for(int i=0;i<pushA.length;i++){
          stack.push(pushA[i]);
         while(j<popA.length&&(!stack.empty())&&stack.peek()==popA[j]){
              stack.pop();
              j++;
          }

    }return stack.empty();
    }
}

第二類：中綴運算式轉后綴運算式（逆波蘭運算式）

簡易解題思想：加括號

eg.（5+4）*3-2

①將每個運算子所在的運算式加上括號至最外一層

(((5+4)*3)-2)

②將所有符號移至相對應括號外

（((54)+3)*2)-

③數字順序不變，去掉括號

54+3*2-

思考？？？如何通過后綴運算式計算一個值呢？？？

利用堆疊

解題思路：

①當i指向數字時，入堆疊數字，當i指向運算子時，將入堆疊的數字分別放于其左右

②回圈上述步驟

代碼實作：150. 逆波蘭運算式求值 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < tokens.length;i++) {
            String val = tokens[i];
            if(isOperation(val) == false) {
                //如果不是運算子
                stack.push(Integer.parseInt(val));
            }else {
                //到底是什么運算子
                  int num2 = stack.pop();
                  int num1 = stack.pop();
                switch(val) {
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperation(String x) {
        if(x.equals("+") || x.equals("-") ||x.equals("*") ||x.equals("/")) {
            return true;
        }
        return false;
    }
}

第三類：

經典題目之有效的括號

20. 有效的括號 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/valid-parentheses/

class Solution {
    public boolean isValid(String s) {
        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()){
                    //右括號多
                    System.out.println("右括號多");
                    return false;
                }
                char top=stack.peek();//哪個左括號
                if(top=='{' && ch=='}'||top=='(' && ch==')'||top=='[' && ch==']'){
                    stack.pop();
                }else{
                    //左右括號不匹配
                    System.out.println("左右括號不匹配");
                    return false;
                }
                
            }
        }
        if(!stack.empty()){
            //左括號多
            System.out.println("左括號多");
            return false;
        }
    return true;
    }
}

經典題目之最小堆疊155. 最小堆疊 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/min-stack/解題思路：

相關代碼：

class MinStack {
    private Stack<Integer>stack;
     private Stack<Integer>minStack;
    

    public MinStack() {
           stack=new Stack<>();
           minStack=new Stack<>();
    }
    
    public void push(int val) {
      stack.push(val);
      if(!minStack.empty()){
          int top=minStack.peek();
          if(top>=val){
              minStack.push(val);
          }
      }else{
      minStack.push(val);
    }
    }
    public void pop() {
int popVal=stack.pop();
if(!minStack.empty()){
    int top=minStack.peek();
if(popVal==top){
    minStack.pop();
}

    }
    }
    public int top() {
return stack.peek();
    }
    
    public int getMin() {
return minStack.peek();
    }
}