數據結構 1 線性表詳解 鏈表、 棧 、 隊列 結合JAVA 詳解
- 2020 年 3 月 6 日
- 筆記
前言
其實在學習數據結構之前，我也是從來都沒了解過這門課，但是隨着工作的慢慢深入，之前學習的東西實在是不夠用，並且太皮毛了。太淺，只是懂得一些淺層的，我知道這個東西怎麼用，但是要優化、或者是解析，就不知道該咋弄了。比如JAVA 最有名的幾個容器:
- List
- Set
- MAP
- Queue
這些都是涉及到有關數據結構的，以及一些簡單的算法。排序、冒泡排序、二分法這些，都要涉及到時間複雜度、以及數據結構的知識，這門課，還是很重要的。
為了啥
其實數據結構，結構這個詞，就是將我們原本的一些數據，按照某種結構放到一起，為了更加便利以及後期對於這些數據的利用。不能胡來，亂放一遭，那樣整理起來很麻煩，並且不方便以後的二次利用。
平時使用的數據，要麼是基本類型、要麼就是引用類型、數組、這些就是最基本的。加入需要存一個比如層級結構的崗位，那普通的數組就沒有辦法了。
這裡我們所涉及到的內容其實就是 數據的 結構
結構分類
數據結構的分類，到底有哪些呢，如何去理解他們，就是我們本節課的內容。這裡我們將接觸到線性表、樹狀圖、圖存儲結構等
線性表
線性表其實和數組有些類似。我們都知道，所有數據的類型都可以通過
最基本的 數組 指針（引用類型） 這兩種最基本的類型構造。
線性表可以細分為：
- 順序表
- 鏈表
- 棧
- 隊列
本節課就圍繞線性表，將這幾種類型依次解釋清楚
順序表
順序表最常見的，當然就是數組（不等同數組），滿足 一對一 何謂一對一呢，就是其裏面存儲的元素，他們的類型，都是存在相同類型的關係，並且緊挨着連接起來的。例如：
String [] array = new String[] {"a","b","c"};類似於這種，除掉首元素和尾元素，每個元素前後都有相鄰的元素。這樣的我們就叫做順序表
JAVA 裏面我們知道最基本的List 接口，下面有一個 ArrayList
ArrayList 底層就是以一個數組，其就是一個順序表。
基本操作
我這裡全部以JAVA 為例。
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }通過這個構造函數，我們可以發現，傳入一個指定的大小數，大於0，則指定基本數組的大小為傳入大小。 雖然這個數組是支持自動擴容的，我們還是研究一下
add() 增加元素到尾部
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }ensureCapacityInternal是對數組的監測，若大小不足以容納，則擴容的機制
這裡的增加元素其實很簡單，就將元素放到size ，也就是容器當中元素數的位置，首次放入元素的時候，size 初始化就是0 而後自增，很簡單
add() 插入元素
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } rangeCheckForAdd 檢查插入位置有沒有超過數組大小。則直接拋出異常
擴容後，將插入點後面的元素往後移動一個位置，通過System.arraycopy複製方式實現
查找指定下標 get()
public E get(int index) { rangeCheck(index); return elementData(index); }這個就不細說了，太簡單了。
remove() 移除元素
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }這個和上面指定位置插入一個元素剛好相反，把指定位置的元素移除掉後，後面的元素往前移動一位，而後將最後元素的位置進行清理。
總結
順序表最大的特點是：查詢快，因為是數組，直接下標出。插入和移除就比較慢了。因為要移動、複製數組，很麻煩
鏈表
在上面我們已經說過了，任何的數據類型都可以通過最基本的數組和指針構造。鏈表也不例外，相比於數組，數組則是定長的，不管存儲的滿否，都申請了一定大小的內存空間，而鏈表則不是，鏈表的空間是隨用隨申請，數據的位置相比於數組，其實不連續的，一般來說，需要在元素上指定下一個元素的指針，來達成鏈接關係。
每個元素上都有一塊位置用於指向下一個元素（指針）
這裡我畫的不連續也就是為了表示元素的不連續性
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }鏈表在JAVA 當中最具代表性的就是 LinkedList(雙向鏈表)，就是每個元素會帶有它的上一個節點和下一個節點的指針，我們圖上畫出來的是單向鏈表。
add(E e)
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }新下掛一個節點的時候，將最後一個節點（null）保存到 l 下，然後構造出一個新節點，將本節點作為最後一個最後一個節點。
add(int Index,E e)
void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }這裡兩個參數，E 表示將要插入的元素，
兩邊鏈表斷開，new 一個新的節點，連接即可。
get(i) 查找
Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 鏈表的查找指定下標就比較費時了。需要一個個遍歷。其實是很麻煩的。
remove(i)
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }移除一個指定位置的節點，這個其實和增加一個節點時候其實是類似的。將上下節點對於這個節點的引用進行修改即可。
小結
鏈表還是比較適合於快速增加、刪除、不適合於索引。因為需要全盤遍歷
棧 Stack
堆還是按照數組為基礎實現的，只不過它是一個半開的數組，怎麼理解這個半開的數組呢，如圖，就好像一個瓶子一樣，往裏面丟元素，先進後出原則
入棧 push
將一個元素加入的棧裏面，此時的元素是最外層的一個元素，此時執行出棧命令，則這個元素會被刪除並返回
出棧 pop
刪除此堆棧頂部的對象，並將該對象作為此函數的值返回。
查看 peek
通過 peek 查看當前棧頂的元素，只是查看，並不執行刪除
隊列 Queue
隊列遵循先進先出原則
隊列還提供額外的插入，提取和檢查操作。 這些方法中的每一種都有兩種形式：如果操作失敗，則拋出一個異常，另一種返回一個特殊值（ null或false ，具體取決於操作）。
這裡使用 ArrayBlockingQueue 以數組實現的阻塞隊列
BlockingQueue<String> strings = new ArrayBlockingQueue<String>(2);一個有限的blocking queue由數組支持。 這個隊列排列元素FIFO（先進先出）。 隊列的頭部是隊列中最長的元素。 隊列的尾部是隊列中最短時間的元素。 新元素插入隊列的尾部，隊列檢索操作獲取隊列頭部的元素。
這是一個經典的「有界緩衝區」，其中固定大小的數組保存由生產者插入的元素並由消費者提取。 創建後，容量無法更改
入隊 add()/offer()/put()
add 和 offer 都可以將元素加入到隊列中。但是add 在超過隊列容量的時候會拋出異常，offer 則會返回false
而put 操作則會在隊列沒有空間的時候阻塞，直到隊列有空間執行
出隊 poll()/take()
- poll檢索並刪除此隊列的頭，如果此隊列為空，則返回 null 。
- take 在沒有元素的時候則會阻塞
小結
通過本小結，我們已經學習到了最基本的線性表，而線性表又包含哪些呢
- 順序表 ArrayList
- 鏈表 LinkedList
- 棧 Stack
- 隊列 Queue
下一節我們將繼續學習有關於字符串、數組、廣義表等內容
參考：
http://c.biancheng.net/view/3352.html
