資料結構與算法之美專欄筆記

資料結構與算法之美課後筆記

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;
  }
}

https://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)級别，因為隻需更改單個節點的索引即可。

實作代碼：（棧的連結清單實作）

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;
    }
}