Java數據結構—

Stack

棧的概念和使用
- 棧的概念
- 棧的使用
棧的應用
- 出棧元素序列
- 有效的括號
- 棧的壓入、彈出序列
- 逆波蘭表達式
- 最小棧

棧的概念和使用

棧的概念

棧(Stack)：一種特殊的線性表，只允許再棧的一端進行插入和刪除元素，這一端點被稱為棧頂，另一端就是棧頂
棧中有兩種使用：
入棧(push)：插入數據進入棧中，入棧在棧頂
出棧(pop)：刪除棧中數據，出的是棧頂的數據
遵循的是先入后出的原則

在這里插入圖片描述

棧的使用

方法	功能
Stack()	構造空的棧
E push(E e)	將e入棧，返回e
E pop()	將棧頂元素取出
E peek()	獲取棧頂元素
int size()	棧的有效元素個數
boolean empty()	判斷棧是否為空

E push(E e) 將e入棧，返回e

public class Test {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(10);System.out.println(stack);}
}

運行結果如下
在這里插入圖片描述

E pop() 將棧頂元素取出
E peek() 獲取棧頂元素

public class Test {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(10);System.out.println(stack);int ret = stack.pop();//10 ,取出棧頂元素int ret1 = stack.peek();//2 //獲取棧頂元素是多少System.out.println(ret);System.out.println(ret1);System.out.println("出棧后"+stack);//出棧后，棧中數據 1 2}
}

這里的pop是出棧的意思，而peek()只是獲取其棧頂元素，并不是出棧，不會影響棧中元素
所以這里會取出棧頂元素10 而在獲取棧頂元素是2，最終棧中元素是1 2
在這里插入圖片描述

int size() 棧的有效元素個數
boolean empty() 判斷棧是否為空

public class Test {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(5);stack.push(11);System.out.println(stack.size());//棧的元素個數 5 System.out.println(stack.empty());//這里棧不為空，false}
}

在這里插入圖片描述

棧的應用

出棧元素序列

題目：若進棧序列為 1,2,3,4 ，進棧過程中可以出棧，則下列不可能的?個出棧序列是（）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
答案是 C
A ：如果是1進棧，1出棧，在將1 2 3放入進去再出棧，這樣出棧結果就1 4 3 2
B: 1進棧，先不出來，2 3 4依次進棧后就出棧，這樣結果出棧結果為 2 3 4 1
C: 先出3 說明 1 2 3已經進棧了，3 出棧 2就是棧頂，不可以直接出1，所以錯誤
D 1 2 進棧，3 4分別進棧后出棧，最后出棧2 1結果為 3 4 2 1
在這里插入圖片描述
C選項錯誤，所以選C

有效的括號

目的：括號是否可以左右匹配成功 “()” 或者 "([ ])"類型的都是匹配成功
思路：1創建一個Character類型的棧
2.如果遇到左邊括號就將其放入棧中，遇到右括號就與棧頂括號元素進行匹配，匹配不成功就直接返回false，匹配成功就繼續向后匹配,入棧重復操作
3 在匹配的時候，如果棧為空，返回false
4.最后右括號匹配完成，但是棧不為空也返回false

1.這里再進行匹配的時候如果棧為空說明沒有其右括號左邊沒有左括號入棧
2.如果匹配失敗直接
3.最后字符串遍歷完了，但是不為空，說明棧中的左括號沒有全部匹配
這上面三種情況不符合要求直接返回false

class Solution {public boolean isValid(String s) {//創建一個Character的棧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{//匹配//1.判斷棧是否為空if(stack.empty()){return false;}//2.出棧進行匹配char ch2 = stack.peek();if(ch2=='('&&ch==')'||ch2=='['&&ch==']'||ch2=='{'&&ch=='}'){stack.pop();}else{//不匹配return false;}}}//最后如果棧不為空，說明還有沒匹配的if(!stack.empty()){return false;}return true;}
}

棧的壓入、彈出序列

目的：有一個所有數都不相同的pushV數組壓棧順序，有一個和壓棧的數相同出棧順序，判斷這個出棧順序是否正確
思路：1.遍歷這個pushV，將其元素進行入棧，2.并進行判斷，棧頂元素是否與出棧順序相同，相同就出棧，不相同就繼續入棧，繼續判斷，重復操作
最后遍歷完整個pushV數組，如果棧為空，說明其出棧順序正確

1.這里的進行棧頂元素與popV判斷明顯是個while循環，因為可能連續出棧
2.并且這個循環不僅要判斷是否相同也要注意棧不為空再進行判斷
3.遍歷完整個pushV數組后，最后如果棧為空說明出棧順序是對的返回true，反之是false

import java.util.*;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++){//入棧stack.push(pushV[i]);//根據給出彈出的序列看看是否要出棧while(!stack.empty()&&stack.peek()==popV[j]){j++;stack.pop();//出棧}}//如果最后stack為空，說明成功了return stack.empty();}
}

逆波蘭表達式

逆波蘭式

目的：給一個逆波蘭表達式，求出其結果
思路：使用棧進行計算，遇到數字就入棧，反之就是運算符，就要出棧進行計算

1.這里就是遇到數字字符就進行入棧，這里注意將數字字符轉為數字，
2.遇到運算符就要計算，將計算結果入棧
3.最后返回棧頂數據就是計算結果

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for(String str: tokens){if(!isOperator(str)){stack.push(Integer.valueOf(str));//轉換為數字入棧}else{//反之就出棧計算//將計算結果入棧int val1 = stack.pop();int val2 = stack.pop();switch(str){case "+":stack.push(val2+val1);break;case "-":stack.push(val2-val1);break;case "*":stack.push(val2*val1);break;case "/":stack.push(val2/val1);break;}}}return stack.pop();}//判斷是不是運算符private boolean  isOperator(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}
}

最小棧

在這里插入圖片描述

目的：獲取其棧中最小元素
思路：就是創建兩個棧，1.正常棧一個棧是正常將所有元素依靠順序入棧，出棧
2.最小棧用來放棧中最小元素，棧頂是最小元素，這樣獲取最小元素的效率是O(1)

在這里插入圖片描述

注意這里在入棧的時候也要將和最小棧相同的元素也要放入進去
出棧的時候，也要注意棧的最小元素可能發生變化，最小棧可能也要出棧
這時候無論如何，最小棧棧頂就是棧中最小的元素

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {//將=最小棧頂元素的值也要放入最小棧if(minStack.empty()||val<=minStack.peek()){minStack.push(val);}stack.push(val);}public void pop() {//注意這里如果出棧的話，最小值可能發生變化if(stack.peek().equals(minStack.peek())){minStack.pop();}stack.pop();}public int top() {return stack.peek();  }public int getMin() {return minStack.peek();}
}