本篇文章給大家?guī)砹岁P(guān)于java的相關(guān)知識(shí)，其中主要整理了棧和隊(duì)列的相關(guān)問題，包括了棧和隊(duì)列的定義、應(yīng)用、實(shí)現(xiàn)和操作等等內(nèi)容，下面一起來看一下，希望對(duì)大家有幫助。

推薦學(xué)習(xí)：《java視頻教程》

在學(xué)習(xí)棧和隊(duì)列 之前，先了解一下什么是線性表：一次保存單個(gè)同類型的元素，多個(gè)元素之間邏輯上連續(xù)，比如數(shù)組，鏈表，字符串，棧和隊(duì)列
棧和隊(duì)列其實(shí)操作受限的線性表，數(shù)組也罷，鏈表也罷，既可以在頭部插入和刪除，也能在尾部插入和刪除，但是棧和隊(duì)列只能在一端插入，在一端刪除

一、棧

1.定義

只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把棧看作一個(gè)“水杯”，只能從一端添加元素，也只能從一段刪除元素，而且，先進(jìn)入水杯的水在杯底，后進(jìn)入水杯的水在杯頂，往出倒水的時(shí)候，也是倒出的杯頂?shù)乃瑮Ｒ彩且粯樱热霔５脑卦跅５祝笕霔５脑卦跅ｍ敚韵热霔５脑睾蟪觯笕霔５脑叵瘸觯@也是棧的特性“先進(jìn)后出，后進(jìn)先出”Last In First Out(LIFO),取出元素和添加元素只能在棧頂。
將1 2 3 4 5，一次放入棧中

2.棧的應(yīng)用

1.無處不在的undo(撤銷)操作

在任何一個(gè)編輯器中輸錯(cuò)一個(gè)內(nèi)容后，使用Ctrl + z就返回到了輸入的內(nèi)容；
在任何一個(gè)瀏覽器中點(diǎn)擊后退操作

都是棧的這個(gè)結(jié)構(gòu)的應(yīng)用
1.使用編輯器使用撤銷操作，一次輸入就把內(nèi)容壓入棧中，再輸入就就再壓入棧中，發(fā)現(xiàn)一次輸入錯(cuò)誤，就使用撤銷操作，把當(dāng)前棧頂?shù)腻e(cuò)誤內(nèi)容彈出，那么當(dāng)前棧頂?shù)膬?nèi)容就是上次輸入的內(nèi)容。
2.瀏覽網(wǎng)頁其實(shí)也是相同原理的，就像打開百度 -> 打開csdn -> 打開創(chuàng)作中心，也是使用棧這個(gè)結(jié)構(gòu)，先把百度網(wǎng)頁壓入棧中 ，然后csdn網(wǎng)頁壓入棧中，然后創(chuàng)作中心網(wǎng)頁壓入棧中，想要返回到csdn主頁，按下后頭箭頭，就把當(dāng)前棧頂?shù)膭?chuàng)作中心網(wǎng)頁彈出，取出csdn主頁。

2.操作系統(tǒng)棧

程序再執(zhí)行的過程中，從A函數(shù)調(diào)用B函數(shù)，從B函數(shù)調(diào)用C函數(shù)，調(diào)用結(jié)束，返回執(zhí)行時(shí)，如何得知從哪繼續(xù)開始執(zhí)行呢，背后也是棧這個(gè)結(jié)構(gòu)

3.棧的實(shí)現(xiàn)

基于鏈表實(shí)現(xiàn)的棧 – 鏈?zhǔn)綏?br /> 基于數(shù)組實(shí)現(xiàn)的棧 – 順序棧（使用較多）
定義一個(gè)基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的棧

//基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的順序棧public class MyStack<E> {     //記錄當(dāng)前棧的元素個(gè)數(shù)     private int size;     //實(shí)際存儲(chǔ)數(shù)據(jù)的動(dòng)態(tài)數(shù)組，此時(shí)在棧中只能在數(shù)組的尾部添加和刪除元素     private List<E> data = new ArrayList<>();     }

4.棧的操作

1.向棧中添加一個(gè)元素
只能在棧頂添加

 /**      * 向當(dāng)前棧中添加元素 -- >壓棧操作      * @param val      */     public void push(E val){         data.add(val);         size++;     }

2.當(dāng)前從棧頂彈出一個(gè)元素

/**      * 彈出當(dāng)前棧頂元素,返回棧頂元素的值      * @return      */     public E pop(){         if (isEmpty()){             //棧為空無法彈出             throw new NoSuchElementException("stack is empty!cannot pop!");         }         //在數(shù)組末尾刪除元素         E val = data.get(size - 1);         data.remove(size - 1);         size --;         return val;     }

3.查看當(dāng)前棧頂元素，但不彈出

/**      * 查看當(dāng)前棧頂元素值，不彈出該元素      * @return      */     public E peek(){         if (isEmpty()){             throw new NoSuchElementException("stack is empty!cannot peek!");         }         return data.get(size - 1);     }

二、隊(duì)列

1.定義

隊(duì)列：先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)i，元素只能從隊(duì)尾添加到隊(duì)列中，也只能從隊(duì)首出隊(duì)列，元素的出隊(duì)順序和入隊(duì)順序保持一致
將1 2 3 4 5依次入隊(duì)

2.隊(duì)列的應(yīng)用

現(xiàn)實(shí)生活中，各種各樣的“排隊(duì)”操作

3.隊(duì)列的實(shí)現(xiàn)

基于數(shù)組實(shí)現(xiàn)的隊(duì)列 – 順序隊(duì)列
基于鏈表實(shí)現(xiàn)的隊(duì)列 – 鏈?zhǔn)疥?duì)列
出隊(duì)操作只能在隊(duì)列的頭部進(jìn)行，若采用數(shù)組實(shí)現(xiàn)的隊(duì)列，每次出隊(duì)一個(gè)元素就得搬移剩下的所有元素向前移動(dòng)一個(gè)單位，此時(shí)采用鏈表實(shí)現(xiàn)的隊(duì)列更適合隊(duì)列的結(jié)構(gòu)，刪除元素只需要?jiǎng)h除頭結(jié)點(diǎn)，添加元素在鏈表的尾部添加

public interface Queue<E> {     //入隊(duì)操作     void offer(E val);     //出隊(duì)操作     E poll();     //查看隊(duì)首元素     E peek();     boolean isEmpty();}

對(duì)于棧來說隊(duì)列的實(shí)現(xiàn)子類是比較多的，比如
FIFO隊(duì)列
雙端隊(duì)列
循環(huán)隊(duì)列
優(yōu)先級(jí)隊(duì)列
不管哪個(gè)隊(duì)列都要實(shí)現(xiàn)

4.FIFO隊(duì)列

1.定義一個(gè)FIFO隊(duì)列

// An highlighted blockvar foo = 'bar';

2.向隊(duì)列中添加一個(gè)元素

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.從當(dāng)前隊(duì)首出隊(duì)一個(gè)元素

 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.查看當(dāng)前隊(duì)列的隊(duì)首元素

public E peek() {         if (isEmpty()){             throw new NoSuchElementException("queue is empty!cannot peek!");         }         return head.val;     }

5.循環(huán)隊(duì)列

1.定義：基本上都是使用固定長(zhǎng)度的數(shù)組來實(shí)現(xiàn)，數(shù)組在實(shí)現(xiàn)隊(duì)時(shí)，若從數(shù)組頭部刪除元素需要頻繁的移動(dòng)后面的元素，效率比較低；出隊(duì)和入隊(duì)操作，使用兩個(gè)引用，一個(gè)head，一個(gè)tail,添加元素在數(shù)組的尾部添加，刪除元素只需要移動(dòng)head引用指向的地址即可（邏輯刪除）
2.應(yīng)用：操作系統(tǒng)的生產(chǎn)消費(fèi)者模型，MySQL數(shù)據(jù)庫的InnoDB存儲(chǔ)引擎的redo日志
3.循環(huán)隊(duì)列就是使用長(zhǎng)度固定的數(shù)組來實(shí)現(xiàn)，數(shù)組頭部就是隊(duì)首（head），數(shù)組的尾部就是隊(duì)尾（tail），數(shù)組[head…tail)時(shí)循環(huán)隊(duì)列的有效元素
head永遠(yuǎn)指向循環(huán)隊(duì)列的第一個(gè)元素
tai永遠(yuǎn)指向循環(huán)隊(duì)列有效元素的后一個(gè)位置

此時(shí)循環(huán)隊(duì)列的有效元素就為7 9 1兩個(gè)元素
循環(huán)隊(duì)列出隊(duì)一個(gè)元素，就只用讓head引用向后移動(dòng)一個(gè)位置

此時(shí)循環(huán)隊(duì)列的有效元素就只有9 和 1 兩個(gè)元素了
再出隊(duì)一個(gè)元素，但此時(shí)head引用已經(jīng)走到末尾了，所謂循環(huán)隊(duì)列就是當(dāng)head或者tail引用走到數(shù)組末尾時(shí)，再向后移動(dòng)就是返回?cái)?shù)組頭部的操作，循環(huán)隊(duì)列最大好處就是進(jìn)行元素的刪除的時(shí)候不需要進(jìn)行數(shù)據(jù)的搬移操作，當(dāng)有新的元素添加到隊(duì)列中就會(huì)覆蓋掉原來的元素，就只需要將tail索引位置覆蓋上新的元素，再讓tail再向后移動(dòng)

當(dāng)隊(duì)列為空時(shí),head == tail

當(dāng)隊(duì)列已“滿”時(shí)，head == tail

循環(huán)隊(duì)列需要注意的關(guān)鍵點(diǎn)
1.因此當(dāng)head 和 tail相等時(shí)，沒法區(qū)分此時(shí)循環(huán)隊(duì)列已滿，還是為空，因此在循環(huán)隊(duì)列中，若(tail + 1) % n == head就認(rèn)為循環(huán)隊(duì)列已滿

此時(shí)循環(huán)隊(duì)列就已經(jīng)滿了，在循環(huán)隊(duì)列中就會(huì)浪費(fèi)一個(gè)空間，判斷隊(duì)列是否已滿
2.head和tail的移動(dòng)不能簡(jiǎn)單的 + 1，使用取模操作，取數(shù)組長(zhǎng)度
tail = (tail + 1) % n
head = (head + 1) % n
對(duì)數(shù)組長(zhǎng)度取模的本質(zhì)：
當(dāng)head和tai走到數(shù)組最后一個(gè)索引位置時(shí)，下一次要返回?cái)?shù)組頭部，就必須用 + 1對(duì)數(shù)組長(zhǎng)度取模
3.head == tail時(shí)，認(rèn)為隊(duì)列為空

6.循環(huán)隊(duì)列的操作

1.定義一個(gè)循環(huán)隊(duì)列

//基于整形的循環(huán)隊(duì)列public class LoopQueue implements Queue<Integer> {     //定長(zhǎng)數(shù)組     private Integer[] data;     //指向隊(duì)首元素     int head;     //指向隊(duì)尾元素的下一個(gè)元素     int tail;     public LoopQueue(int size){         data = new Integer[size + 1];     }}

2.向循環(huán)隊(duì)列中添加一個(gè)元素

@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.從循環(huán)隊(duì)列中出隊(duì)一個(gè)元素

 @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.查看當(dāng)前循環(huán)隊(duì)列隊(duì)首元素

 @Override    public Integer peek() {         if (isEmpty()){             throw new NoSuchElementException("loopQueue is empty!cannot peek!");         }         return data[head];     }

5.判斷當(dāng)前循環(huán)隊(duì)列是否為空

 @Override    public boolean isEmpty() {         return head == tail;     }

6.判斷當(dāng)前循環(huán)隊(duì)列是否已滿

 public boolean isFull(){         return (tail + 1) % data.length == head;     }

7.toString方法

public String toString(){         StringBuilder sb = new StringBuilder();         sb.append("front [");         //最后一個(gè)有效元素的索引         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.雙端隊(duì)列

雙端隊(duì)列：Deque是Queue的子接口，這個(gè)隊(duì)列既可以尾插，頭出；也可以頭插，尾出

雙端隊(duì)列的一個(gè)常用子類就是LinkedList，不管使用棧還是隊(duì)列，都可以統(tǒng)一使用雙端隊(duì)列接口
1.現(xiàn)在需要一個(gè)棧

2.現(xiàn)在需要一個(gè)隊(duì)列

推薦學(xué)習(xí)：《java視頻教程》