目錄
棧的概念
棧的使用
?編輯?模擬實現棧
中綴表達式轉后綴表達式
括號匹配
出棧入棧次序匹配
隊列概念
隊列的使用
棧的概念
棧是一種特殊的線性表,其只允許在固定的一端進行插入和刪除元素的操作.進行數據插入和刪除操作的一端稱為棧頂,;另一端稱為棧底.棧中的數據元素遵守先進后出的原則.
壓棧:棧的插入操作叫做壓棧/進棧/入棧,入數據在棧頂.
出棧:棧的刪除操作叫做出棧.出數據在棧頂.
棧的底層是一個動態的數組.因此其中的元素在物理和邏輯上都是連續的.
棧的使用
?模擬實現棧
import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public static final int DEFAULT_SIZE = 10;public MyStack(){this.elem = new int[DEFAULT_SIZE];}/*** 壓棧*/public int push(int val){if (isFull()){elem = Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize] = val;usedSize++;return val;}public boolean isFull(){return usedSize == elem.length;}//出棧public int pop(){if (empty()){throw new MyEmptyStackException("棧為空!");}int ret = elem[usedSize-1];usedSize--;return ret;}public boolean empty(){return usedSize == 0;}public int peek(){if (empty()){throw new MyEmptyStackException("棧為空!");}return elem[usedSize-1];}
}
中綴表達式轉后綴表達式
后綴表達式又叫做逆波蘭式.
快捷的轉換方式:
寫代碼:將后綴表達式123*+45*6+7*+進行計算,求結果.
這類問題就是利用棧.
思路就是遍歷這個表達式,遇到數字就入棧,遇到運算符出棧頂兩個元素,第一個元素作為右操作數,第二個元素作為左操作數.
class?Solution?{
????public?int?evalRPN(String[]?tokens)?{
????????Stack<Integer>?stack?=?new?Stack<>();
????????//遍歷字符串數組,不是運算符就入棧
????????for(String?s:tokens){
????????????if(!isOperations(s)){
????????????????stack.push(Integer.parseInt(s));
????????????}else{
????????????????//是運算符就出棧頂兩個元素
????????????????//第一個元素作為右操作數
????????????????int?num2?=stack.pop();
????????????????//第二個元素作為左操作數
????????????????int?num1?=?stack.pop();
????????????????switch(s){
????????????????????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();
????}
????//判斷是不是運算符
????public?boolean?isOperations(String?s){
????????if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
????????????return?true;
????????}
????????return?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);
????????????if(ch=='('?||?ch=='['?||?ch=='{'){
????????????????stack.push(ch);
????????????}else{
????????????????if(stack.empty()){
????????????????????return?false;
????????????????}
????????????????char?ch2?=?stack.peek();
????????????????if(ch2=='['&&ch==']'?||ch2=='{'&&ch=='}'?||ch2=='('&&ch==')'){
????????????????????stack.pop();
????????????????}else{
????????????????????return?false;
????????????????}
????????????}
????????}
????????if(!stack.empty()){
????????????return?false;
????????}
????????return?true;
????}
}
出棧入棧次序匹配
思路: 用i下標遍歷PushV數組,直接入棧;
入棧之后判斷j下標元素是不是當前入棧的元素,如果是則出棧,j++,并且彈出棧頂元素,彈出之后判斷棧頂元素是不是和j下標元素一樣,一樣則繼續彈出,不一樣則i++.
如果不是就繼續i++.
循環遍歷完之后,棧里還有元素就說明是不匹配的.
public class Solution {
? ? /**
? ? ?* 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
? ? ?*
? ? ?*
? ? ?* @param pushV int整型一維數組
? ? ?* @param popV int整型一維數組
? ? ?* @return bool布爾型
? ? ?*/
? ? public boolean IsPopOrder (int[] pushV, int[] popV) {
? ? ? ? Stack<Integer> stack = new Stack<>();
? ? ? ? int j = 0;//遍歷popV數組
? ? ? ? for(int i=0;i<pushV.length;i++){
? ? ? ? ? ? stack.push(pushV[i]);
? ? ? ? ? ? while(!stack.empty()&&stack.peek()==popV[j]){
? ? ? ? ? ? ? ? stack.pop();
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return stack.empty();
? ? }
}
棧,虛擬機棧和棧幀的區別
棧是一種先進后出的數據結構.
虛擬機棧:是jvm的一塊內存空間.
棧幀:是在調用函數的過程當中,在Java虛擬機棧上開辟的一塊內存.
隊列概念
只允許在一段進行插入數據操作,在另一端進行刪除數據操作的特殊線性表,隊列具有先進先出的特點.入隊列:進行插入操作的一段稱為隊尾.出隊列:進行刪除操作的一端稱為隊頭.
在Java中,Queue是一個接口,低等是通過鏈表實現的.
隊列的使用
Queue是個接口,在實例化時必須實例化LinkedList的對象,因為LinkedList實現了Queue接口.
add方法也是入隊列,它和offer的區別就是add方法在隊列容量有限制的情況下如果沒有可用空間了,就會拋出異常而offer不會.
