棧
在刷算法題中，棧是一種常用的資料結構。下面介紹一些Java中棧的常用的一些方法以及力扣刷題中用到棧的一些題目。
Java Stack類，棧是Vector的一個子類，實作後進先出的棧。
使用Stack類，由于Stack繼承了Vector接口，而Vector底層是一個Object[]數組，那麼就要考慮空間擴容和移位的問題，造成速度較慢，可以使用LinkedList來做Stack的容器。
1.棧的函數
Stack<Integer> stack = new Stack<Integer>();//建棧
stack.push(Element);//進棧
stack.pop();//出棧
stack.peek();//取棧頂值（不出棧）
stack.isEmpty();//判斷棧是否為空
2.力扣關于棧的題
1）劍指offer09：用兩個棧實作隊列
題目：用兩個棧實作一個隊列。隊列的聲明如下，請實作它的兩個函數 appendTail 和 deleteHead ，分别完成在隊列尾部插入整數和在隊列頭部删除整數的功能。(若隊列中沒有元素，deleteHead 操作傳回 -1 )
解題思路：用兩個棧，一個棧将輸入的數存入棧中，再出棧存到另一個棧中，再出棧的時候就實作了隊列的先進先出。
算法代碼：
class CQueue {
private Stack StackA;
private Stack StackB;
public CQueue() { //建立棧
StackA = new Stack();
StackB = new Stack();
}
public void appendTail(int value) { //入隊，進棧
StackA.push(value);
}
public int deleteHead() {
if(StackB.empty()){
while(!StackA.empty()){ //将棧A中的數都存到棧B中
StackB.push(StackA.pop());
}
}
if(StackB.empty()) return -1;
else return (int)StackB.pop();
}
}
2）劍指offer31：棧的壓入，彈出序列
題目：輸入兩個整數序列，第一個序清單示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列，但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。
解題思路：輔助棧，判斷棧頂元素與輸出序列是否相同，相同則出棧，最後判斷棧是否為空。
算法代碼：
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stackA = new Stack();
int in=0;
for(int i=0;i<pushed.length;i++){
stackA.push(pushed[i]); //進棧
while(!stackA.isEmpty() && stackA.peek()==popped[in]){
//棧頂元素等于出棧序列元素,出棧
stackA.pop();
in++;
}
}
return stackA.isEmpty();//根據棧是否為空，判斷
}
}
3）劍指offer30：包含min函數的棧。
題目：定義棧的資料結構，請在該類型中實作一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間複雜度都是 O(1)。
解題思路：建立兩個輔助棧。
- 輔助棧A：用于存儲所有元素，保證入棧push()函數、出棧pop()函數，擷取棧頂top()函數的正常邏輯。
- 輔助棧B：存儲棧A中所有非嚴格降序的元素，則棧A中的最小元素始終對應棧B的棧頂元素。
算法代碼：
class MinStack {
Stack<Integer> stackA, stackB;
public MinStack() {
stackA = new Stack<>();
stackB = new Stack<>();
}
public void push(int x) {
stackA.add(x);
if(stackB.empty()||stackB.peek()>=x)
stackB.add(x);
}
public void pop() {
if(stackA.pop().equals(stackB.peek())) //比較的同時，先執行stackA.pop()
stackB.pop();
}
public int top() {
return stackA.peek();
}
public int min() {
return stackB.peek();
}
}
隊列
LinkedList類實作了Queue接口，是以我們可以把LinkedList當成Queue來用。
1.隊列的函數
添加：queue.offer() queue.add()
删除隊列第一個元素：queue.poll()傳回null queue.remove()傳回異常
查詢隊列頭部元素：peek()傳回null element()傳回異常
2.力扣關于隊列的題
待補充
堆
堆主要介紹PriorityQueue實作的堆。
PriorityQueue，即優先隊列。優先隊列的作用是能保證每次取出的元素都是隊列中權值最小的。堆保證每次插入都排好序。
Java中PriorityQueue預設是小頂堆，可以通過傳入自定義的Comparator函數來實作大頂堆。
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
public int compare(Integer n1, Integer n2){
return n2-n1;
}
});
1.優先隊列實作的堆的函數
建立：PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>()
add()和offer() 向優先隊列中插入元素
element()和peek() 擷取但不删除隊首元素
remove()和poll() 擷取并删除隊首元素
2.力扣關于堆的題
1）劍指offer40：最小的k個數
題目：輸入整數數組 arr ，找出其中最小的 k 個數。例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。
解題思路：使用大頂堆，先将前k個元素加入大頂堆，然後周遊其餘元素，若小于堆頂，則加入堆，最後輸出堆。
算法代碼：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if(k==0) return res;
//将小頂堆改為大頂堆，通過comparator函數
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
public int compare(Integer n1, Integer n2){
return n2-n1;
}
});
for(int i=0;i<k;i++) queue.offer(arr[i]); //将數組前k個元素加入大頂堆
for(int i=k;i<arr.length;i++){ //周遊其餘元素，若小于堆頂，則加入堆
if(queue.peek()>arr[i]){
queue.poll();
queue.offer(arr[i]);
}
}
for(int i=0;i<k;i++) res[i]=queue.poll(); //将周遊完的大頂堆中元素存入數組
return res;
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)