站長資訊網本篇文章給大家帶來了關于java的相關知識，其中主要整理了棧和隊列的相關問題，包括了棧和隊列的定義、應用、實現和操作等等內容，下面一起來看一下，希望對大家有幫助。
推薦學習：《java視頻教程》
在學習棧和隊列 之前，先了解一下什么是線性表：一次保存單個同類型的元素，多個元素之間邏輯上連續，比如數組，鏈表，字符串，棧和隊列
棧和隊列其實操作受限的線性表，數組也罷，鏈表也罷，既可以在頭部插入和刪除，也能在尾部插入和刪除，但是棧和隊列只能在一端插入，在一端刪除
一、棧
1.定義
只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把棧看作一個“水杯”，只能從一端添加元素，也只能從一段刪除元素，而且，先進入水杯的水在杯底，后進入水杯的水在杯頂，往出倒水的時候，也是倒出的杯頂的水，棧也是一樣，先入棧的元素在棧底，后入棧的元素在棧頂，所以先入棧的元素后出，后入棧的元素先出，這也是棧的特性“先進后出，后進先出”Last In First Out(LIFO),取出元素和添加元素只能在棧頂。
將1 2 3 4 5，一次放入棧中
2.棧的應用
1.無處不在的undo(撤銷)操作
在任何一個編輯器中輸錯一個內容后，使用Ctrl + z就返回到了輸入的內容；
在任何一個瀏覽器中點擊后退操作
都是棧的這個結構的應用
1.使用編輯器使用撤銷操作，一次輸入就把內容壓入棧中，再輸入就就再壓入棧中，發現一次輸入錯誤，就使用撤銷操作，把當前棧頂的錯誤內容彈出，那么當前棧頂的內容就是上次輸入的內容。
2.瀏覽網頁其實也是相同原理的，就像打開百度 -> 打開csdn -> 打開創作中心，也是使用棧這個結構，先把百度網頁壓入棧中 ，然后csdn網頁壓入棧中，然后創作中心網頁壓入棧中，想要返回到csdn主頁，按下后頭箭頭，就把當前棧頂的創作中心網頁彈出，取出csdn主頁。
2.操作系統棧
程序再執行的過程中，從A函數調用B函數，從B函數調用C函數，調用結束，返回執行時，如何得知從哪繼續開始執行呢，背后也是棧這個結構
3.棧的實現
基于鏈表實現的棧 – 鏈式棧
基于數組實現的棧 – 順序棧（使用較多）
定義一個基于動態數組實現的棧
//基于動態數組實現的順序棧public class MyStack<E> { //記錄當前棧的元素個數 private int size; //實際存儲數據的動態數組，此時在棧中只能在數組的尾部添加和刪除元素 private List<E> data = new ArrayList<>(); }
4.棧的操作
1.向棧中添加一個元素
只能在棧頂添加
/** * 向當前棧中添加元素 -- >壓棧操作 * @param val */ public void push(E val){ data.add(val); size++; }
2.當前從棧頂彈出一個元素
/** * 彈出當前棧頂元素,返回棧頂元素的值 * @return */ public E pop(){ if (isEmpty()){ //棧為空無法彈出 throw new NoSuchElementException("stack is empty!cannot pop!"); } //在數組末尾刪除元素 E val = data.get(size - 1); data.remove(size - 1); size --; return val; }
3.查看當前棧頂元素，但不彈出
/** * 查看當前棧頂元素值，不彈出該元素 * @return */ public E peek(){ if (isEmpty()){ throw new NoSuchElementException("stack is empty!cannot peek!"); } return data.get(size - 1); }
二、隊列
1.定義
隊列：先進先出（FIFO）的數據結構i，元素只能從隊尾添加到隊列中，也只能從隊首出隊列，元素的出隊順序和入隊順序保持一致
將1 2 3 4 5依次入隊
2.隊列的應用
現實生活中，各種各樣的“排隊”操作
3.隊列的實現
基于數組實現的隊列 – 順序隊列
基于鏈表實現的隊列 – 鏈式隊列
出隊操作只能在隊列的頭部進行，若采用數組實現的隊列，每次出隊一個元素就得搬移剩下的所有元素向前移動一個單位，此時采用鏈表實現的隊列更適合隊列的結構，刪除元素只需要刪除頭結點，添加元素在鏈表的尾部添加
public interface Queue<E> { //入隊操作 void offer(E val); //出隊操作 E poll(); //查看隊首元素 E peek(); boolean isEmpty();}
對于棧來說隊列的實現子類是比較多的，比如
FIFO隊列
雙端隊列
循環隊列
優先級隊列
不管哪個隊列都要實現
4.FIFO隊列
1.定義一個FIFO隊列
// An highlighted blockvar foo = 'bar';
2.向隊列中添加一個元素
public void offer(E val) { Node<E> node = new Node<>(val); if (head == null){ head = tail = node; }else{ //鏈表的尾插 tail.next = node; tail = node; } size++; }
3.從當前隊首出隊一個元素
public E poll() { if (isEmpty()){ throw new NoSuchElementException("queue is empty! cannot poll!"); } //頭刪 E val = head.val; Node<E> node = head; head = head.next; node.next = node = null; size--; return val; }
4.查看當前隊列的隊首元素
public E peek() { if (isEmpty()){ throw new NoSuchElementException("queue is empty!cannot peek!"); } return head.val; }
5.循環隊列
1.定義：基本上都是使用固定長度的數組來實現，數組在實現隊時，若從數組頭部刪除元素需要頻繁的移動后面的元素，效率比較低；出隊和入隊操作，使用兩個引用，一個head，一個tail,添加元素在數組的尾部添加，刪除元素只需要移動head引用指向的地址即可（邏輯刪除）
2.應用：操作系統的生產消費者模型，MySQL數據庫的InnoDB存儲引擎的redo日志
3.循環隊列就是使用長度固定的數組來實現，數組頭部就是隊首（head），數組的尾部就是隊尾（tail），數組[head…tail)時循環隊列的有效元素
head永遠指向循環隊列的第一個元素
tai永遠指向循環隊列有效元素的后一個位置
此時循環隊列的有效元素就為7 9 1兩個元素
循環隊列出隊一個元素，就只用讓head引用向后移動一個位置
此時循環隊列的有效元素就只有9 和 1 兩個元素了
再出隊一個元素，但此時head引用已經走到末尾了，所謂循環隊列就是當head或者tail引用走到數組末尾時，再向后移動就是返回數組頭部的操作，循環隊列最大好處就是進行元素的刪除的時候不需要進行數據的搬移操作，當有新的元素添加到隊列中就會覆蓋掉原來的元素，就只需要將tail索引位置覆蓋上新的元素，再讓tail再向后移動
當隊列為空時,head == tail
當隊列已“滿”時，head == tail
循環隊列需要注意的關鍵點
1.因此當head 和 tail相等時，沒法區分此時循環隊列已滿，還是為空，因此在循環隊列中，若(tail + 1) % n == head就認為循環隊列已滿
此時循環隊列就已經滿了，在循環隊列中就會浪費一個空間，判斷隊列是否已滿
2.head和tail的移動不能簡單的 + 1，使用取模操作，取數組長度
tail = (tail + 1) % n
head = (head + 1) % n
對數組長度取模的本質：
當head和tai走到數組最后一個索引位置時，下一次要返回數組頭部，就必須用 + 1對數組長度取模
3.head == tail時，認為隊列為空
6.循環隊列的操作
1.定義一個循環隊列
//基于整形的循環隊列public class LoopQueue implements Queue<Integer> { //定長數組 private Integer[] data; //指向隊首元素 int head; //指向隊尾元素的下一個元素 int tail; public LoopQueue(int size){ data = new Integer[size + 1]; }}
2.向循環隊列中添加一個元素
@Override public void offer(Integer val) { if (isFull()){ throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer"); } data[tail] = val; tail = (tail + 1) % data.length; }
3.從循環隊列中出隊一個元素
@Override public Integer poll() { if (isEmpty()){ throw new NoSuchElementException("loopQueue is empty!cannot poll!"); } Integer val = data[head]; head = (head + 1) % data.length; return val; }
4.查看當前循環隊列隊首元素
@Override public Integer peek() { if (isEmpty()){ throw new NoSuchElementException("loopQueue is empty!cannot peek!"); } return data[head]; }
5.判斷當前循環隊列是否為空
@Override public boolean isEmpty() { return head == tail; }
6.判斷當前循環隊列是否已滿
public boolean isFull(){ return (tail + 1) % data.length == head; }
7.toString方法
public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("front ["); //最后一個有效元素的索引 int lsatIndex = tail == 0 ? data.length - 1 : tail - 1; for (int i = head; i != tail;) { sb.append(data[i]); if (i != lsatIndex){ sb.append(", "); } i = (i + 1) % data.length; } sb.append("] tail"); return sb.toString(); }
7.雙端隊列
雙端隊列：Deque是Queue的子接口，這個隊列既可以尾插，頭出；也可以頭插，尾出
雙端隊列的一個常用子類就是LinkedList，不管使用棧還是隊列，都可以統一使用雙端隊列接口
1.現在需要一個棧
2.現在需要一個隊列
推薦學習：《java視頻教程》
