數據結構與算法之美專欄筆記
數據結構與算法之美課後筆記
01 為什麼學習數據結構和算法
一、數據結構和算法是什麼
1、數據結構是指一組數據的存儲結構
2、算法就是操作數據的方法
3、數據結構和算法是相輔相成的，數據結構是為算法服務的，而算法要作用在特定的數據結構之上
二、學習的重點在什麼地方
數據結構和算法解決的是如何更省、更快地存儲和處理數據的問題，因此，我們就需要一個考量效率和資源消耗的方法，這就是複雜度分析方法。在學習數據結構和算法的過程中，要學習它的「來歷」、
「自身的特點」、「適合解決的問題」 以吸「實際的應用場景」。
-
數據結構和算法學習的精髓-複雜度分析
-
在本專欄中，重點學習20個最常用的最基礎的數據結構和算法，需要我們逐一攻克。
10個數據結構: 數組，鏈表，棧，隊列，散列表，二叉樹，堆，跳錶，圖，Trie樹
10個算法： 遞歸，排序，二分查找，搜索，哈希算法，貪心算法，分治算法，回溯算法，動態規劃，字符串匹配算法
三、怎麼樣衡量數據結構和算法
- 需要引入一個衡量的標準(metri-)–時間複雜度和空間複雜度。
- 學習數據結構和算法的基石，就是要學會複雜度分析。知道怎麼去分析複雜度,才能作出正確的判
斷，在特定的場景下選用合適的正確的算法。而不是盲目的死記爛背，機械操作。
四、為什麼學習數據結構和算法? 有3點比較重要
- 直接好處是能夠有寫出性能更優的代碼。
- 算法,是一種解決問題的思路和方法，有機會應用到生活和事業的其他方面。
- 長期來看，大腦思考能力是個人最重要的核心競爭力，而算法是為數不多的能夠有效訓練大腦思考能力的途徑之一。
02 複雜度分析(上)
一、什麼是複雜度分析?
- 數據結構和算法解決是「如何讓計算機更快時間、更省空間的解決問題」。
- 因此需從執行時間和佔用空間兩個維度來評估數據結構和算法的性能。
- 分別用時間複雜度和空間複雜度兩個概念來描述性能問題，二 者統稱為複雜度。
- 複雜度描述的是算法執行時間(或佔用空間)與數據規模的增長關係。
二、為什麼要進行複雜度分析?
- 和性能測試相比，複雜度分析有不依賴執行環境、成本低、效率高、易操作、指導性強的特點。
- 掌握複雜度分析，將能編寫出性能更優的代碼,有利於降低系統開發和維護成本。
三、如何進行複雜度分析?
1.大0表示法
- 來源
算法的執行時間與每行代碼的執行次數成正比，用T(n) = 0(n))表示,其中T(n)表示算法執行總時間，f
(n)表示每行代碼執行總次數，而n往往表示數據的規模。 - 特點
以時間複雜度為例，由於時間複雜度描述的是算法執行時間與數據規模的增長變化趨勢,所以常量階、低階以及係數實際上對這種增長趨勢不產決定性影響，所以在做時間複雜度分析時忽略這些項。
2.複雜度分析法則
- 單段代碼看高頻:比如循環。
- 多段代碼取最大:比如一-段代碼中有單循環和多重循環,那麼取多重循環的複雜度。
- 嵌套代碼求乘積:比如遞歸、多重循環等
- 多個規模求加法:比如方法有兩個參數控制兩個循環的次數,那麼這時就取二者複雜度相加。
四、常用的複雜度級別?
-
多項式階:隨着數據規模的增長，算法的執行時間和空間佔用，按照多項式的比例增長。
包括,0(1) (常數階)、O(logn) (對數階)、O(n) (線性階)、O(nlogn) (線性對數階)、O(n^2) (平方
階)、0(n^3) (立方階) -
非多項式階:隨着數據規模的增長，算法的執行時間和空間佔用暴增,這類算法性能極差。
包括,O(2^n) (指數階)、O(n!) (階乘階)。
如何掌握好複雜度分析方法?
複雜度分析關鍵在於多練，所謂孰能生巧。
02 複雜度分析(下)
一、 複雜度分析的4個概念
-
最壞情況時間複雜度:代碼在最理想情況下執行的時間複雜度。
-
最好情況時間複雜度:代碼在最壞情況下執行的時間複雜度。
-
平均時間複雜度:用代碼在所有情況下執行的次數的加權平均值表示。
-
均攤時間複雜度:
在代碼執行的所有複雜度情況中絕大部分是低級別的複雜度,個別情況是高級別複雜度且發生具有時序關係時，可以將個別高級別複雜度均攤到低級別複雜度上。基本上均攤結果就等於低級別複雜度。
二、為什麼要引入這4個概念?
- 同一段代碼在不同情況下時間複雜度會出現量級差異，為了更全面，更準確的描述代碼的時間複雜度,所以引入這4個概念。
- 代碼複雜度在不同情況下出現量級差別時才需要區別這四種複雜度。大多數情況下，是不需要區別分析它們的。
三、如何分析平均、均攤時間複雜度?
1.平均時間複雜度
代碼在不同情況下複雜度出現量級差別，則用代碼所有可能情況下執行次數的加權平均值表示。
2.均攤時間複雜度
兩個條件滿足時使用:
- 代碼在絕大多數情況下是低級別複雜度,只有極少數情況是高級別複雜度;
- 低級別和高級別複雜度出現具有時序規律。均攤結果-般都等於低級別複雜度。
03 數組：為什麼很多編程語言中數組都從0開始編號？
一、為什麼很多編程語言的數組都是從0開始編號的?
- 從數組存儲的內存模型上來看，「下標」 確切的說法就是一種」偏移」，相比從1開始編號,從0開始編號會少-次減法運算, 數組作為非常基礎的數組結構，通過下標隨機訪問元素又是非常基礎的操作，效率的優化就要儘可能的做到極致。
- 主要的原因是歷史原因，C語言的設計者是從0開始計數數組下標的,之後的Java、JS等語言都進行了效仿，或者說是為了減少從C轉向Java、JS等的學習成本。
二、什麼是數組?
- 數組是一個線性數據結構,用一組連續的內存空間存儲一組具有相同類型的數據。
- 其實數組、鏈表、棧、隊列都是線性表結構;樹、圖則是非線性表結構。
三、數組和鏈表的面試糾錯
- 數組中的元素存在一個連續的內存空間中, 而鏈表中的元素可以不存在於連續的內存空間。
- 數組支持隨機訪問，根據下標隨機訪問的時間複雜度是0(1);鏈表適合插入、刪除操作，時間複雜
度為O(1)。
四、容器是否完全替代數組?
容器的優勢:對於Java語言,容器封裝了數組插入、刪除等操作的細節,並且支持動態擴容。對於Java，一些更適合用數組的場景:
- Java的ArrayList無法存儲基本類型， 需要進行裝箱操作，而裝箱與拆箱操作都會有一定的性能消
耗，如果特別注意性能，或者希望使用基本類型，就可以選用數組。 - 若數組大小事先已知，並且對數組只有非常簡單的操作,不需要使用到ArrayList提供的大部分方
法，則可以直接使用數組。 - 多維數組時，使用數組會更加直觀。
五、JVM標記清除算法
GC最基礎的收集算法就是標記-清除算法，如同他們的名字一樣, 此算法分為「標記」、「清除」 兩個
階段,先標記出需要回收的對象,再統- -回收標記的對象。不足有二，一是效率不高， 二是產生碎片內
存空間。
大多數主流虛擬機採用可達性分析算法來判斷對象是否存活，在標記階段，會遍歷所有 GC ROOTS，將所有 GC ROOTS 可達的對象標記為存活。只有當標記工作完成後，清理工作才會開始。
不足：
- 效率問題。標記和清理效率都不高，但是當知道只有少量垃圾產生時會很高效。
- 空間問題。會產生不連續的內存空間碎片。
- 另外，對於數組訪問越界造成無限循環，我理解是編譯器的問題，對於不同的編譯器，在內存分配時，會按照內存地址遞增或遞減的方式進行分配。老師的程序，如果是內存地址遞減的方式，就會造成無限循環。
六、數組的內存尋址公式
一維數組:
$$
a[i]_address=base_address+i*typesize
$$
二維數組假設是，對於 $mn$ 的數組，$a[i]][j]$ (i < m,j < n)的地址為:
$$
a[i][j]_address=base_address + (in+j)typesize
$$
三維數組假設是，對於 $mn*q$ 的數組
$$
a[i][j][k]_address=base_address + (inq + jq + k)typesize
$$
04 鏈表(上): 如何實現LRU緩存淘汰算法?
一、什麼是鏈表？
- 和數組一樣，鏈表也是一種線性表。
- 從內存結構來看，鏈表的內存結構是不連續的內存空間，是將一組零散的內存塊串聯起來，從而進行數據存儲的數據結構。
- 鏈表中的每一個內存塊被稱為節點Node。節點除了存儲數據外，還需記錄鏈上下一個節點的地址，即後繼指針Next。
二、為什麼使用鏈表？即鏈表的特點
-
插入、刪除數據效率高O(1)級別（只需更改指針指向即可），隨機訪問效率低O(n)級別（需要從鏈頭至鏈尾進行遍歷）。
-
和數組相比，內存空間消耗更大，因為每個存儲數據的節點都需要額外的空間存儲後繼指針。
三、常用鏈表：單鏈表、循環鏈表和雙向鏈表
- 單鏈表
1）每個節點只包含一個指針，即後繼指針。
2）單鏈表有兩個特殊的節點，即首節點和尾節點。為什麼特殊？用首節點地址表示整條鏈表，尾節點的後繼指針指向空地址null。
3）性能特點：插入和刪除節點的時間複雜度為O（1），查找的時間複雜度為O(n)。 - 循環鏈表
1）除了尾節點的後繼指針指向首節點的地址外均與單鏈表一致。
2）適用於存儲有循環特點的數據，比如約瑟夫問題。 - 雙向鏈表
1）節點除了存儲數據外，還有兩個指針分別指向前一個節點地址（前驅指針prev）和下一個節點地址（後繼指針next）。
2）首節點的前驅指針prev和尾節點的後繼指針均指向空地址。
3）性能特點：
和單鏈表相比，存儲相同的數據，需要消耗更多的存儲空間。
插入、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例，刪除操作分為2種情況：給定數據值刪除對應節點和給定節點地址刪除節點。對於前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應節點進行刪除，時間複雜度為O(n)。對於第二種情況，要進行刪除操作必須找到前驅節點，單鏈表需要從頭到尾進行遍歷直到p->next = q，時間複雜度為O(n)，而雙向鏈表可以直接找到前驅節點，時間複雜度為O(1)。
對於一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p，每一次查詢時，根據要查找的值與p的大小關係，決定是往前還是往後查找，所以平均只需要查找一半的數據。 - 雙向循環鏈表：首節點的前驅指針指向尾節點，尾節點的後繼指針指向首節點。
四、選擇數組還是鏈表？
- 插入、刪除和隨機訪問的時間複雜度
數組：插入、刪除的時間複雜度是O(n)，隨機訪問的時間複雜度是O(1)。
鏈表：插入、刪除的時間複雜度是O(1)，隨機訪問的時間複雜端是O(n)。 - 數組缺點
1）若申請內存空間很大，比如100M，但若內存空間沒有100M的連續空間時，則會申請失敗，儘管內存可用空間超過100M。
2）大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數據複製，而這時非常費時的。 - 鏈表缺點
1）內存空間消耗更大，因為需要額外的空間存儲指針信息。
2）對鏈表進行頻繁的插入和刪除操作，會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。 - 如何選擇？
數組簡單易用，在實現上使用連續的內存空間，可以藉助CPU的緩衝機制預讀數組中的數據，所以訪問效率更高，而鏈表在內存中並不是連續存儲，所以對CPU緩存不友好，沒辦法預讀。
如果代碼對內存的使用非常苛刻，那數組就更適合。
五、應用
如何分別用鏈表和數組實現LRU緩衝淘汰策略？
-
什麼是緩存？
緩存是一種提高數據讀取性能的技術，在硬件設計、軟件開發中都有着非廣泛的應用，比如常見的CPU緩存、數據庫緩存、瀏覽器緩存等等。 -
為什麼使用緩存？即緩存的特點
緩存的大小是有限的，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？就需要用到緩存淘汰策略。 -
什麼是緩存淘汰策略？
指的是當緩存被用滿時清理數據的優先順序。 -
有哪些緩存淘汰策略？
常見的3種包括先進先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）。 -
鏈表實現LRU緩存淘汰策略
當訪問的數據沒有存儲在緩存的鏈表中時，直接將數據插入鏈表表頭，時間複雜度為O(1)；當訪問的數據存在於存儲的鏈表中時，將該數據對應的節點，插入到鏈表表頭,時間複雜度為O(n)。如果緩存被佔滿，則從鏈表尾部的數據開始清理，時間複雜度為O(1)。 -
數組實現LRU緩存淘汰策略
方式一：首位置保存最新訪問數據，末尾位置優先清理
當訪問的數據未存在於緩存的數組中時，直接將數據插入數組第一個元素位置，此時數組所有元素需要向後移動1個位置，時間複雜度為O(n)；當訪問的數據存在於緩存的數組中時，查找到數據並將其插入數組的第一個位置，此時亦需移動數組元素，時間複雜度為O(n)。緩存用滿時，則清理掉末尾的數據，且剩餘數組元素需整體後移一位，時間複雜度為O(n)。方式二：首位置優先清理，末尾位置保存最新訪問數據
當訪問的數據未存在於緩存的數組中時，直接將數據添加進數組作為當前最後一個元素時間複雜度為O(1)；當訪問的數據存在於緩存的數組中時，查找到數據並將其插入當前數組最後一個元素的位置，此時亦需移動數組元素，時間複雜度為O(n)。緩存用滿時，則清理掉數組首位置的元素，且剩餘數組元素需整體前移一位，時間複雜度為O(n)。（優化：清理的時候可以考慮一次性清理一定數量，從而降低清理次數，提高性能。）
六、設計思想
時空替換思想：「用空間換時間」 與 「用時間換空間」
當內存空間充足的時候，如果我們更加追求代碼的執行速度，我們就可以選擇空間複雜度相對較高，時間複雜度小相對較低的算法和數據結構，緩存就是空間換時間的例子。如果內存比較緊缺，比如代碼跑在手機或者單片機上，這時，就要反過來用時間換空間的思路。
七、課後習題
如何判斷一個字符串是否是迴文字符串的問題，我想你應該聽過，我們今天的題目就是基於這個問題的改造版本。如果字符串是通過單鏈表來存儲的，那該如何來判斷是一個迴文串呢？你有什麼好的解決思路呢？相應的時間空間複雜度又是多少呢？
方法一：半棧法
- 用快慢兩個指針遍歷，同時用棧copy慢指針指向的data。
- 完成後，慢指針指向中間節點，耗時為N/2.
- 最後用pop棧中的data和慢指針指向的data比較，耗時也是N/2.
所以時間複雜度為：Ｏ(N)，空間複雜度因棧額外存儲了一半的data，故為O(N/2)
方法二：全棧法
- 全部遍歷，data壓棧，額外空間消耗N
- 再次全部遍歷取data，同時pop棧取data, 二者比較，時間消耗2N。
所以時間複雜度為O(3N)，空間複雜度為O(N)。
該法算法最簡單，但複雜度高。可以用棧存儲節點指針，而非data來改進。
方法三：硬幹法
1. 一個指針從頭取data，另一個指針遍歷到底取data，比較二者，刪除尾部節點，重複１。
２
時間複雜度高達 O(N^2)，空間複雜度卻最低Ｏ(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
//leetcode.wang/leetcode-234-Palindrome-Linked-List.html
04 鏈表(下): 如何實現LRU緩存淘汰算法?
一、理解指針或引用的含義
- 含義：指針是一個變量，該變量中存的是其它變量的地址。將某個變量（對象）賦值給指針（引用），實際上就是就是將這個變量（對象）的地址賦值給指針（引用）。
- 示例：
p—>next = q; 表示p節點的後繼指針存儲了q節點的內存地址。
p—>next = p—>next—>next; 表示p節點的後繼指針存儲了p節點的下下個節點的內存地址。
二、警惕指針丟失和內存泄漏（單鏈表）
在插入和刪除結點時，要注意先持有後面的結點再操作，否者一旦後面結點的前繼指針被斷開，就無法再訪 問，導致內存泄漏。
- 插入節點
在節點a和節點b之間插入節點x，b是a的下一節點，，p指針指向節點a，則造成指針丟失和內存泄漏的代碼：p—>next = x;x—>next = p—>next; 顯然這會導致x節點的後繼指針指向自身。
正確的寫法是2句代碼交換順序，即：x—>next = p—>next; p—>next = x; - 刪除節點
在節點a和節點b之間刪除節點b，b是a的下一節點，p指針指向節點a：p—>next = p—>next—>next;
三、利用「哨兵」簡化實現難度
鏈表的插入、刪除操作，需要對插入第一個結點和刪除最後一個節點做特殊處理。利用哨兵對象可以不用邊界判斷，鏈表的哨兵對象是只存指針不存數據的頭結點。
-
什麼是「哨兵」？
鏈表中的「哨兵」節點是解決邊界問題的，不參與業務邏輯。如果我們引入「哨兵」節點，則不管鏈表是否為空，head指針都會指向這個「哨兵」節點。我們把這種有「哨兵」節點的鏈表稱為帶頭鏈表，相反，沒有「哨兵」節點的鏈表就稱為不帶頭鏈表。 -
未引入「哨兵」的情況
如果在p節點後插入一個節點，只需2行代碼即可搞定：new_node—>next = p—>next; p—>next = new_node;但，若向空鏈表中插入一個節點，則代碼如下：
if(head == null){ head = new_node;}如果要刪除節點p的後繼節點，只需1行代碼即可搞定：
p—>next = p—>next—>next;
但，若是刪除鏈表的最後一個節點（鏈表中只剩下這個節點），則代碼如下：if(head—>next == null){ head = null;}從上面的情況可以看出，針對鏈表的插入、刪除操作，需要對插入第一個節點和刪除最後一個節點的情況進行特殊處理。這樣代碼就會顯得很繁瑣，所以引入「哨兵」節點來解決這個問題。
-
引入「哨兵」的情況
「哨兵」節點不存儲數據，無論鏈表是否為空，head指針都會指向它，作為鏈表的頭結點始終存在。這樣，插入第一個節點和插入其他節點，刪除最後一個節點和刪除其他節點都可以統一為相同的代碼實現邏輯了。
四、重點留意邊界條件處理
經常用來檢查鏈表是否正確的邊界4個邊界條件：
- 如果鏈表為空時
- 如果鏈表只包含一個節點時
- 如果鏈表只包含兩個節點時
- 代碼邏輯在處理頭尾節點時
五、舉例畫圖，輔助思考
核心思想：釋放腦容量，留更多的給邏輯思考，這樣就會感覺到思路清晰很多。
六、多寫多練，沒有捷徑
5個常見的鏈表操作：
- 單鏈表反轉
- 鏈表中環的檢測
- 兩個有序鏈表合併
- 刪除鏈表倒數第n個節點
- 求鏈表的中間節點
練習題LeetCode對應編號：206，141，21，19，876
哨兵代碼優勢: 代碼2為什麼比代碼1性能更優? 為什麼代碼2少了一個比較?
原因如下,首先要明確作者舉兩個代碼例子的目的是為了說明”哨兵”的優勢.
我們先分析沒有哨兵的代碼1,邏輯很簡單,在遍曆數組的時候,挨個比較每一個元素是否等於key,另外我們要還判斷循環條件i是否小於n,如果相等了,那麼就退出循環遍歷,所以針對每一個元素判斷都進行了2次比較.
代碼2,一開始就把數組中最後一個元素修改成了目標key,while一次循環中,循環條件僅僅判斷當前數組元素是否等於key,對於跳出循環的條件是省略的,為什麼呢?因為前面說了,數組最後一個元素改成了key,最後肯定會在數組中找到key,也就是定會跳出. 於是最後我們只關注i是不是n-1就可以了,是n-1代表”原始整個數組”元素中的確沒有key.
05 棧：如何實現瀏覽器的前進和後退功能？
一、什麼是棧？
1.後進者先出，先進者後出，這就是典型的「棧」結構。
2.從棧的操作特性來看，是一種「操作受限」的線性表，只允許在端插入和刪除數據。
二、為什麼需要棧？
- 棧是一種操作受限的數據結構，其操作特性用數組和鏈表均可實現。
- 特定數據結構是對特定應用場景的抽象，數組和鏈表雖然使用起來更加靈活，但卻暴露了太多操作接口，更容易出錯。
- 所以，當某個數據集合只涉及在某端插入和刪除數據，且滿足後進者先出，先進者後出的操作特性時，我們應該首選棧這種數據結構。
三、如何實現棧？
-
棧的API
public class Stack<Item> { //壓棧 public void push(Item item){} //彈棧 public Item pop(){} //是否為空 public boolean isEmpty(){} //棧中數據的數量 public int size(){} //返回棧中最近添加的元素而不刪除它 public Item peek(){} } -
數組實現（自動擴容）
時間複雜度分析：根據均攤複雜度的定義，可以得數組實現（自動擴容）符合大多數情況是O(1)級別複雜度，個別情況是O(n)級別複雜度，比如自動擴容時，會進行完整數據的拷貝。
空間複雜度分析：在入棧和出棧的過程中，只需要一兩個臨時變量存儲空間，所以O(1)級別。我們說空間複雜度的時候，是指除了原本的數據存儲空間外，算法運行還需要額外的存儲空間。實現代碼：（棧的數組實現）
public class StackOfArray<Item> implements Iterable<Item>{ //存儲數據的數組 Item[] a = (Item[])new Object[1]; //記錄元素個數N int N = 0; //構造器 public StackOfArray(){} //添加元素 public void push(Item item){ //自動擴容 if (N == a.length ) resize(2*a.length ); a[N++] = item; } //刪除元素 public Item pop(){ Item item = a[--N]; a[N] = null; if (N > 0 && N == a.length / 4) resize(a.length / 2); return item; } //是否為空 public boolean isEmpty(){ return N == 0; } //元素個數 public int size(){ return N; } //改變數組容量 private void resize(int length) { Item[] temp = (Item[])new Object[length]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; }//可直接用 System.arraycopy //返回棧中最近添加的元素而不刪除它 public Item peek(){ return a[N-1]; } @Override public Iterator<Item> iterator() { return new ArrayIterator(); } //內部類 class ArrayIterator implements Iterator{ //控制迭代數量 int i = N; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { return a[--i]; } } } -
鏈表實現
時間複雜度分析：壓棧和彈棧的時間複雜度均為O(1)級別，因為只需更改單個節點的索引即可。
空間複雜度分析：在入棧和出棧的過程中，只需要一兩個臨時變量存儲空間，所以O(1)級別。我們說空間複雜度的時候，是指除了原本的數據存儲空間外，算法運行還需要額外的存儲空間。
實現代碼：（棧的鏈表實現）public class StackOfLinked<Item> implements Iterable<Item> { //定義一個內部類，就可以直接使用類型參數 private class Node{ Item item; Node next; } private Node first; private int N; //構造器 public StackOfLinked(){} //添加 public void push(Item item){ Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } //刪除 public Item pop(){ Item item = first.item; first = first.next; N--; return item; } //是否為空 public boolean isEmpty(){ return N == 0; } //元素數量 public int size(){ return N; } //返回棧中最近添加的元素而不刪除它 public Item peek(){ return first.item; } @Override public Iterator<Item> iterator() { return new LinkedIterator(); } //內部類：迭代器 class LinkedIterator implements Iterator{ int i = N; Node t = first; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { Item item = (Item) t.item; t = t.next; i--; return item; } } }
四、棧的應用
- 棧在函數調用中的應用
操作系統給每個線程分配了一塊獨立的內存空間，這塊內存被組織成「棧」這種結構，用來存儲函數調用時的臨時變量。每進入一個函數，就會將其中的臨時變量作為棧幀入棧，當被調用函數執行完成，返回之後，將這個函數對應的棧幀出棧。 - 棧在表達式求值中的應用（比如：34+13*9+44-12/3）
利用兩個棧，其中一個用來保存操作數，另一個用來保存運算符。我們從左向右遍歷表達式，當遇到數字，我們就直接壓入操作數棧；當遇到運算符，就與運算符棧的棧頂元素進行比較，若比運算符棧頂元素優先級高，就將當前運算符壓入棧，若比運算符棧頂元素的優先級低或者相同，從運算符棧中取出棧頂運算符，從操作數棧頂取出2個操作數，然後進行計算，把計算完的結果壓入操作數棧，繼續比較。 - 棧在括號匹配中的應用（比如：{}{()}）
用棧保存為匹配的左括號，從左到右一次掃描字符串，當掃描到左括號時，則將其壓入棧中；當掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數據，則說明為非法格式。
當所有的括號都掃描完成之後，如果棧為空，則說明字符串為合法格式；否則，說明未匹配的左括號為非法格式。 - 如何實現瀏覽器的前進後退功能？
我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X，當點擊後退按鈕時，再依次從棧X中出棧，並將出棧的數據一次放入Y棧。當點擊前進按鈕時，我們依次從棧Y中取出數據，放入棧X中。當棧X中沒有數據時，說明沒有頁面可以繼續後退瀏覽了。當Y棧沒有數據，那就說明沒有頁面可以點擊前進瀏覽了。
五、課後思考
1.我們在講棧的應用時，講到用函數調用棧來保存臨時變量，為什麼函數調用要用「棧」來保存臨時變量呢？用其他數據結構不行嗎？
其實，我們不一定非要用棧來保存臨時變量，只不過如果這個函數調用符合後進先出的特性，用棧這種數據結構來實現，是最順理成章的選擇。
從調用函數進入被調用函數，對於數據來說，變化的是什麼呢？是作用域。所以根本上，只要能保證每進入一個新的函數，都是一個新的作用域就可以。而要實現這個，用棧就非常方便。在進入被調用函數的時候，分配一段棧空間給這個函數的變量，在函數結束的時候，將棧頂複位，正好回到調用函數的作用域內。
2.我們都知道，JVM 內存管理中有個「堆棧」的概念。棧內存用來存儲局部變量和方法調用，堆內存用來存儲 Java 中的對象。那 JVM 裏面的「棧」跟我們這裡說的「棧」是不是一回事呢？如果不是，那它為什麼又叫作「棧」呢？
內存中的堆棧和數據結構堆棧不是一個概念，可以說內存中的堆棧是真實存在的物理區，數據結構中的堆棧是抽象的數據存儲結構。
內存空間在邏輯上分為三部分：代碼區、靜態數據區和動態數據區，動態數據區又分為棧區和堆區。
- 代碼區：存儲方法體的二進制代碼。高級調度（作業調度）、中級調度（內存調度）、低級調度（進程調度）控制代碼區執行代碼的切換。
- 靜態數據區：存儲全局變量、靜態變量、常量，常量包括final修飾的常量和String常量。系統自動分配和回收。
- 棧區：存儲運行方法的形參、局部變量、返回值。由系統自動分配和回收。
- 堆區：new一個對象的引用或地址存儲在棧區，指向該對象存儲在堆區中的真實數據。
06 隊列：隊列在線程池等有限資源池中的應用
一、如何理解「隊列」？
- 隊列是一種操作受限的線性表數據結構。
- 隊列最大的特點就是先進先出。
- 最基本的操作：入隊 enqueue()，放一個數據到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。
二、順序隊列和鏈式隊列
1、用數組實現的隊列叫順序隊列，用鏈表實現的隊列叫鏈式隊列。
2、隊列需要兩個指針：一個是 head 指針，指向隊頭；一個是 tail 指針，指向隊尾。
3、隨着不停地進行入隊、出隊操作，head 和 tail 都會持續往後移動。當 tail 移動到最右邊，即使數組中還有空閑空間，也無法繼續往隊列中添加數據了。
4、基於鏈表的實現，同樣需要兩個指針：head 指針和 tail 指針。分別指向鏈表的第一個結點和最後一個結點。入隊時，tail->next= new_node, tail = tail->next；出隊時，head = head->next。
三、循環隊列
1、循環隊列，原本數組是有頭有尾的，是一條直線。把首尾相連，扳成了一個環。
2、在數組實現隊列的時候，會有數據搬移操作，要想解決數據搬移的問題，需要像環一樣的循環隊列。
3、要想寫出沒有 bug 的循環隊列的實現代碼，最關鍵的是，確定好隊空和隊滿的判定條件。
1）隊列為空的判斷條件仍然是 head == tail。
2）當隊滿時，(tail+1)%n=head。 tail 指向的位置實際上是沒有存儲數據的。所以，循環隊列會浪費一個數組的存儲空間。
四、阻塞隊列和並發隊列
1、阻塞隊列
1）阻塞隊列就是在隊列基礎上增加了阻塞操作。
2）在隊列為空的時候，從隊頭取數據會被阻塞。因為此時還沒有數據可取，直到隊列中有了數據才能返回；如果隊列已經滿了，那麼插入數據的操作就會被阻塞，直到隊列中有空閑位置後再插入數據，然後再返回。
3）基於阻塞隊列實現的「生產者 – 消費者模型」，可以有效地協調生產和消費的速度。
當「生產者」生產數據的速度過快，「消費者」來不及消費時，存儲數據的隊列很快就會滿了，這時生產者就阻塞等待，直到「消費者」消費了數據，「生產者」才會被喚醒繼續生產。不僅如此，基於阻塞隊列，我們還可以通過協調「生產者」和「消費者」的個數，來提高數據處理效率，比如配置幾個消費者，來應對一個生產者。
2、並發隊列
1）在多線程的情況下，會有多個線程同時操作隊列，這時就會存在線程安全問題。能夠有效解決線程安全問題的隊列就稱為並發隊列。
2）最簡單直接的實現方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大並發度會比較低，同一時刻僅允許一個存或者取操作。
3）實際上，基於數組的循環隊列，利用 CAS 原子操作，可以實現非常高效的並發隊列。這也是循環隊列比鏈式隊列應用更加廣泛的原因。
五、線程池資源排隊處理策略
線程池沒有空閑線程時，新的任務請求線程資源時，線程池該如何處理？各種處理策略又是如何實現的呢？
一般有兩種處理策略。第一種是非阻塞的處理方式，直接拒絕任務請求；另一種是阻塞的處理方式，將請求排隊，等到有空閑線程時，取出排隊的請求繼續處理。
1、基於鏈表的實現方式，可以實現一個支持無限排隊的無界隊列（unbounded queue），但是可能會導致過多的請求排隊等待，請求處理的響應時間過長。所以，針對響應時間比較敏感的系統，基於鏈表實現的無限排隊的線程池是不合適的。
2、基於數組實現的有界隊列（bounded queue），隊列的大小有限，所以線程池中排隊的請求超過隊列大小時，接下來的請求就會被拒絕，這種方式對響應時間敏感的系統來說，就相對更加合理。不過，設置一個合理的隊列大小，也是非常有講究的。隊列太大導致等待的請求太多，隊列太小會導致無法充分利用系統資源、發揮最大性能。
（除了前面講到隊列應用在線程池請求排隊的場景之外，隊列可以應用在任何有限資源池中，用於排隊請求，比如數據庫連接池等。實際上，對於大部分資源有限的場景，當沒有空閑資源時，基本上都可以通過「隊列」這種數據結構來實現請求排隊。）
【思考】
1.除了線程池這種池結構會用到隊列排隊請求，還有哪些類似線程池結構或者場景中會用到隊列的排隊請求呢？
- 像windows操作系統的消息隊列，略高級一些帶有優先級。還有qt中的信號與槽函數機制，使用connect鏈接，其中的參數就是設置為把窗口界面消息放到消息隊列，然後一次取出。比如優先級消息，窗口系統關閉，優先級高，則就直接執行關閉操作。
- sockets網絡連接隊列。
- 數據庫連接隊列。
- 一種集群操作，很多客戶端像服務端請求資源，處理高並發大量請求。把這些請求放到隊列中。
- 分佈式應用中的消息隊列，也是一種隊列結構。
2.今天講到並發隊列，關於如何實現無鎖的並發隊列，網上有很多討論。對這個問題，你怎麼看？
考慮使用CAS實現無鎖隊列，則在入隊前，獲取tail位置，入隊時比較tail是否發生變化，如果否，則允許入隊，反之，本次入隊失敗。出隊則是獲取head位置，進行cas。
隊列的實現
1.隊列API
public interface Queue<T> {
public void enqueue(T item); //入隊
public T dequeue(); //出隊
public int size(); //統計元素數量
public boolean isNull(); //是否為空
}
2.用數組實現的隊列
老師的
// 用數組實現的隊列
public class ArrayQueue {
// 數組：items，數組大小：n
private String[] items;
private int n = 0;
// head表示隊頭下標，tail表示隊尾下標
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 如果tail == n 表示隊列已經滿了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
//解決數據遷移問題的入隊函數
// 入隊操作，將item放入隊尾
public boolean enqueue(String item) {
// tail == n表示隊列末尾沒有空間了
if (tail == n) {
// tail ==n && head==0，表示整個隊列都佔滿了
if (head == 0) return false;
// 數據搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之後重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
// 為了讓其他語言的同學看的更加明確，把--操作放到單獨一行來寫了
String ret = items[head];
++head;
return ret;
}
}
同學的
public class ArrayQueue {
//存儲數據的數組
private String[] items;
//記錄數組容量
private int n;
private int size;
//head記錄隊頭索引，tail記錄隊尾索引
private int head = 0;
private int tail = 0;
//申請一個指定容量的隊列
public ArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
/*
* 入隊：
* 1.堆滿的時，入隊失敗
* 1.1頻繁出入隊，造成數組使用不連續
* 1.2在入隊的時候，集中觸發進行數據搬移
* 2.在末尾插入數據，注意tail指向隊尾元素的索引+1
*/
public boolean enqueue(String item){
//表示隊滿
if(head == 0 && tail == n)
return false;
//表示需要數據搬移
else if(head != 0 && tail == n){
for (int i = head; i < tail; i++) {
items[i-head] = items[i];
}
tail = tail - head;
head = 0;
}
//將數據加入隊列
items[tail++] = item;
size++;
return true;
}
//出隊：1.隊空時，出隊失敗;2.出隊，head索引+1
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head++];
size--;
return res;
}
}
2.鏈表實現隊列
public class LinkedQueue {
//定義一個節點類
private class Node{
String value;
Node next;
}
//記錄隊列元素個數
private int size = 0;
//head指向隊頭結點，tail指向隊尾節點
private Node head;
private Node tail;
//申請一個隊列
public LinkedQueue(){}
//入隊
public boolean enqueue(String item){
Node newNode = new Node();
newNode.value = item;
if (size == 0) head = newNode;
else tail.next = newNode;
tail = newNode;
size++;
return true;
}
//出隊
public String dequeue(){
String res = null;
if(size == 0) return res;
if(size == 1) tail = null;
res = head.value;
head = head.next;
size--;
return res;
}
}
3.循環隊列
//老師的
public class CircularQueue {
// 數組：items，數組大小：n
private String[] items;
private int n = 0;
// head表示隊頭下標，tail表示隊尾下標
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數組
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 隊列滿了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
//同學的
public class LoopArrayQueue {
//存儲數據的數組
private String[] items;
//記錄數組容量
private int n;
private int size = 0;
//head記錄隊頭索引，tail記錄隊尾索引
private int head = 0;
private int tail = 0;
//申請一個指定容量的隊列
public LoopArrayQueue(int capacity){
items = new String[capacity];
n = capacity;
}
//入隊：關鍵在於隊滿的條件
public boolean enqueue(String item){
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
size++;
return true;
}
//出隊：關鍵在於隊空的條件
public String dequeue(){
String res = null;
if(head == tail) return res;
res = items[head];
head = (head + 1) % n;
size--;
return res;
}
}
