目錄

• 前言：
• 一、什麽是(shì)數據結構？
• 二、我們爲(wéi / wèi)什麽要(yào / yāo)了(le／liǎo)解數據結構？
• 三、Java中我們常見的(de)數據結構是(shì)哪些？
• • 棧（Stack）
  • • 概述：
    • 特點：
    • 場景：
  • 隊列（Queue）
  • • 概述：
    • 特點：
    • 場景：
  • 數組（Array）
  • • 概述：
    • 特點：
    • 場景：
  • 鏈表（Linked list）
  • • 概述：
    • 特點：
    • 場景：
  • 樹(Tree)
  • • 概述：
    • 特點：
    • 場景:

前言：

數據結構是(shì)計算機存儲和(hé / huò)組織數據的(de)方式。Java中的(de)集合就(jiù)是(shì)基于(yú)數據結構編寫出(chū)來(lái)的(de)，通過了(le／liǎo)解數據結構，我們再面對具體場景的(de)時(shí)候，就(jiù)能夠用精心選擇的(de)數據結構可以(yǐ)帶來(lái)更高的(de)運行或者存儲效率。

一、什麽是(shì)數據結構？

數據結構(Data Structure)是(shì)帶有結構特性的(de)數據元素的(de)集合，它研究的(de)是(shì)數據的(de)邏輯結構和(hé / huò)數據的(de)物理結構以(yǐ)及它們之(zhī)間的(de)相互關系，并對這(zhè)種結構定義相适應的(de)運算，設計出(chū)相應的(de)算法，并确保經過這(zhè)些運算以(yǐ)後所得到(dào)的(de)新結構仍保持原來(lái)的(de)結構類型。
簡而(ér)言之(zhī)，數據結構是(shì)相互之(zhī)間存在(zài)一種或多種特定關系的(de)數據元素的(de)集合，即帶“結構”的(de)數據元素的(de)集合。“結構”就(jiù)是(shì)指數據元素之(zhī)間存在(zài)的(de)關系，分爲(wéi / wèi)邏輯結構和(hé / huò)存儲結構。

二、我們爲(wéi / wèi)什麽要(yào / yāo)了(le／liǎo)解數據結構？

以(yǐ)做一道(dào)名菜“佛跳牆”爲(wéi / wèi)例：

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

要(yào / yāo)想做出(chū)來(lái)的(de)“佛跳牆”正宗、美味，就(jiù)需要(yào / yāo)我們按照正宗菜譜的(de)指導，分别用不(bù)同的(de)方法料理我們的(de)不(bù)同的(de)食材。

不(bù)同的(de)集合底層采用的(de)數據結構也(yě)是(shì)不(bù)一樣的(de)，我們了(le／liǎo)解這(zhè)些集合底層是(shì)基于(yú)哪些數據結構存儲和(hé / huò)組織數據，就(jiù)能在(zài)具體情景下針對具體問題做出(chū)更匹配的(de)選擇。

三、Java中我們常見的(de)數據結構是(shì)哪些？

常用結構有：棧、隊列、數組、鏈表和(hé / huò)紅黑樹。

棧（Stack）

概述：

它是(shì)運算受限的(de)線性表，其限制是(shì)僅允許在(zài)标的(de)一端進行插入和(hé / huò)删除操作，不(bù)允許在(zài)其他(tā)任何位置進行添加、查找、删除等操作。

特點：

棧的(de)入口、出(chū)口的(de)都是(shì)棧的(de)頂端位置。
先進後出(chū)原則（即，存進去的(de)元素，要(yào / yāo)在(zài)後它後面的(de)元素依次取出(chū)後，才能取出(chū)該元素）。

場景：

子(zǐ)彈壓進彈夾，先壓進去的(de)子(zǐ)彈在(zài)下面，後壓進去的(de)子(zǐ)彈在(zài)上(shàng)面，當開槍時(shí)，先彈出(chū)上(shàng)面的(de)子(zǐ)彈，然後才能彈出(chū)下面的(de)子(zǐ)彈。

隊列（Queue）

概述：

它同堆棧一樣，也(yě)是(shì)一種運算受限的(de)線性表，其限制是(shì)僅允許在(zài)表的(de)一端進行插入，而(ér)在(zài)表的(de)另一端進行删除。

特點：

隊列的(de)入口、出(chū)口各占一側。
先進先出(chū)原則（即，存進去的(de)元素，要(yào / yāo)在(zài)後它前面的(de)元素依次取出(chū)後，才能取出(chū)該元素）。

場景：

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

數組（Array）

概述：

是(shì)有序的(de)元素序列，數組是(shì)在(zài)内存中開辟一段連續的(de)空間，并在(zài)此空間存放元素。

特點：

查找元素快：通過索引，可以(yǐ)快速訪問指定位置的(de)元素
增删元素慢：數組無法改變長度，增删數組元素時(shí)，需要(yào / yāo)創建新數組，原數組元素根據新數組新的(de)索引位置一一複制。

場景：

學校宿舍房間号，按照一層層從左往右一間間的(de)順序依次排好，根據房間号找到(dào)對應宿舍的(de)人(rén)很快。但是(shì)要(yào / yāo)是(shì)更換房間号，就(jiù)需要(yào / yāo)将全部樓層的(de)都更換一次。

鏈表（Linked list）

概述：

由一系列結點Node（鏈表中每一個(gè)元素稱爲(wéi / wèi)一個(gè)結點）組成，結點可以(yǐ)在(zài)運行時(shí)動态生成。每個(gè)結點包括兩個(gè)部分：一個(gè)是(shì)存儲數據元素的(de)數據域，另一個(gè)是(shì)存儲下一個(gè)結點地(dì / de)址的(de)指針域。

特點：

查找元素慢：想查找某個(gè)元素，需要(yào / yāo)通過連接的(de)節點，依次向後查找指定元素。
增删元素快：隻需要(yào / yāo)修改連接元素的(de)地(dì / de)址值即可。

場景：

我們手機上(shàng)都存儲有别人(rén)的(de)手機号，要(yào / yāo)聯系之(zhī)前認識的(de)一個(gè)人(rén)，但是(shì)沒有他(tā)的(de)手機号，就(jiù)需要(yào / yāo)打電話找到(dào)有他(tā)手機号的(de)人(rén)，再聯系他(tā)。
我們要(yào / yāo)想以(yǐ)後繼續聯系，但是(shì)手機号碼存儲滿了(le／liǎo)，就(jiù)需要(yào / yāo)删除一個(gè)來(lái)保留這(zhè)個(gè)手機号。

樹(Tree)

概述：

樹是(shì)典型的(de)非線性結構，它是(shì)由n（n>0）個(gè)有限節點組成一個(gè)具有層次關系的(de)集合。把它叫做“樹”是(shì)因爲(wéi / wèi)它看起來(lái)像一棵倒挂的(de)樹，也(yě)就(jiù)是(shì)說(shuō)它是(shì)根朝上(shàng)，而(ér)葉朝下的(de)。

特點：

沒有父節點的(de)節點稱爲(wéi / wèi)根節點，每個(gè)數有且隻有一個(gè)根節點。
每一個(gè)非根節點有且隻有一個(gè)父節點。
每個(gè)節點有零個(gè)或多個(gè)子(zǐ)節點。

場景:

平衡二叉樹(紅黑樹)