稀疏數組、隊列的概念與實踐
目錄
一、前言
數據結構包括：線性結構和非線性結構。
1.1 線性結構
- 線性結構是最常見的數據結構，其特點是數據元素與下標之間存在一一對應的關係；
- 線性結構有兩種不同的存儲結構，即順序存儲結構（數組）和鏈式存儲結構（鏈表）。順序存儲的的線性表稱為順序表，順序表中存儲的數據在存儲空間上是連續的；鏈式存儲的線性表稱為鏈表，鏈表中的數據在存儲空間上不一定是連續的，元素節點中存放數據元素以及相鄰元素的地址信息。
- 線性結構常見的有：數組、隊列、鏈表和棧。
1.2 非線性結構
- 非線性結構包括：二維數組、多維數組、廣義表、圖結構和樹結構。
二、稀疏數組的概念與實踐
當一個二維數組存在大量無意義的數據時，可以選擇稀疏數組來保存該數組。
2.1 實際需求
在五子棋程序的實現中，存在存盤退出和續上盤的功能。
因為該二維數組的默認值是0，因此記錄了很多沒有意義的數據，故可以使用稀疏數組來保存該數組。
2.2 基本介紹
2.2.1 稀疏數組的處理方式是
- 記錄數組有幾行、幾列，有多少個不同的值；
- 把具有不同值得元素的行列及值記錄在一個小規模的數組中，從而實現縮小二維數組的規模。
2.2.2 應用舉例
轉換過後的數組說明：
- [0]列：表示原二維數組有6行7列，其中有8個數據值不是默認值。
- [1]列：表示原二維數組0行3列位置的數據值是22。其後的數據表示方式與此相似。
2.2.3 代碼實現
2.2.3.1 思路分析
- 二維數組 轉 稀疏數組的思路
- 遍歷 原始的二維數組，得到有效數據的個數 sum
- 根據sum 就可以創建 稀疏數組 sparseArr int[sum + 1] [3]
- 將二維數組的有效數據數據存入到 稀疏數組
- 稀疏數組轉原始的二維數組的思路
- 先讀取稀疏數組的第一行，根據第一行的數據，創建原始的二維數組，比如上面的 chessArr2 = int [11][11]
- 在讀取稀疏數組後幾行的數據，並賦給 原始的二維數組 即可.
2.2.3.2 code
代碼實現：//github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter03/SparseArray.java
三、隊列的概念及實踐
3.1 隊列簡介
- 隊列是一個有序列表，可以用數組或是鏈表來實現；
- 遵循先入先出的原則；
3.2 數組模擬隊列思路
隊列是有序的，使用數組機構來模擬隊列時，需要對數組作以下聲明：
-
maxSize是該隊列的最大容量；
-
因為隊列的輸入、輸出分別是從前後兩頭來處理，因此需要兩個變量front及rear來分別記錄隊列前後端的下標。front代表隊列頭，隨着數據輸出而改變；rear代表隊列尾，隨着數據輸入而變化。如下圖：
-
當我們將數據存入隊列是需要兩個步驟：首先判斷隊列是否已滿，若指針rear小於隊列的最大容量maxSize-1，則可以存入，否則不可以存入數據；第二步將尾指針往後移一位（rear++）。
-
在取數據的時候需要判斷隊列是否為空，若front==rear則表示隊列為空。
3.2.1 code
3.3 使用數組模擬環形隊列優化
對於3.2中的實現，存在一個問題就是數組只能使用一次就不能復用了，這裡可以使用一個簡單的算法，改進成一個環形的數組。（取模）
思路說明：
- front變量的含義做一個調整：front直接指向隊列的第一個元素，front的初始值變為0；
- rear變量的含義做一個調整：rear指向隊列的最後一個元素的後一個位置，因為需要空出一個空間作為約定，rear的初始值為0；
- 當隊列滿時，條件是(rear + 1) % maxSize = front 【滿】；
- 隊列為空時，rear == front 【空】；
- 隊列中有效的數據個數：(rear + maxSize – front) % maxSize
