# 資料結構小結

簡單的小結，給各位簡略複習一下。

## 常見的資料結構
* 堆疊（Stack）
* 佇列（Queue）
* 陣列（Array）
* 連結串列（Linked List）
* 樹（Tree）
* 圖（Graph）
* 堆積（Heap）
* 雜湊表（Hash table）

目前已經提到的資料結構有
- [稀疏矩陣(Sparse Matrix)](https://hackmd.io/@Aquamay/Syd8UdLqu)
- [佇列(Queue)與環形佇列](https://hackmd.io/@Aquamay/S1eTd_LcO)
- [單向鏈結串列(Single Linked List)](https://hackmd.io/@Aquamay/HJxij_U9u)
- [雙向鏈結串列(Doubly Linked List)](https://hackmd.io/@Aquamay/rysZmo_cu)
- [棧(Stack)](https://hackmd.io/@Aquamay/rJQGIpu5O)
- [遞迴(Recursion)](https://hackmd.io/@Aquamay/BJ_2YSqqO)

## 稀疏矩陣(Sparse Matrix)


### 使用情況
當一個陣列有很多沒意義數據(0)或相同數據。

### 處理方法
第一列記錄陣列共幾列幾行並且有幾個非0的值。
第二列開始用於紀錄每個非0值在陣列第幾列第幾行、值為多少。

### 應用場景
- 五子棋盤中的下棋情況

## 佇列(Queue)


### 特徵
* 先進先出(FIFO)
* 有序列表，可以用陣列或連結串列來實現。
* Queue兩個指針：rear 佇列的尾部(含)、front 佇列的頭部(不含)。
* 新增數據時，front不動rear動；刪除數據時，rear不動front動 => 由尾端加入數據，由頭部取出。

### 思路
* front的初始值 = -1 , rear的初始值 = -1
* 判斷佇列為空 rear == front
* 判斷佇列為滿 rear = maxSize -1

### 環形佇列
* front的初始值 = 0 , rear的初始值 = 0
* 需預留一個儲存單元來判斷佇列是否為空還是滿
* 判斷佇列為空 rear == front
* 判斷佇列為滿 (rear+1) % maxSize == front
* 判斷佇列的有效數據個數 (rear + maxSzie - front) % maxSize

## 單向鏈結串列(Single Linked List)

鏈結串列以節點(node)來儲存資料，每個節點中包含兩個域：資料域(data)、指標域(next)，指標域用於指向下一個節點，將這些節點串連起來形成 Linked List，而最後一個節點則指向一個空值。


鏈結串列的各個節點不一定是連續存放的。

### 應用案例

客戶端發來好友編號21、1、19、38、5，要求按照編號大小順序將這幾位的資訊傳回來，為了速度不允許經過數據庫，那我們可以使用鏈結串列來解決。

### 常見面試題
1. 求鏈結串列中有效節點的個數
1. 查找鏈結串列中的倒數第k個結點 【新浪面試題】
1. 鏈結串列的反轉【騰訊面試題，有點難度】
1. 從尾到頭列印鏈結串列 【百度，要求 方式1：反向遍歷, 方式2：Stack棧】
1. 合併兩個有序的鏈結串列，合併之後的鏈結串列依然有序

### 缺點
1. 單向鏈結串列查找的方向只能是一個方向，而雙向鏈結串列可以向前或向後查找。
2. 單向鏈結串列不能自我刪除，需要靠輔助節點，而雙向鏈結串列則可以自我刪除。

## 雙向鏈結串列(Doubly Linked List)

示意圖


### 思路
* 遍歷方式和單向鏈結串列一樣，只是可以向前也可以向後查找
* 添加(默認加到雙向鏈結串列的最後)
-先找到雙向鏈結串列的最後節點
-`temp.next = newHeroNode`
-`newHeroNode.prev = temp`
* 修改的思路和原來的單向鏈結串列一樣
* 刪除
– 因為是雙向，因此我們可以實現自我刪除某個節點
– 直接找到要刪除的節點，比如 temp
– `temp.prev.next = temp.next`
– `temp.next.prev = temp.prev`

### 應用
- 約瑟夫問題(Josephus Problem)

## 棧(Stack)


### 特徵
* 先進後出(FILO)的有序列表
* 是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(top)，另一端為固定的一端，稱為棧底(bottom)。
* 入棧稱為PUSH，出棧稱為POP，PUSH和POP的順序和現實生活中堆書本是一樣的。

### 應用場景
1. 子程序的調用：在跳往子程序前，會先將下個指令的地址存在棧中，直到子程序執行完後再將地址取出，以回到原來的程序中。
1. 處理遞歸調用：和子程序的調用類似，只是除了儲存下一個指令的地址外，也將參數、區域變數等數據存入到棧中。
1. 表達式的轉換[中綴表達式轉後綴表達式]與求值
1. 二元樹的遍歷
1. 圖形的深度優先搜尋法(DFS)

## 遞迴(Recursion)

遞迴就是一個函式直接或間接的呼叫自己本身，用相同的方法解決重複性的問題，有助於programmer解決複雜的問題，同時可以讓代碼變得簡潔。


### 應用場景
1. 各種數學問題如：八皇后問題、河內塔、階乘問題、迷宮問題、球和籃子、費氏數列的問題
1. 各種演算法中也會使用到遞迴，比如：快速排序法、合併排序法、二分搜尋法、分治法…等。
1. 將用棧解決的問題改為遞迴，程式碼會比較簡潔。