線性表：棧、隊列? ? ? ? ? ? ? ? ? ? ?抽象的數(shù)據(jù)結(jié)構(gòu)

棧：操作受限的線性表，只允許一段插入或刪除，功能上可替代，操作上越靈活使用時就不可控，先進后出、先出后進

????入棧和出棧都在棧頂插入或刪除數(shù)據(jù)

????數(shù)組實現(xiàn)的棧：順序棧

????鏈表實現(xiàn)的棧：鏈式棧

入棧的最好情況時間復(fù)雜度O（1），最壞O（n），平均=最壞

攤還分析法=最好

只有在個別時候退化為O（n），均攤到其他的操作上。

函數(shù)調(diào)用棧：存儲函數(shù)調(diào)用時的臨時變量

編譯器實現(xiàn)表達式求值

????用到兩個棧：操作數(shù)（紅色）、運算符（黃色）

瀏覽器的前進和后退（a、b、c三個網(wǎng)頁，三次后退和前進）

隊列

????先進先出

????入隊（數(shù)據(jù)放在隊尾）、出隊（隊頭取出數(shù)據(jù)）

????順序隊列：數(shù)組實現(xiàn)

????鏈式隊列：鏈表實現(xiàn)

????

當(dāng)滿了以后搬一次數(shù)據(jù)O（1）

環(huán)形隊列操作

隊滿的判斷條件tail==n

隊空的判斷條件tail==head

隊滿（tail+1）%n=head

阻塞隊列

????生產(chǎn)-消費者模型：生產(chǎn)數(shù)據(jù)的速度過快，消費者來不及消費，很快就會滿。生產(chǎn)者和消費者個數(shù)，N個消費者對應(yīng)一個生產(chǎn)者。

循環(huán)隊列比鏈表（沒有隨機訪問特性）應(yīng)用更廣泛

并發(fā)隊列（特殊特性的隊列應(yīng)用廣泛）

線程池中應(yīng)用

????處理速度和線程個數(shù)不是線程正相關(guān)

????過多的線程反而會導(dǎo)致CPU頻繁切換

????固定大小的線程池，沒有空間處理策略：

????????非阻塞的處理方式，直接拒絕（微服務(wù)里的熔斷）

????阻塞的處理方式，排隊、等空閑線程

????先進先服務(wù)，存儲排隊請求。

????無限排隊的無界隊列，請求處理時間長，對響應(yīng)敏感不合適（鏈式隊列）

????有界隊列，Polly瞬態(tài)故障，限制并發(fā)數(shù)（12個并發(fā)，10個排隊）直接拒絕。? ??

隊列可以應(yīng)用在任何有限資源池，數(shù)據(jù)庫連接池。