***** ## 棧與隊列 ### 如何理解“棧”？ 關于“棧”，我有一個非常貼切的例子，就是一摞疊在一起的盤子。我們平時放盤子的時候，都是從下往上一個一個放；取的時候，我們也是從上往下一個一個地依次取，不能從中間任意抽出。**后進者先出，先進者后出，這就是典型的“棧”結構。**  從棧的操作特性上來看，**棧是一種“操作受限”的線性表**，只允許在一端插入和刪除數據 <br>大家有沒有覺得，相比鏈表，棧帶給我的只有限制，并沒有任何優勢。那我直接使用數組或者鏈表不就好了嗎？為什么還要用這個“操作受限”的“棧”呢？ <br>事實上，從功能上來說，鏈表確實可以替代棧，但你要知道，特定的數據結構是對特定場景的抽象，而且，數組或鏈表暴露了太多的操作接口，操作上的確靈活自由，但使用時就比較不可控，自然也就更容易出錯。 <br>**當某個數據集合只涉及在一端插入和刪除數據，并且滿足后進先出、先進后出的特性，我們就應該首選“棧”這種數據結構。** ### 如何實現一個“棧”？ 從剛才棧的定義里，我們可以看出，棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個數據和從棧頂刪除一個數據。理解了棧的定義之后，我們來看一看如何用代碼實現一個棧。 <br>實際上，棧既可以用順序表來實現，也可以用鏈表來實現。用順序表實現的棧，我們叫作順序棧，用鏈表實現的棧，我們叫作鏈式棧。 ### 棧的操作 - Stack() 創建一個新的空棧 - push(item) 添加一個新的元素item到棧頂 - pop() 彈出棧頂元素 - peek() 返回棧頂元素 - is_empty() 判斷棧是否為空 - size() 返回棧的元素個數 ## 案例 瀏覽器的前進、后退功能，我想你肯定很熟悉吧？ <br>當你依次訪問完一串頁面 a-b-c 之后，點擊瀏覽器的后退按鈕，就可以查看之前瀏覽過的頁面 b 和 a。當你后退到頁面 a，點擊前進按鈕，就可以重新查看頁面 b 和 c。但是，如果你后退到頁面 b 后，點擊了新的頁面 d，那就無法再通過前進、后退功能查看頁面 c 了。 <br>假設你是 Chrome 瀏覽器的開發工程師，你會如何實現這個功能呢？ ## 隊列 隊列這個概念非常好理解。你可以把它想象成排隊買票，先來的先買，后來的人只能站末尾，不允許插隊。**先進者先出，這就是典型的“隊列”。** <br>我們知道，棧只支持兩個基本操作：入棧 push()和出棧 pop()。隊列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個：入隊 enqueue()，放一個數據到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。  所以，隊列跟棧一樣，也是一種操作受限的線性表數據結構。 隊列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎的數據結構，隊列的應用也非常廣泛，特別是一些具有某些額外特性的隊列，比如循環隊列、阻塞隊列、并發隊列。它們在很多偏底層系統、框架、中間件的開發中，起著關鍵性的作用。 ### 隊列的實現 - Queue() 創建一個空的隊列 - enqueue(item) 往隊列中添加一個item元素 - dequeue() 從隊列頭部刪除一個元素 - is_empty() 判斷一個隊列是否為空 - size() 返回隊列的大小 ## 雙端隊列 雙端隊列（deque，全名double-ended queue），是一種具有隊列和棧的性質的數據結構。 雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。  ### 操作 - Deque() 創建一個空的雙端隊列 - add_front(item) 從隊頭加入一個item元素 - add_rear(item) 從隊尾加入一個item元素 - remove_front() 從隊頭刪除一個item元素 - remove_rear() 從隊尾刪除一個item元素 - is_empty() 判斷雙端隊列是否為空 - size() 返回隊列的大小 ### 阻塞隊列 阻塞隊列其實就是在隊列基礎上增加了阻塞操作。簡單來說，就是在隊列為空的時候，從隊頭取數據會被阻塞。因為此時還沒有數據可取，直到隊列中有了數據才能返回；如果隊列已經滿了，那么插入數據的操作就會被阻塞，直到隊列中有空閑位置后再插入數據，然后再返回。 ## 案例 我們知道，CPU 資源是有限的，任務的處理速度與線程個數并不是線性正相關。相反，過多的線程反而會導致 CPU 頻繁切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務的特點和硬件環境，來事先設置的。 <br>當我們向固定大小的線程池中請求一個線程時，如果線程池中沒有空閑資源了，這個時候線程池如何處理這個請求？是拒絕請求還是排隊請求？各種處理策略又是怎么實現的呢？