同步博客：My Love
記錄一下在極客時間學習數據結構與算法的筆記凤类，將自己看到聽到的有關數據結構與算法的內容都記錄下來映挂。這是關于基礎數據結構的部分泽篮，包括數組、鏈表柑船、棧帽撑、隊列。
數組
數組是最基本的數據結構了鞍时，數組(Array)的定義是：數組是一種線性表數據結構亏拉，它用一組連續(xù)的內存空間存放一組具有相同類型數據。
這里有三個關鍵點逆巍，線性表及塘，連續(xù)的內存空間 和 相同類型。
線性表的數據結構除了數組還有：隊列锐极， 棧笙僚， 鏈表；與之對應的非線性表的數據結構有：樹灵再， 圖肋层。
連續(xù)存儲空間和相同數據類型這個特定決定了數組的本質，使其具有了“隨機訪問”的特性翎迁，但是也讓其在某些操作(比如插入栋猖、刪除元素)方面非常低效，是把雙刃劍吧汪榔，具體要根據使用場景來決定是否使用數組蒲拉。
數組的隨機訪問是通過數組基址和數組下標實現的，基址加上下標與數據寬度的乘積就是要訪問數據的地址痴腌，尋址公式：
a[i]_address = base_address + i * data_type_size
data_type_size就是數據的寬度雌团，也就是每個元素占用內存的大小，常用數據類型占用內存大小如下所示：
| type | byte | ch | bit |
|---|---|---|---|
| char | 1 | 字節(jié) | 8 |
| short | 2 | 字 | 16 |
| int | 4 | 雙字 | 32 |
| long | 8 | 四字 | 64 |
| char * | 4(32bit) 8(64bit) | 雙字, 四字 | 32,64 |
| float | 4 | 雙字 | 32 |
| double | 8 | 四字 | 64 |
可以用一個圖表示數組內存分布：
數組查找的時間復雜度是O(1)這種說法是不準確的士聪，應該說是數組按下標隨機訪問的時間復雜度是O(1)辱姨。
數組插入和刪除真的比較低效嗎？
看情況戚嗅，如果數組本來是有序的，要在數組中插入一個元素并保證插入后的數組還是有序的，那么這時的插入操作就是低效的懦胞；
如果數組本來就是無序的替久，只是用來保存數據的，這時插入數據時就可以不用搬移大量數據了只需要將第k位數據搬移到數組最后躏尉，然后將元素插入到第k位即可蚯根。
數組的刪除也可以先標記要刪除的位置，當數組不夠使用時再將標記過的元素刪除胀糜，這樣避免了多次刪除造成的多次數據搬移操作颅拦，降低性能損耗。JVM的垃圾回收也是使用的這個思想教藻。
注意的問題
-
數組越界問題
先看一段代碼：
int main(int argc, char* argv[]){ int i = 0; int arr[3] = {0}; for(; i<=3; i++){ arr[i] = 0; printf("hello world\n"); } return 0; }這段代碼的執(zhí)行結果是循環(huán)打印hello world距帅，而不是打印三次hello world。因為數組越界了括堤，a3正好是變量i的存儲位置碌秸，所以就一直循環(huán)了。
c語言沒做數組越界判定悄窃，Java有做讥电，編譯的時候會直接報錯。
-
容器能否完全代替數組轧抗？
當然不能恩敌，容器有一個弊端就是不能存儲基本類型的數據，都是封裝后的數據横媚。
當然這層封裝也有好處纠炮，對于數組的插入刪除操作在容器內都有對應實現，而且容器支持動態(tài)擴容分唾。
什么時候用數組抗碰，什么時候用容器呢？
比如Java ArrayList無法存儲基本類型绽乔，如int弧蝇， long，需要封裝成對應的Integer折砸，Long類才能存儲看疗，但是Autoboxing,Unboxing對性能有一定損耗，在關注性能的時候可以使用數組睦授，不怎么關注性能的時候使用容器两芳。
如果數據量大小已知，并且對數據的操作非常簡單去枷，可以選擇使用數組怖辆。
需要使用到多維數組時是复，直接使用數組會更加直觀，如Object[][] Array;但是容器的話需要這樣定義：ArrayList<ArrayList> array竖螃。
業(yè)務開發(fā)直接使用容器就行了淑廊，省時省力。對性能要求比較高的場景使用數組特咆，比如網絡框架季惩，性能要做到極致。
-
數組為什么從0開始編號腻格？
一般數組的下表我們是作為偏移量處理的画拾，在計算第k個元素的地址時直接使用``a[k]_address = base_address + k * type_size
就可以計算得到了，如果從1開始編號菜职，那么計算公式就變成了a[k]_address = base_address + (k-1)*type_size`青抛，計算級需要多一次減法計算，對于數組這種經常使用的數據結構些楣，會對性能造成損耗脂凶。歷史原因，C語言作者就是這樣做的愁茁，你能怎么樣蚕钦。
鏈表
這里沒有特殊說明鏈表指的都是單向無循環(huán)鏈表。
鏈表的插入和刪除不需要數據搬移鹅很，只需要考慮相鄰節(jié)點的指針改變即可嘶居，對應時間復雜度為O(1)锋华。
鏈表隨機訪問性能沒有數組好税课，需要從鏈表頭一個一個往下查找，所以時間復雜度是O(n)账忘。
雙向鏈表支持O(1)時間復雜度的情況下找到前驅節(jié)點菠齿，這就使雙向鏈表在某些情況下插入佑吝、刪除等操作比單鏈表簡單、高效绳匀。比如將新的節(jié)點插入到某個節(jié)點之前芋忿。
Java的LinkedHashMap這個容器就使用了雙向鏈表這種數據結構。
注意事項
-
鏈表與指針關系密切疾棵，有些語言沒有指針戈钢，取而代之的引用，都是一個意思是尔，都是表示用于存儲內容的內存地址殉了。
將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針拟枚，或者反過來說薪铜，指針中存儲了這個變量的內存地址指向了這個變量众弓，通過指針就能找到這個變量。
警惕內存泄漏和指針丟失隔箍，鏈表操作要注意順序田轧，了解當前改變的節(jié)點指向。
-
使用哨兵簡化難度鞍恢。對于插入頭節(jié)點和刪除尾節(jié)點的操作需要特殊處理，這時為了簡化難度每窖，可以使用一個哨兵節(jié)點作為頭節(jié)點帮掉，里面不存儲數據，只有一個指向第一個存儲數據的節(jié)點即可窒典，這樣不管時插入還是刪除都不用特殊處理蟆炊。
哨兵簡化編程的技巧在插入排序、歸并排序瀑志、動態(tài)規(guī)劃中都有使用涩搓。
-
重點留意邊界條件，在寫任何代碼時都要多想想可能會遇到哪些邊界情況或者異常情況劈猪，遇到后怎么處理昧甘。
鏈表為空時代碼能工作嗎？
鏈表只包含一個節(jié)點時能工作嗎战得？
鏈表只包含兩個節(jié)點時能工作嗎充边？
代碼在處理頭節(jié)點和尾節(jié)點時能工作嗎？
常侦。浇冰。。
畫圖輔助思考聋亡，很好的方法肘习，我一直在用。
多謝多練坡倔，沒捷徑漂佩。
鏈表與數組的比較
| 時間復雜度 | 數組 | 鏈表 |
|---|---|---|
| 插入刪除 | O(n) | O(1) |
| 隨機訪問 | O(1) | O(n) |
數組簡單易用，是連續(xù)存儲空間致讥，利用cpu的緩存機制可以預讀數組中的數據仅仆，訪問效率更高。鏈表相反垢袱，數據不是連續(xù)存儲墓拜，不能預讀。
數組缺點是大小固定请契，出現不夠用的情況時需要重新開辟數組空間并復制原有數組數據到新數組咳榜，費力耗時夏醉。鏈表不存在這個問題，理論上剩余內存空間有多大就可以創(chuàng)建多大的鏈表涌韩。
Java的ArrayList容器支持動態(tài)擴容的原理就是數組空間不夠用時就再申請一個更大的空間（默認是原數組大小的1.5倍）畔柔，將原有數據拷貝到新數組中，所以Java動態(tài)擴容再數據量很大的情況下會很耗時臣樱。比如一個1G大小的ArrayList要存滿后再加入數據就會申請一個1.5G大小的存儲空間靶擦，并把原來1G的數據拷貝到新申請的空間上，恐怖不雇毫。
如果代碼對內存要求嚴格玄捕，就用數組，因為鏈表需要額外空間存儲指向下一個節(jié)點的指針棚放，所以占用空間更多枚粘。而且對鏈表進行頻繁插入刪除操作會產生很多內存碎片，對于Java語言來說會導致頻繁GC飘蚯。
問題
-
如何使用鏈表實現最近最少使用策略LRU（Least Recently Used）馍迄？
思路如下：維護一個有序單鏈表L，將最近訪問的節(jié)點依次添加到鏈表中局骤。當有新的節(jié)點被訪問時攀圈，就先從頭遍歷鏈表L，如果數據已經存在于鏈表L中庄涡，就將包含這個數據的節(jié)點從原來的位置刪除量承，并添加到鏈表L的頭部；如果數據不在鏈表L中穴店，就將創(chuàng)建包含該數據的節(jié)點插入到鏈表L的頭部撕捍，不過插入前要判斷一下緩存是否已滿（因為緩存一般是指定大小的，不肯能把整個剩余內存空間都劃分成緩存）泣洞，如果緩存已滿忧风，就刪除尾節(jié)點后再將新建節(jié)點插入L頭部；如果緩存未滿球凰，直接插入頭部即可狮腿。
分析一下時間復雜度，不管緩存是否已滿呕诉，都需要從頭開始遍歷鏈表L缘厢，因此時間復雜度是O(n)。
-
如何判斷一個字符串是否是回文甩挫？
使用快慢指針定位中間節(jié)點贴硫，快指針每次遍歷兩個節(jié)點，慢指針每次便利一個節(jié)點，當快指針到達鏈表尾時英遭，慢指針所在的位置就是鏈表中間節(jié)點的位置间护。這里分中間節(jié)點是奇數還是偶數節(jié)點的問題，需要分開處理挖诸。
從中間節(jié)點開始對后半部分逆序汁尺，
前半部分和后半部分比較，判斷是否相等多律，相等就是回文痴突，不相等就不是回文
最后再將后半部分逆序復原
時間復雜度因為使用慢指針進行了便利，所以是O(n)狼荞，空間復雜度因為開辟了快慢指針(只有固定幾個)苞也，所以是O(1).
-
如何判斷鏈表中是否存在環(huán)？如果存在怎么求環(huán)的長度和入口節(jié)點
還是使用快慢指針粘秆， 如果兩個指針能相遇，就存在環(huán)收毫，而且相遇節(jié)點必在環(huán)內攻走。
先找到環(huán)內節(jié)點，根據這個節(jié)點找出環(huán)的長度n此再。
再使用兩個指針昔搂，先讓一個指針移動n個位置，然后兩個指針一起移動输拇，兩個指針相等的節(jié)點就是環(huán)的入口摘符。
棧
為什么有了數組，還需要棧策吠？從功能上來看逛裤，數組或鏈表確實可以替代棧，但是數組或鏈表比較靈活猴抹，暴露了太多操作接口带族，容易出錯。
當數據集合只涉及在一端插入和刪除元素蟀给，并且滿足后進先出蝙砌、先進后出的特性時，應該首選棧這種數據結構跋理。
如何實現一個棧
使用數組和鏈表都可以择克，用數組實現的棧我們叫做順序棧，使用鏈表實現的我們叫做鏈式棧前普。
順序棧的實現：
// 基于數組實現的順序棧
public class ArrayStack {
private String[] items; // 數組
private int count; // 棧中元素個數
private int n; // 棧的大小
// 初始化數組肚邢，申請一個大小為 n 的數組空間
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入棧操作
public boolean push(String item) {
// 數組空間不夠了，直接返回 false汁政，入棧失敗道偷。
if (count == n) return false;
// 將 item 放到下標為 count 的位置缀旁，并且 count 加一
items[count] = item;
++count;
return true;
}
// 出棧操作
public String pop() {
// 棧為空，則直接返回 null
if (count == 0) return null;
// 返回下標為 count-1 的數組元素勺鸦，并且棧中元素個數 count 減一
String tmp = items[count-1];
--count;
return tmp;
}
}
支持動態(tài)擴容的順序棧
上面基于數組實現的順序棧是大小固定的并巍，當棧滿后該怎么辦呢？總不能直接讓程序崩潰吧换途，這就涉及到動態(tài)擴容的內容了懊渡。
棧的動態(tài)擴容跟數組動態(tài)擴容一樣，因為順序棧就是基于數組的嘛军拟，棧滿后剃执，申請一個更大的數組，將原來的數據拷貝到新數組中后懈息，再插入新元素肾档。
這里插入操作時間復雜度分析會稍稍復雜一點，因為要考慮擴容的情況辫继，出棧操作時間復雜度還是O(1)怒见，這很簡單。入棧操作時姑宽，如果空間不夠遣耍，就要動態(tài)擴容，假設擴容為原數組的兩倍大小炮车，如果當前棧大小是K舵变，并且已滿，那么就需要做K個數據的搬移操作瘦穆。但是這種情況畢竟是少數纪隙，大多數情況下的時間復雜度還是O(1)，所以均攤時間復雜度就是O(1)扛或。
棧在函數中的應用
最常見的就是函數調用瘫拣，線程運行過程中會占用一塊獨立內存空間，這塊內存空間就是按棧這種數據結構組織的告喊，用于存放函數調用時的臨時變量麸拄，每進入一個函數，就會將臨時變量作為一個棧幀入棧黔姜，當調用完成后拢切，將對應棧幀出棧。
比如這樣一段程序：
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
對應的入棧情況就是下面這樣：
棧在表達式求值中的應用
如四則運算秆吵，要計算12+25*4-10/2的值淮椰，就可以將數字和運算符號分別存放在兩個棧中，從做向右遍歷表達式，遇到數組就直接壓入數字棧主穗，入到運算符就與棧頂運算符比較泻拦，如果比運算符棧頂元素的優(yōu)先級高，就將當前運算符壓入棧忽媒；如果比棧頂運算符優(yōu)先級低或者相同争拐，就從數字棧頂去除兩個操作數，進行計算晦雨，然后再壓入數字棧架曹；繼續(xù)比較。
棧在括號匹配中的應用
比如`{{[()]}`是合法的闹瞧，`{([]}`這種就是不合法的.
我們可以使用棧來從左到右依次掃描字符串绑雄，掃到左括號時就入棧，掃到右括號時就從棧頂取出一個左括號.
如果能夠匹配奥邮，比如`(`跟`)`匹配万牺，`[`跟`]`匹配，`{`跟`}`匹配洽腺，就繼續(xù)掃描剩下的字符串.
如果掃描過程中出現不能匹配的情況杏愤，或者棧內沒有數據，就是非法格式字符串已脓。
所有括號掃描完后，如果棧為空通殃，表示字符串合法度液，否則，字符串非法画舌，有未匹配的左括號堕担。
問題
-
為什么要用炸來保存函數臨時變量，用其他數據結構行不行曲聂？
為什么使用棧來保存函數臨時變量呢霹购？因為棧的特性和函數調用的特性啊，函數調用時相當于跳轉到函數所在的內存地址開始執(zhí)行指令朋腋，此時使用棧的話就比較方便齐疙，從函數所在地址開始分配一段棧空間旭咽，調用過程中的局部變量和函數參數都在這個棧內贞奋，調用完成后復位棧頂即可。用數組不能說不行穷绵，就是沒棧方便轿塔。
-
JVM內存管理中也有“堆棧”的概念，棧內存用來存儲局部變量和方法調用勾缭，堆內存用來存儲java對象揍障，那么jvm中的棧與數據結構的棧是一回事嗎？如果不是俩由，那jvm為什么要叫做棧呢毒嫡？
內存中的棧與數據結構中的棧不一樣，內存中的棧就是真實的物理內存采驻，數據結構中的棧指的是抽象的數據存儲結構审胚。
內存空間分三部分：代碼區(qū)、靜態(tài)數據區(qū)和動態(tài)數據區(qū)礼旅，動態(tài)數據區(qū)又分棧和堆膳叨。
代碼區(qū)存儲方法體的二進制代碼；靜態(tài)數據區(qū)存儲全局變量痘系、靜態(tài)常量菲嘴、常量，常量包括final修飾的常量和String常量汰翠，系統自動分配和回收龄坪。棧存放運行時方法的形參、局部變量复唤、返回值健田，由系統分配和回收；堆存放用戶分配的內存空間佛纫，c中由用戶自行管理妓局，java中由用戶申請，JVM釋放呈宇。
隊列
隊列的特性先進先出好爬，而且只能在一端進行插入，另一端進行刪除操作甥啄。跟棧一樣存炮，都是一種操作受限的線性表數據結構。
隊列根據實現方式的不同可以分為順序隊列和鏈式隊列蜈漓，使用數組實現的叫順序隊列穆桂，使用鏈表實現的叫鏈式隊列。
隊列的實現如下：
// 用數組實現的隊列
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;
}
// 入隊操作衣形，將 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;
}
}
這里需要注意入隊操作，當隊尾指針指向數組最后一個元素時倒源，再進行數據入隊操作時需要現將隊列數據進行搬移苛预，將head放到數組第一個元素所在位置，tail放到數組tail-head的位置笋熬。
使用鏈表實現的鏈式隊列：
public class QueueBasedOnLinkedList {
// 隊列的隊首和隊尾
private Node head = null;
private Node tail = null;
// 入隊
public void enqueue(String value) {
if (tail == null) {
Node newNode = new Node(value, null);
head = newNode;
tail = newNode;
} else {
tail.next = new Node(value, null);
tail = tail.next;
}
}
// 出隊
public String dequeue() {
if (head == null) return null;
String value = head.data;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
public void printAll() {
Node p = head;
while (p != null) {
System.out.print(p.data + " ");
p = p.next;
}
System.out.println();
}
private static class Node {
private String data;
private Node next;
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
}
}
鏈式隊列入隊和出隊沒有限制热某，直接進行指針的移動即可。
循環(huán)隊列
循環(huán)隊列設計比較巧妙胳螟，是將隊列尾與隊列頭邏輯連接的一種數據結構昔馋。
寫出循環(huán)隊列的關鍵是判斷出隊滿和隊空的條件，隊空的條件很好判斷糖耸，head==tail時隊列就是空的秘遏；隊列滿的條件稍微復雜一點，這里把隊列最后一個位置留出來不用嘉竟，當(tail+1)%length==head時邦危，隊列就是滿的，length是隊列的長度舍扰。
循環(huán)隊列實現如下：
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 void printAll() {
if (0 == n) return;
for (int i = head; i % n != tail; ++i) {
System.out.print(items[i] + " ");
}
System.out.println();
}
}
阻塞隊列與并發(fā)隊列
實際使用中陵且，有一個阻塞隊列，就是在隊列的基礎上增加了阻塞操作个束，在隊空的時候讀操作被阻塞慕购，直到有隊列有新數據存入，然后返回播急；在隊列滿時，插入操作阻塞售睹，直到隊列有空閑位置后再插入數據桩警，然后返回。
這其實就是生產者消費者模型昌妹，而且阻塞隊列很肯定不是一個生產者或者消費者捶枢，當有多個消費者時，多個線程會并發(fā)對隊列讀飞崖，這時就會有線程安全問題烂叔，那么如何實現一個線程安全的隊列呢？
線程安全的隊列也叫并發(fā)隊列固歪，最簡單的方法是在入隊和出隊操作上加鎖蒜鸡，但是鎖的粒度比較大導致并發(fā)度比較低胯努，同一時刻僅允許一個入隊或者出隊操作。實際中逢防，基于數組的循環(huán)隊列可以利用CAS原子操作叶沛，實現高效并發(fā)隊列。這也是循環(huán)隊列比鏈式隊列應用更加廣泛的原因忘朝。
問題
-
線程池沒有空閑線程時灰署，新的任務請求線程資源時，線程池該怎么處理局嘁，各種處理策略是怎么實現的溉箕？
一般有兩種處理策略，阻塞和非阻塞悦昵。阻塞就是直接拒絕任務請求肴茄，非阻塞就是排隊，新來的請求都放入到一個隊列中旱捧，等線程池有空閑線程時再從等待隊列中拿出請求處理独郎。
隊列一般使用基于數組的循環(huán)隊列，因為鏈式隊列沒有大小限制枚赡，來多少請求就加多少氓癌，如果請求過多，就會導致排隊等待時間過長贫橙，影響用戶體驗贪婉。使用循環(huán)隊列可以設置隊列大小，隊列滿后新的請求就不再處理卢肃，直接拒絕連接疲迂，這比較適合對響應時間敏感的系統。至于隊列的大小根據實際業(yè)務需要和服務器資源進行配置莫湘。
隊列可以應用到大部分資源有限的場景尤蒿，比如數據庫連接池。沒有空閑資源時就排隊幅垮，通過隊列這種數據結構實現排隊請求的機制腰池。
-
除了線程池用到排隊請求，還有那些場景用到了排隊忙芒？
分布式系統中消息隊列示弓，也是一種隊列結構。
-
關于無鎖并發(fā)隊列呵萨，有什么好的實現方法奏属？
可以使用CAS實現無鎖隊列，每次入隊前潮峦，獲取tail的位置囱皿，入隊時檢查tail是否發(fā)生了變化勇婴，如果沒有就正常入隊，否則入隊失敗铆帽，出隊是同樣的原地咆耿，出隊前檢查head的位置，出隊時比較head的位置是否發(fā)生了變化爹橱，如果沒有就正常出隊萨螺，否則出隊失敗。
