目錄

一、棧的概念

二、棧的基本方法

三、棧的模擬實現?

四、棧的練習

1、括號匹配??

?2、出棧入棧次序匹配

---

一、棧的概念

棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。其特點是數據元素先進后出（先入棧的元素后出棧）。

?入棧與出棧：

入棧：棧的插入操作叫做進棧/壓棧/入棧。入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據在棧頂。

還不太理解的小伙伴可以看看以下圖示：

?

?

二、棧的基本方法

?棧的基本方法有：push()（入棧）、pop()（出棧）、peek()（獲取棧頂元素，不刪除）、empty()（判斷棧是否為空）

三、棧的模擬實現?

?以下的代碼我們默認數據元素是整型。

import java.util.Arrays;public class MyStack {public int[] elem;//存放數據的數組public int usedSize;//當前數據的個數public MyStack() {elem=new int[10];}//入棧public void push(int val){if(isFull()){//滿了就擴容elem= Arrays.copyOf(elem,elem.length*2);}elem[usedSize]=val;usedSize++;}//判斷棧是否滿了private boolean isFull(){return elem.length==usedSize;}//出棧public int pop(){if(isEmpty()){return -1;}int getVal=elem[usedSize-1];usedSize--;return getVal;}//判斷棧是否為空public boolean isEmpty(){return usedSize==0;}//獲取棧頂元素，不刪除public int peek(){if(isEmpty()){return -1;}return elem[usedSize-1];}
}

四、棧的練習

1、括號匹配??

?20. 有效的括號 - 力扣（LeetCode）

題目要求如下：?

?

?解題思路：先創建一個字符類型的棧，再遍歷字符串，如果是左括號就入棧，如果是右括號，就看是否與棧頂元素匹配，不匹配返回false，遍歷結束后看棧是否為空，不為空則返回false（這是為了防止類似于"(((("的情況出現）。

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);//獲取i下標字符if(ch=='('||ch=='{'||ch=='['){//如果是左符號，入棧stack.push(ch);}else{if(stack.empty()){//判斷棧是否為空，為空則返回falsereturn false;}char loop=stack.peek();//判斷左右是否匹配，若不匹配則返回false，否則棧頂元素出棧if(loop=='('&&ch==')'||loop=='['&&ch==']'||loop=='{'&&ch=='}'){stack.pop();}else{return false;}}}//遍歷結束后看棧是否為空，不為空則返回false（這是為了防止類似于"(((("的情況出現）if(!stack.empty()){return false;}return true;}
}

?2、出棧入棧次序匹配

棧的壓入、彈出序列_牛客題霸_牛客網

題目要求如下：?

?

解題思路：創建一個整型棧，遍歷pushV，對每個元素進行入棧操作，再創建一個循環，判斷該元素是否與popV[j]相等，若相等則出棧，移動j下標，當遍歷完pushV后，若棧空，則匹配，反之不匹配。

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param pushV int整型一維數組 * @param popV int整型一維數組 * @return bool布爾型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack=new Stack<>();//創建一個整型棧int j=0;for(int i=0;i<pushV.length;i++){//遍歷pushVstack.push(pushV[i]);//入棧//如果棧頂元素與popV[j]相等，出棧，移動j下標while(j<popV.length&&!stack.empty()&&popV[j]==stack.peek()){stack.pop();j++;}}return stack.empty();}
}

以上便是本篇文章的全部內容，感謝各位看官支持~~~