---

1.棧

1.1 棧的定義

棧是一種特殊的線性表，其只允許在固定的一段進行數據的插入或者刪除。一般，插入或刪除元素的一端叫棧頂，棧頂的另一端一般叫做棧底。棧中的元素均遵循后進先出(LIFO)的原則。

1.2 棧的使用

棧的常用方法為：

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

public static void main(String[] args) {Stack<Integer> s=new Stack<>();s.push(1);s.push(2);s.push(3);System.out.println("棧的大小為:"+s.size());System.out.println("棧頂元素為:"+s.peek());System.out.println("出棧元素為:"+s.pop());System.out.println("出棧后的棧頂元素為:"+s.peek());s.pop();s.pop();if(s.empty()) {System.out.println("當前棧為空");}
}

1.3 棧的模擬實現

圖中可以看出，Stack繼承了Vector類，Vector和ArrayList類似，都是會動態增長的順序表。

public class MyStack<E> {  private Object[] elem;private int elemSize;//構造方法public MyStack() {}public MyStack(int capacity) {}//元素入棧并返回public E push(E e) {}//元素出棧并返回public E pop() {}//獲取棧頂元素public E peek() {}//獲得棧中元素個數public int size() {}//判斷是否為空棧public boolean empty() {}
}

1.入棧：

public E push(E e) {if(elem.length==elemSize) {this.elem=Arrays.copyOf(elem,2*elem.length);}elem[elemSize++]=e;return e;
}

2.出棧：

public E pop() {if(size()==0) {throw new RuntimeException("棧中不存在元素，無法刪除");}E obj=peek();elemSize--;return obj;
}

3.獲取棧頂元素

public E peek() {int len=size();if(len==0) {throw new RuntimeException("棧中不存在元素");}return (E)elem[len-1];
}

4.判空與獲取大小

//獲得棧中元素個數
public int size() {return elemSize;
}//判斷是否為空棧
public boolean empty() {return elemSize==0;
}

5.測試結果：

2.隊列

2.1 隊列的定義

隊列是一種特殊的線性表。其是只允許在一端進行插入，在另一端進行刪除的結構。

插入端即隊尾(Tail/Rear)，刪除端為隊頭(Head/Front)。對元素的操作遵循先入先出(FIFO)的原則。

2.2 隊列的使用

可以看到，LinkedList類實現了Queue接口，因此需要用LinkedList類來實例化對象；

方法	功能
boolean offer(E e)	將元素入隊
E poll()	隊頭元素出隊并返回該元素
E peek()	獲取隊頭元素
int size()	獲取隊列中的元素個數
boolean isEmpty()	判斷隊列是否為空

public static void main(String[] args) {Queue<Integer> q=new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);  //1,2,3System.out.println(q.poll()); System.out.println(q.peek());System.out.println("隊列為空嗎？"+q.isEmpty());
}

2.3 隊列的模擬實現

隊列的實現既可以用數組也可以用列表實現；雖然在Java中使用鏈表來實現隊列，但其常數時間的并不是很好，因此，如果在刷題，尤其是競賽等場景(數據量確定)，用數組去模擬隊列會是更好的寫法；

這里使用雙端鏈表來模擬實現:

public class MyQueue<E> {class ListNode{private E val;private ListNode prev;private ListNode next;public ListNode(E val) {this.val=val;}}private ListNode head;  //頭指針private ListNode tail;  //尾指針private int usedSize;   //當前隊列大小//元素從隊尾入隊列public boolean offer(E e) {}//隊頭元素出隊列public E poll() {}//獲取隊頭元素public E peek() {}//獲取隊列元素個數public int size() {return usedSize;}//判斷隊列是否為空public boolean isEmpty() {return usedSize==0;}
}

1.入隊列:

public boolean offer(E e) {ListNode node=new ListNode(e);//空隊列if(usedSize==0) {head=tail=node;}else {tail.next=node;node.prev=tail;tail=tail.next;}this.usedSize++;return true;
}

2.出隊列：

public E poll() {if(usedSize==0) {throw new RuntimeException("當前隊列為空");}E obj=head.val;if(head==tail) {head=tail=null;}else {head=head.next;head.prev=null;}usedSize--;return obj;
}

3.獲取隊頭元素：

public E peek() {if(usedSize==0) {throw new RuntimeException("隊列為空");}return head.val;
}

4.測試結果：

3.循環隊列

3.1 循環隊列的概念

循環隊列簡單來說就是一個將隊列的首尾相連接的特殊隊列；循環隊列通常采用數組實現；

3.2 循環隊列判斷空和滿

1.使用size記錄循環隊列大小：

if(front==rear&&size==0)System.out.println("循環隊列為空")
if(front==rear&&size!=0)System.out.println("循環隊列為滿")

2.使用標記：

1. 初始狀態：隊列為空，front==rear&&isFull=false
2. 入隊前，檢查front與rear是否重合，重合則isFull=true，即隊列滿，否則rear移動
3. 出隊時，front移動，isFull=false

3.保留一個位置：

• 隊列為空：front==rear
• 隊列為滿：(rear+1)%capacity
• rear的循環移動：rear=(rear+1)%capacity

4.雙端隊列Deque

雙端隊列是可以在兩端均進行插入和刪除的隊列；即隊頭隊尾均可以進行出隊入隊，

因此Deque既可以當作隊列也可以當作棧使用。

Deque是接口，因此使用時必須用LinkedList創建對象。

Deque常見的實現類為：

Deque<Integer> stack=new ArrayDeque<>();
Deque<Integer> queue=new LinkedList<>();

-----------------------------------------------------------------------------完-----------------------------------------------------------------------------