一. 棧(Stack)

1.1 概念

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。

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

1.2 棧的使用

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());   // 獲取棧中有效元素個數---> 4System.out.println(s.peek());   // 獲取棧頂元素---> 4s.pop();   // 4出棧，棧中剩余1   2   3，棧頂元素為3System.out.println(s.pop());   // 3出棧，棧中剩余1  2   棧頂元素為3if(s.empty()){System.out.println("棧空");}else{System.out.println(s.size());}}

1.3 棧的模擬實現

Stack繼承了Vector，Vector和ArrayList類似，都是動態的順序表

1.3.1 順序表結構

public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}
}

1.3.2 進棧 壓棧

 public void push(int val) {if(isFull()) {this.elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = val;}public boolean isFull() {return usedSize == elem.length;}

1.3.3 刪除棧頂元素

public int pop() {if(isEmpty()) {throw new EmptyStackException();}int val = elem[usedSize-1];usedSize--;return val;}

1.3.4 獲取棧頂元素

 public int peek() {if(isEmpty()) {throw new EmptyStackException();}return elem[usedSize-1];}public boolean isEmpty() {return usedSize == 0;}

1.3.5 自定義異常

public class EmptyStackException extends RuntimeException{public EmptyStackException() {}public EmptyStackException(String message) {super(message);}
}

完整代碼:

public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}public void push(int val) {if(isFull()) {this.elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = val;}public boolean isFull() {return usedSize == elem.length;}public int pop() {if(isEmpty()) {throw new EmptyStackException();}int val = elem[usedSize-1];usedSize--;return val;}//獲取棧頂元素 但是不刪除public int peek() {if(isEmpty()) {throw new EmptyStackException();}return elem[usedSize-1];}public boolean isEmpty() {return usedSize == 0;}
}

1.4 棧的應用場景

1.改變元素序列

2. 將遞歸轉化為循環

逆序打印鏈表

// 遞歸方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}// 循環方式
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 將鏈表中的結點保存在棧中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 將棧中的元素出棧while(!s.empty()){System.out.print(s.pop().val + " ");}
}

3. 四道習題

都是力扣牛客網上的題目,也是常見的面試題,會在刷題專欄詳細講解

1.5 概念分區

棧 虛擬機棧 棧幀有什么區別?

• 棧是一種通用的數據結構概念，而虛擬機棧是在 Java 虛擬機環境下對棧這種數據結構的具體應用
• 虛擬機棧由多個棧幀組成，每個棧幀對應一個方法的調用。當方法調用開始時，會創建一個新的棧幀并壓入虛擬機棧；當方法調用結束時，對應的棧幀會從虛擬機棧中彈出
• 綜上所述,棧是一種抽象的數據結構，虛擬機棧是 JVM 中使用棧結構來管理方法調用的具體實現，而棧幀則是虛擬機棧中用于支持單個方法執行的具體數據結構

二. 隊列(Queue)

2.1 概念

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 入隊列：進行插入操作的一端稱為隊尾（Tail/Rear） 出隊列：進行刪除操作的一段稱為隊頭（Head/Front）

2.2 隊列的使用

在Java中，Queue是個接口，底層是通過鏈表實現的

每個方法都有一個類似的方法
從效果上沒有區別

注意：Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現了Queue接口

LinkedList實現的方法是很多的,可以直接拿來用
那就要這樣寫了:

LinkedList <Integer> q = new LinkedList<>();

2.3 隊列模擬實現

隊列中既然可以存儲元素，那底層肯定要有能夠保存元素的空間，通過前面線性表的學習了解到常見的空間類型有兩種：順序結構 和 鏈式結構

隊列的實現使用順序結構還是鏈式結構好？

我們先說鏈式結構:


雙向鏈表實現隊列

 static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode first=null;public ListNode last=null;public int useSize=0;public void offer(int val){//addLast尾插ListNode node=new ListNode(val);if(isEmpty()){first=last=null;}last.next=node;node.prev=last;last=last.next;useSize++;}public int poll(){//頭刪if(isEmpty()){return -1;}int val= first.val;//隊頭的數據first=first.next;if(first!=null){//只剩一個節點 直接useSize--first.prev=null;}useSize--;return 0;}public int peek(){//獲取隊頭元素if(first==null){return -1;}return first.val;}public boolean isEmpty(){return useSize==0;}

雙向鏈表實現隊列效率很高 刪除 插入都很方便

如果是數組實現隊列該如何實現?

其實按照順序遍歷插入刪除 可以實現,但是數組的遍歷 一旦往后走就無法回去 被刪除的空間沒辦法再次使用了

如果數組是一個環就好了,這樣就可以走回去再次使用空間–這就是循環隊列

2.4 循環隊列

我們有時還會使用一種隊列叫循環隊列。如操作系統課程講解生產者消費者模型時可能就會使用循環隊列。環形隊列通常使用數組實現。

上面兩個一個是空的環形隊列 一個是滿的環形隊列

實現環形隊列兩個問題:
1.怎么判斷空和滿?
2.rear 和 front 下標從7到0怎么做到的?

解答:
空:只要front 和 rear 相遇就是空的
滿 有三種方法判斷
1.定義size size=數組長度就是滿
2.添加標記 boolean類型元素 一開始是false一旦開始添加元素就變為true
3.浪費一個空間 判斷rear是不是front

先放入元素 再rear++ 判斷rear的下一個元素是不是front就可以了

判斷 rear=(rear+1)%len

關于這個公式:

數組下標循環的小技巧

利用取模運算得到下標

好了,解決了這兩個問題,我們可以使用循環隊列了,正好我們來看一道設計循環隊列的題目

設計循環隊列

設計循環隊列

class MyCircularQueue {//數組實現public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {//使用浪費一個空間的方法來判斷隊列是否滿//數組多給一個空間elem=new int[k+1];}public boolean enQueue(int value) {//插入 判滿if(isFull()){return false;}elem[rear]=value;rear =(rear+1)%elem.length;return true;}public boolean deQueue() {//刪除 判空if(isEmpty()){return false;}//頭向后走 因為是環形的所以 向后走也不用擔心前面的空間不能使用了front=(front+1)%elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return-1;}//return elem[rear];}public boolean isEmpty() {return rear==front;}public boolean isFull() {//rear 的下一個是 frontreturn (rear+1)%elem.length==front;}
}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/

如果是這樣寫示例測到這里會有一個報錯
原因在于我們并沒有考慮 最重要的一點
rear 從尾到頭 怎么辦 front刪除是向后走了 rear等于0 是可以的
rear 的下一個確實不是front 可以等于0

正確代碼如下:

class MyCircularQueue {//數組實現public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {//使用浪費一個空間的方法來判斷隊列是否滿//數組多給一個空間elem=new int[k+1];}public boolean enQueue(int value) {//插入 判滿if(isFull()){return false;}elem[rear]=value;rear =(rear+1)%elem.length;return true;}public boolean deQueue() {//刪除 判空if(isEmpty()){return false;}//頭向后走 因為是環形的所以 向后走也不用擔心前面的空間不能使用了front=(front+1)%elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return-1;}//int index=(rear==0)?elem.length-1:rear-1;return elem[index];}public boolean isEmpty() {return rear==front;}public boolean isFull() {//rear 的下一個是 frontreturn (rear+1)%elem.length==front;}
}

三. 雙端隊列 (Deque)

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊

Deque是一個接口，使用時必須創建LinkedList的對象
在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口

再來看一下我們數據結構第一篇文章畫的圖,想打關一樣,已經學完這么多了

兩種使用方式

Deque<Integer> stack = new ArrayDeque<>();//雙端隊列的線性實現
Deque<Integer> queue = new LinkedList<>();//雙端隊列的鏈式實現

四. 兩道面試題

4.1 用隊列實現棧

隊列實現棧

class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1=new LinkedList<>();qu2=new LinkedList<>();}//入棧public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}//出棧public int pop() {if(empty()){return-1;}else if(!qu1.isEmpty()){ // 1不是空 將1的size-1個元素放到2for(int i=0;i<qu1.size()-1;i++){qu2.offer(qu1.poll());}return qu1.poll();}else{//2 不為空for(int i=0;i<qu2.size()-1;i++){qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if(empty()){return-1;}//用一個臨時變量 把每個刪除的都記錄一下,最后一個就是棧頂if(!qu1.isEmpty()){ // 1不是空 將1的size-1個元素放到2int val=0;for(int i=0;i<qu1.size();i++){val=qu1.poll();qu2.offer(val);}return val;}else{//2 不為空int val=0;for(int i=0;i<qu2.size();i++){val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty()&&qu2.isEmpty();}
}

正確代碼:

class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1=new LinkedList<>();qu2=new LinkedList<>();}//入棧public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}//出棧public int pop() {if(empty()){return-1;}else if(!qu1.isEmpty()){ // 1不是空 將1的size-1個元素放到2int size=qu1.size();for(int i=0;i<size-1;i++){qu2.offer(qu1.poll());}return qu1.poll();}else{//2 不為空int size=qu2.size();for(int i=0;i<size-1;i++){qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if(empty()){return-1;}//用一個臨時變量 把每個刪除的都記錄一下,最后一個就是棧頂if(!qu1.isEmpty()){ // 1不是空 將1的size-1個元素放到2int size=qu1.size();int val=0;for(int i=0;i<size;i++){val=qu1.poll();qu2.offer(val);}return val;}else{//2 不為空int size=qu2.size();int val=0;for(int i=0;i<size;i++){val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty()&&qu2.isEmpty();}
}

4.2 用棧實現隊列

按照我們畫圖得到的思路,寫代碼:

class MyQueue {
// 兩個棧
public ArrayDeque<Integer> s1;
public ArrayDeque<Integer> s2;public MyQueue() {s1=new ArrayDeque<>();s2=new ArrayDeque<>();}public void push(int x) {//入隊s1.push(x);}public int pop() {if(empty()){return -1;}if(s2.isEmpty()){while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}public int peek() {if(empty()){return -1;}if(s2.isEmpty()){while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty()&&s2.isEmpty();}
}