目錄

• 前言：
• 一、什麼是數據結構？
• 二、我們為什麼要了解數據結構？
• 三、Java中(zhōng)我們常見的數據結構是哪些？
• • 棧（Stack）
  • • 概述：
    • 特點：
    • 場景：
  • 隊列（Queue）
  • • 概述：
    • 特點：
    • 場景：
  • 數組（Array）
  • • 概述：
    • 特點：
    • 場景：
  • 鍊表（Linked list）
  • • 概述：
    • 特點：
    • 場景：
  • 樹(shù)(Tree)
  • • 概述：
    • 特點：
    • 場景:

前言：

數據結構是計算機存儲和(hé)組織數據的方式。Java中(zhōng)的集合就是基于數據結構編寫出來的，通(tōng)過了解數據結構，我們再面對具體場景的時候，就能夠用精心選擇的數據結構可(kě)以帶來更高的運行或者存儲效率。

一、什麼是數據結構？

數據結構(Data Structure)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和(hé)數據的物理結構以及它們之間的相互關(guān)系，并對這種結構定義相适應的運算，設計出相應的算法，并确保經過這些運算以後所得到的新結構仍保持原來的結構類型。
簡而言之，數據結構是相互之間存在一種或多種特定關(guān)系的數據元素的集合，即帶“結構”的數據元素的集合。“結構”就是指數據元素之間存在的關(guān)系，分為邏輯結構和(hé)存儲結構。

二、我們為什麼要了解數據結構？

以做一道名菜“佛跳牆”為例：

料理的一個(gè)環境 ------> 程序運行的時候的環境
做一道正宗“佛跳牆” ------> 項目的一個(gè)具體需求
料理的大廚 ------> 編寫程序的程序員
料理的一些食材、器(qì)具 ------> 我們要編寫的一行行的代碼
“佛跳牆的菜譜” ------> 我們編寫代碼要用的數據結構

要想做出來的“佛跳牆”正宗、美味，就需要我們按照正宗菜譜的指導，分别用不同的方法料理我們的不同的食材。

不同的集合底層采用的數據結構也是不一樣的，我們了解這些集合底層是基于哪些數據結構存儲和(hé)組織數據，就能在具體情景下(xià)針對具體問(wèn)題做出更匹配的選擇。

三、Java中(zhōng)我們常見的數據結構是哪些？

常用結構有：棧、隊列、數組、鍊表和(hé)紅黑樹(shù)。

棧（Stack）

概述：

它是運算受限的線性表，其限制是僅允許在标的一端進行插入和(hé)删除操作，不允許在其他任何位置進行添加、查找、删除等操作。

特點：

棧的入口、出口的都是棧的頂端位置。
先進後出原則（即，存進去的元素，要在後它後面的元素依次取出後，才能取出該元素）。

場景：

子(zǐ)彈壓進彈夾，先壓進去的子(zǐ)彈在下(xià)面，後壓進去的子(zǐ)彈在上面，當開槍時，先彈出上面的子(zǐ)彈，然後才能彈出下(xià)面的子(zǐ)彈。

隊列（Queue）

概述：

它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行删除。

特點：

隊列的入口、出口各占一側。
先進先出原則（即，存進去的元素，要在後它前面的元素依次取出後，才能取出該元素）。

場景：

射擊子(zǐ)彈，先進入的子(zǐ)彈被先射出，然後再進入一顆子(zǐ)彈。

數組（Array）

概述：

是有序的元素序列，數組是在内存中(zhōng)開辟一段連續的空間，并在此空間存放元素。

特點：

查找元素快：通(tōng)過索引，可(kě)以快速訪問(wèn)指定位置的元素
增删元素慢：數組無法改變長度，增删數組元素時，需要創建新數組，原數組元素根據新數組新的索引位置一一複制。

場景：

學校(xiào)宿舍房(fáng)間号，按照一層層從左往右一間間的順序依次排好，根據房(fáng)間号找到對應宿舍的人很快。但是要是更換房(fáng)間号，就需要将全部樓層的都更換一次。

鍊表（Linked list）

概述：

由一系列結點Node（鍊表中(zhōng)每一個(gè)元素稱為一個(gè)結點）組成，結點可(kě)以在運行時動(dòng)态生成。每個(gè)結點包括兩個(gè)部分：一個(gè)是存儲數據元素的數據域，另一個(gè)是存儲下(xià)一個(gè)結點地址的指針域。

特點：

查找元素慢：想查找某個(gè)元素，需要通(tōng)過連接的節點，依次向後查找指定元素。
增删元素快：隻需要修改連接元素的地址值即可(kě)。

場景：

我們手機上都存儲有别人的手機号，要聯系之前認識的一個(gè)人，但是沒有他的手機号，就需要打電話找到有他手機号的人，再聯系他。
我們要想以後繼續聯系，但是手機号碼存儲滿了，就需要删除一個(gè)來保留這個(gè)手機号。

樹(shù)(Tree)

概述：

樹(shù)是典型的非線性結構，它是由n（n>0）個(gè)有限節點組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因為它看起來像一棵倒挂的樹(shù)，也就是說它是根朝上，而葉朝下(xià)的。

特點：

沒有父節點的節點稱為根節點，每個(gè)數有且隻有一個(gè)根節點。
每一個(gè)非根節點有且隻有一個(gè)父節點。
每個(gè)節點有零個(gè)或多個(gè)子(zǐ)節點。

場景:

平衡二叉樹(shù)(紅黑樹(shù))