假設(shè)堆棧中有n個(gè)元素。
訪問(wèn)：O（n）//最壞情況
插入刪除：O（1）//頂端插入和刪除元素

3.2. 棧的常見(jiàn)應(yīng)用常見(jiàn)應(yīng)用場(chǎng)景

當(dāng)我們我們要處理的數(shù)據(jù)只涉及在一端插入和刪除數(shù)據(jù)，并且滿足 后進(jìn)先出（LIFO, Last In First Out） 的特性時(shí)，我們就可以使用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。

3.2.1. 實(shí)現(xiàn)瀏覽器的回退和前進(jìn)功能

我們只需要使用兩個(gè)棧(Stack1 和 Stack2)和就能實(shí)現(xiàn)這個(gè)功能。比如你按順序查看了 1,2,3,4 這四個(gè)頁(yè)面，我們依次把 1,2,3,4 這四個(gè)頁(yè)面壓入 Stack1 中。當(dāng)你想回頭看 2 這個(gè)頁(yè)面的時(shí)候，你點(diǎn)擊回退按鈕，我們依次把 4,3 這兩個(gè)頁(yè)面從 Stack1 彈出，然后壓入 Stack2 中。假如你又想回到頁(yè)面 3，你點(diǎn)擊前進(jìn)按鈕，我們將 3 頁(yè)面從 Stack2 彈出，然后壓入到 Stack1 中。示例圖如下:

3.2.2. 檢查符號(hào)是否成對(duì)出現(xiàn)

給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷該字符串是否有效。

有效字符串需滿足：

1. 左括號(hào)必須用相同類型的右括號(hào)閉合。
2. 左括號(hào)必須以正確的順序閉合。

比如 “()”、“()[]{}”、“{[]}” 都是有效字符串，而 “(]” 、“([)]” 則不是。

這個(gè)問(wèn)題實(shí)際是 Leetcode 的一道題目，我們可以利用棧 Stack 來(lái)解決這個(gè)問(wèn)題。

1. 首先我們將括號(hào)間的對(duì)應(yīng)規(guī)則存放在 Map 中，這一點(diǎn)應(yīng)該毋容置疑；
2. 創(chuàng)建一個(gè)棧。遍歷字符串，如果字符是左括號(hào)就直接加入stack中，否則將stack 的棧頂元素與這個(gè)括號(hào)做比較，如果不相等就直接返回 false。遍歷結(jié)束，如果stack為空，返回 true。

public boolean isValid(String s){
    // 括號(hào)之間的對(duì)應(yīng)規(guī)則
    HashMap<Character, Character> mappings = new HashMap<Character, Character>();
    mappings.put(')', '(');
    mappings.put('}', '{');
    mappings.put(']', '[');
    Stack<Character> stack = new Stack<Character>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (mappings.containsKey(chars[i])) {
            char topElement = stack.empty() ? '#' : stack.pop();
            if (topElement != mappings.get(chars[i])) {
                return false;
            }
        } else {
            stack.push(chars[i]);
        }
    }
    return stack.isEmpty();
}

3.2.3. 反轉(zhuǎn)字符串

將字符串中的每個(gè)字符先入棧再出棧就可以了。

3.2.4. 維護(hù)函數(shù)調(diào)用

最后一個(gè)被調(diào)用的函數(shù)必須先完成執(zhí)行，符合棧的 后進(jìn)先出（LIFO, Last In First Out） 特性。

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

棧既可以通過(guò)數(shù)組實(shí)現(xiàn)，也可以通過(guò)鏈表來(lái)實(shí)現(xiàn)。不管基于數(shù)組還是鏈表，入棧、出棧的時(shí)間復(fù)雜度都為 O(1)。

下面我們使用數(shù)組來(lái)實(shí)現(xiàn)一個(gè)棧，并且這個(gè)棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()、size()這些基本的方法。

提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用Arrays.copyOf()進(jìn)行擴(kuò)容；

public class MyStack {
    private int[] storage;//存放棧中元素的數(shù)組
    private int capacity;//棧的容量
    private int count;//棧中元素?cái)?shù)量
    private static final int GROW_FACTOR = 2;

    //不帶初始容量的構(gòu)造方法。默認(rèn)容量為8
    public MyStack() {
        this.capacity = 8;
        this.storage=new int[8];
        this.count = 0;
    }

    //帶初始容量的構(gòu)造方法
    public MyStack(int initialCapacity) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException("Capacity too small.");

        this.capacity = initialCapacity;
        this.storage = new int[initialCapacity];
        this.count = 0;
    }

    //入棧
    public void push(int value) {
        if (count == capacity) {
            ensureCapacity();
        }
        storage[count++] = value;
    }

    //確保容量大小
    private void ensureCapacity() {
        int newCapacity = capacity * GROW_FACTOR;
        storage = Arrays.copyOf(storage, newCapacity);
        capacity = newCapacity;
    }

    //返回棧頂元素并出棧
    private int pop() {
        if (count == 0)
            throw new IllegalArgumentException("Stack is empty.");
        count--;
        return storage[count];
    }

    //返回棧頂元素不出棧
    private int peek() {
        if (count == 0){
            throw new IllegalArgumentException("Stack is empty.");
        }else {
            return storage[count-1];
        }
    }

    //判斷棧是否為空
    private boolean isEmpty() {
        return count == 0;
    }

    //返回棧中元素的個(gè)數(shù)
    private int size() {
        return count;
    }

}

驗(yàn)證

MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {
    System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//報(bào)錯(cuò)：java.lang.IllegalArgumentException: Stack is empty.

4. 隊(duì)列

4.1. 隊(duì)列簡(jiǎn)介

隊(duì)列 是 先進(jìn)先出( FIFO，F(xiàn)irst In, First Out) 的線性表。在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)，用數(shù)組實(shí)現(xiàn)的隊(duì)列叫作 順序隊(duì)列 ，用鏈表實(shí)現(xiàn)的隊(duì)列叫作 鏈?zhǔn)疥?duì)列 。隊(duì)列只允許在后端（rear）進(jìn)行插入操作也就是 入隊(duì) enqueue，在前端（front）進(jìn)行刪除操作也就是出隊(duì) dequeue

隊(duì)列的操作方式和堆棧類似，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。

假設(shè)隊(duì)列中有n個(gè)元素。
訪問(wèn)：O（n）//最壞情況
插入刪除：O（1）//后端插入前端刪除元素

4.2. 隊(duì)列分類

4.2.1. 單隊(duì)列

單隊(duì)列就是常見(jiàn)的隊(duì)列, 每次添加元素時(shí)，都是添加到隊(duì)尾。單隊(duì)列又分為 順序隊(duì)列（數(shù)組實(shí)現(xiàn)） 和 鏈?zhǔn)疥?duì)列（鏈表實(shí)現(xiàn)）。

順序隊(duì)列存在“假溢出”的問(wèn)題也就是明明有位置卻不能添加的情況。

假設(shè)下圖是一個(gè)順序隊(duì)列，我們將前兩個(gè)元素 1,2 出隊(duì)，并入隊(duì)兩個(gè)元素 7,8。當(dāng)進(jìn)行入隊(duì)、出隊(duì)操作的時(shí)候，front 和 rear 都會(huì)持續(xù)往后移動(dòng)，當(dāng) rear 移動(dòng)到最后的時(shí)候,我們無(wú)法再往隊(duì)列中添加數(shù)據(jù)，即使數(shù)組中還有空余空間，這種現(xiàn)象就是 ”假溢出“ 。除了假溢出問(wèn)題之外，如下圖所示，當(dāng)添加元素 8 的時(shí)候，rear 指針移動(dòng)到數(shù)組之外（越界）。

為了避免當(dāng)只有一個(gè)元素的時(shí)候，隊(duì)頭和隊(duì)尾重合使處理變得麻煩，所以引入兩個(gè)指針，front 指針指向?qū)︻^元素，rear 指針指向隊(duì)列最后一個(gè)元素的下一個(gè)位置，這樣當(dāng) front 等于 rear 時(shí)，此隊(duì)列不是還剩一個(gè)元素，而是空隊(duì)列?！狥rom 《大話數(shù)據(jù)結(jié)構(gòu)》

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

循環(huán)隊(duì)列可以解決順序隊(duì)列的假溢出和越界問(wèn)題。解決辦法就是：從頭開始，這樣也就會(huì)形成頭尾相接的循環(huán)，這也就是循環(huán)隊(duì)列名字的由來(lái)。

還是用上面的圖，我們將 rear 指針指向數(shù)組下標(biāo)為 0 的位置就不會(huì)有越界問(wèn)題了。當(dāng)我們?cè)傧蜿?duì)列中添加元素的時(shí)候， rear 向后移動(dòng)。

順序隊(duì)列中，我們說(shuō) front==rear 的時(shí)候隊(duì)列為空，循環(huán)隊(duì)列中則不一樣，也可能為滿，如上圖所示。解決辦法有兩種：

1. 可以設(shè)置一個(gè)標(biāo)志變量 flag,當(dāng) front==rear 并且 flag=0 的時(shí)候隊(duì)列為空，當(dāng)front==rear 并且 flag=1 的時(shí)候隊(duì)列為滿。
2. 隊(duì)列為空的時(shí)候就是 front==rear ，隊(duì)列滿的時(shí)候，我們保證數(shù)組還有一個(gè)空閑的位置，rear 就指向這個(gè)空閑位置，如下圖所示，那么現(xiàn)在判斷隊(duì)列是否為滿的條件就是： (rear+1) % QueueSize= front 。

4.3. 常見(jiàn)應(yīng)用場(chǎng)景

當(dāng)我們需要按照一定順序來(lái)處理數(shù)據(jù)的時(shí)候可以考慮使用隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-667448.html

• 阻塞隊(duì)列： 阻塞隊(duì)列可以看成在隊(duì)列基礎(chǔ)上加了阻塞操作的隊(duì)列。當(dāng)隊(duì)列為空的時(shí)候，出隊(duì)操作阻塞，當(dāng)隊(duì)列滿的時(shí)候，入隊(duì)操作阻塞。使用阻塞隊(duì)列我們可以很容易實(shí)現(xiàn)“生產(chǎn)者 - 消費(fèi)者“模型。
• 線程池中的請(qǐng)求/任務(wù)隊(duì)列： 線程池中沒(méi)有空閑線程時(shí)，新的任務(wù)請(qǐng)求線程資源時(shí)，線程池該如何處理呢？答案是將這些請(qǐng)求放在隊(duì)列中，當(dāng)有空閑線程的時(shí)候，會(huì)循環(huán)中反復(fù)從隊(duì)列中獲取任務(wù)來(lái)執(zhí)行。隊(duì)列分為無(wú)界隊(duì)列(基于鏈表)和有界隊(duì)列(基于數(shù)組)。無(wú)界隊(duì)列的特點(diǎn)就是可以一直入列，除非系統(tǒng)資源耗盡，比如 ：FixedThreadPool 使用無(wú)界隊(duì)列 LinkedBlockingQueue。但是有界隊(duì)列就不一樣了，當(dāng)隊(duì)列滿的話后面再有任務(wù)/請(qǐng)求就會(huì)拒絕，在 Java 中的體現(xiàn)就是會(huì)拋出java.util.concurrent.RejectedExecutionException 異常。
• Linux 內(nèi)核進(jìn)程隊(duì)列（按優(yōu)先級(jí)排隊(duì)）
• 現(xiàn)實(shí)生活中的派對(duì)，播放器上的播放列表;
• 消息隊(duì)列

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——線性數(shù)據(jù)結(jié)構(gòu)（數(shù)組，鏈表，棧，隊(duì)列）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！