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

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

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

一、棧

1.定義

只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把?？醋饕粋€“水杯”，只能從一端添加元素，也只能從一段刪除元素，而且，先進入水杯的水在杯底，后進入水杯的水在杯頂，往出倒水的時候，也是倒出的杯頂?shù)乃?，棧也是一樣，先入棧的元素在棧底，后入棧的元素在棧頂，所以先入棧的元素后出，后入棧的元素先出，這也是棧的特性“先進后出，后進先出”Last In First Out(LIFO),取出元素和添加元素只能在棧頂。
將1 2 3 4 5，一次放入棧中

2.棧的應(yīng)用

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

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

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

3.棧的實現(xiàn)

基于鏈表實現(xiàn)的棧 – 鏈式棧
基于數(shù)組實現(xiàn)的棧 – 順序棧（使用較多）
定義一個基于動態(tài)數(shù)組實現(xiàn)的棧

//基于動態(tài)數(shù)組實現(xiàn)的順序棧public class MyStack<E> {     //記錄當前棧的元素個數(shù)     private int size;     //實際存儲數(shù)據(jù)的動態(tài)數(shù)組，此時在棧中只能在數(shù)組的尾部添加和刪除元素     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!");         }         //在數(shù)組末尾刪除元素         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）的數(shù)據(jù)結(jié)構(gòu)i，元素只能從隊尾添加到隊列中，也只能從隊首出隊列，元素的出隊順序和入隊順序保持一致
將1 2 3 4 5依次入隊

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

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

3.隊列的實現(xiàn)

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

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

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

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.循環(huán)隊列

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

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

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

當隊列為空時,head == tail

當隊列已“滿”時，head == tail

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

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

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

1.定義一個循環(huán)隊列

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

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

@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)隊列中出隊一個元素

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

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

5.判斷當前循環(huán)隊列是否為空

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

6.判斷當前循環(huán)隊列是否已滿

 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，不管使用棧還是隊列，都可以統(tǒng)一使用雙端隊列接口
1.現(xiàn)在需要一個棧

2.現(xiàn)在需要一個隊列

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