數據結構

數據結構是計算機存儲、組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合。

通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。

1.數據結構的基本功能

(1)如何插入一條新的數據項

(2)如何尋找某一特定的數據項

(3)如何刪除某一特定的數據項

(4)如何迭代的訪問各個數據項，以便進行顯示或其他操作

2.常用的數據結構

數組Array、棧Stack、隊列Queue，鏈表 linked List、樹Tree、哈希表Hash、堆Heap、圖Graph

算法

算法簡單來說就是解決問題的步驟。

在Java中，算法通常都是由類的方法來實現的。前面的數據結構，比如鏈表為啥插入、刪除快，而查找慢，平衡的二叉樹插入、刪除、查找都快，這都是實現這些數據結構的算法所造成的。后面我們講的各種排序實現也是算法范疇的重要領域。

1.算法的五個特征

(1)有窮性：對于任意一組合法輸入值，在執行又窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內完成。

(2)確定性：在每種情況下所應執行的操作，在算法中都有確切的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且在任何條件下，算法都只有一條執行路徑。

(3)可行性：算法中的所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。

(4)有輸入：作為算法加工對象的量值，通常體現在算法當中的一組變量。有些輸入量需要在算法執行的過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。

(5)有輸出：它是一組與“輸入”有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法功能。

2.算法的設計原則

(1)正確性：首先，算法應當滿足以特定的“規則說明”方式給出的需求。其次，對算法是否“正確”的理解可以有以下四個層次：

1)程序語法錯誤。

2)程序對于幾組輸入數據能夠得出滿足需要的結果。

3)程序對于精心選擇的、典型、苛刻切帶有刁難性的幾組輸入數據能夠得出滿足要求的結果。

4)程序對于一切合法的輸入數據都能得到滿足要求的結果。

PS：通常以第 三 層意義的正確性作為衡量一個算法是否合格的標準。

(2)可讀性：算法為了人的閱讀與交流，其次才是計算機執行。因此算法應該易于人的理解;另一方面，晦澀難懂的程序易于隱藏較多的錯誤而難以調試。

(3)健壯性：當輸入的數據非法時，算法應當恰當的做出反應或進行相應處理，而不是產生莫名其妙的輸出結果。并且，處理出錯的方法不應是中斷程序執行，而是應當返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。

(4)高效率與低存儲量需求：通常算法效率值得是算法執行時間;存儲量是指算法執行過程中所需要的最大存儲空間，兩者都與問題的規模有關。

前面三點 正確性，可讀性和健壯性相信都好理解。對于第四點算法的執行效率和存儲量，我們知道比較算法的時候，可能會說“A算法比B算法快兩倍”之類的話，但實際上這種說法沒有任何意義。因為當數據項個數發生變化時，A算法和B算法的效率比例也會發生變化，比如數據項增加了50%，可能A算法比B算法快三倍，但是如果數據項減少了50%，可能A算法和B算法速度一樣。所以描述算法的速度必須要和數據項的個數聯系起來。也就是“大O”表示法，它是一種算法復雜度的相對表示方式，這里我簡單介紹一下，后面會根據具體的算法來描述。

相對(relative)：你只能比較相同的事物。你不能把一個做算數乘法的算法和排序整數列表的算法進行比較。但是，比較2個算法所做的算術操作(一個做乘法，一個做加法)將會告訴你一些有意義的東西;

表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個單一變量。這個變量的選擇基于觀察或假設。例如，排序算法之間的對比通常是基于比較操作(比較2個結點來決定這2個結點的相對順序)。這里面就假設了比較操作的計算開銷很大。但是，如果比較操作的計算開銷不大，而交換操作的計算開銷很大，又會怎么樣呢?這就改變了先前的比較方式;

復雜度(complexity)：復雜度就是相對其他東西的度量結果。

算法的存儲量，包括：

程序本身所占空間;

輸入數據所占空間;

輔助變量所占空間;

數據結構必須具有以下基本功能：

(1)如何插入一條新的數據項

(2)如何尋找某一特定的數據項

(3)如何刪除某一特定的數據項

(4)如何迭代的訪問各個數據項，以便進行顯示或其他操作

數組的局限性分析：

(1)插入快，對于無序數組，上面我們實現的數組就是無序的，即元素沒有按照從大到小或者某個特定的順序排列，只是按照插入的順序排列。無序數組增加一個元素很簡單，只需要在數組末尾添加元素即可，但是有序數組卻不一定了，它需要在指定的位置插入。

(2)查找慢，當然如果根據下標來查找是很快的。但是通常我們都是根據元素值來查找，給定一個元素值，對于無序數組，我們需要從數組第一個元素開始遍歷，直到找到那個元素。有序數組通過特定的算法查找的速度會比無需數組快，后面我們會講各種排序算法。

(3)刪除慢，根據元素值刪除，我們要先找到該元素所處的位置，然后將元素后面的值整體向前面移動一個位置。也需要比較多的時間。

(4)數組一旦創建后，大小就固定了，不能動態擴展數組的元素個數。如果初始化你給一個很大的數組大小，那會白白浪費內存空間，如果給小了，后面數據個數增加了又添加不進去了。

棧的基本概念

棧(英語：stack)又稱為堆棧或堆疊，棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據(最后一個數據被第一個讀出來)。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom);棧底固定，而棧頂浮動;棧中元素個數為零時稱為空棧。插入一般稱為進棧(PUSH)，刪除則稱為退棧(POP)。

由于堆疊數據結構只允許在一端進行操作，因而按照后進先出(LIFO, Last In First Out)的原理運作。棧也稱為后進先出表。

隊列：

隊列(queue)是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進行刪除操作，而在表的后端(rear)進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出(FIFO—first in first out)線性表。

隊列分為：

1.單向隊列(Queue)：只能在一端插入數據，另一端刪除數據。

與棧不同的是，隊列中的數據不總是從數組的0下標開始的，移除一些隊頭front的數據后，隊頭指針會指向一個較高的下標位置

隊列中新增一個數據時，隊尾的指針rear 會向上移動，也就是向下標大的方向。移除數據項時，隊頭指針 front 向上移動。

在計算機中也可以在隊列中刪除一個數之后，隊列整體向前移動，但是這樣做效率很差。我們選擇的做法是移動隊頭和隊尾的指針。

為了避免隊列不滿卻不能插入新的數據，我們可以讓隊尾指針繞回到數組開始的位置，這也稱為“循環隊列”。

2.雙向隊列(Deque)：每一端都可以進行插入數據和刪除數據操作。

雙端隊列就是一個兩端都是結尾或者開頭的隊列， 隊列的每一端都可以進行插入數據項和移除數據項，這些方法可以叫做：

insertRight()、insertLeft()、removeLeft()、removeRight()

如果嚴格禁止調用insertLeft()和removeLeft()(或禁用右端操作)，那么雙端隊列的功能就和前面講的棧功能一樣。

如果嚴格禁止調用insertLeft()和removeRight(或相反的另一對方法)，那么雙端隊列的功能就和單向隊列一樣了。

3.優先級隊列，優先級隊列是比棧和隊列更專用的數據結構，在優先級隊列中，數據項按照關鍵字進行排序，關鍵字最小(或者最大)的數據項往往在隊列的最前面，而數據項在插入的時候都會插入到合適的位置以確保隊列的有序。

優先級隊列(priority queue)是比棧和隊列更專用的數據結構，在優先級隊列中，數據項按照關鍵字進行排序，關鍵字最小(或者最大)的數據項往往在隊列的最前面，而數據項在插入的時候都會插入到合適的位置以確保隊列的有序。

優先級隊列 是0個或多個元素的集合，每個元素都有一個優先權，對優先級隊列執行的操作有：

(1)查找

(2)插入一個新元素

(3)刪除

一般情況下，查找操作用來搜索優先權最大的元素，刪除操作用來刪除該元素 。對于優先權相同的元素，可按先進先出次序處理或按任意優先權進行。

棧和隊列這兩種數據結構，總結一下：

1.棧、隊列(單向隊列)、優先級隊列通常是用來簡化某些程序操作的數據結構，而不是主要作為存儲數據的。

2.在這些數據結構中，只有一個數據項可以被訪問。

3.棧允許在棧頂壓入(插入)數據，在棧頂彈出(移除)數據，但是只能訪問最后一個插入的數據項，也就是棧頂元素。

4.隊列(單向隊列)只能在隊尾插入數據，對頭刪除數據，并且只能訪問對頭的數據。而且隊列還可以實現循環隊列，它基于數組，數組下標可以從數組末端繞回到數組的開始位置。

5.優先級隊列是有序的插入數據，并且只能訪問當前元素中優先級別最大(或最小)的元素。

6.這些數據結構都能由數組實現，但是可以用別的機制(鏈表、堆等數據結構)實現。

以上就是動力節點小編介紹的"數據結構與算法分析"，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為您服務。