目錄

• 前言：
• 一、什么是數(shù)據(jù)結(jié)構(gòu)？
• 二、我們?yōu)槭裁匆私鈹?shù)據(jù)結(jié)構(gòu)？
• 三、Java中我們常見的數(shù)據(jù)結(jié)構(gòu)是哪些？
• • 棧（Stack）
  • • 概述：
    • 特點(diǎn)：
    • 場景：
  • 隊(duì)列（Queue）
  • • 概述：
    • 特點(diǎn)：
    • 場景：
  • 數(shù)組（Array）
  • • 概述：
    • 特點(diǎn)：
    • 場景：
  • 鏈表（Linked list）
  • • 概述：
    • 特點(diǎn)：
    • 場景：
  • 樹(Tree)
  • • 概述：
    • 特點(diǎn)：
    • 場景:

前言：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲和組織數(shù)據(jù)的方式。Java中的集合就是基于數(shù)據(jù)結(jié)構(gòu)編寫出來的，通過了解數(shù)據(jù)結(jié)構(gòu)，我們再面對具體場景的時候，就能夠用精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。

一、什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)(Data Structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。
簡而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合?！敖Y(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

二、我們?yōu)槭裁匆私鈹?shù)據(jù)結(jié)構(gòu)？

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

料理的一個環(huán)境 ------> 程序運(yùn)行的時候的環(huán)境
做一道正宗“佛跳墻” ------> 項(xiàng)目的一個具體需求
料理的大廚 ------> 編寫程序的程序員
料理的一些食材、器具 ------> 我們要編寫的一行行的代碼
“佛跳墻的菜譜” ------> 我們編寫代碼要用的數(shù)據(jù)結(jié)構(gòu)

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

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

三、Java中我們常見的數(shù)據(jù)結(jié)構(gòu)是哪些？

常用結(jié)構(gòu)有：棧、隊(duì)列、數(shù)組、鏈表和紅黑樹。

棧（Stack）

概述：

它是運(yùn)算受限的線性表，其限制是僅允許在標(biāo)的一端進(jìn)行插入和刪除操作，不允許在其他任何位置進(jìn)行添加、查找、刪除等操作。

特點(diǎn)：

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

場景：

子彈壓進(jìn)彈夾，先壓進(jìn)去的子彈在下面，后壓進(jìn)去的子彈在上面，當(dāng)開槍時，先彈出上面的子彈，然后才能彈出下面的子彈。

隊(duì)列（Queue）

概述：

它同堆棧一樣，也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。

特點(diǎn)：

隊(duì)列的入口、出口各占一側(cè)。
先進(jìn)先出原則（即，存進(jìn)去的元素，要在后它前面的元素依次取出后，才能取出該元素）。

場景：

射擊子彈，先進(jìn)入的子彈被先射出，然后再進(jìn)入一顆子彈。

數(shù)組（Array）

概述：

是有序的元素序列，數(shù)組是在內(nèi)存中開辟一段連續(xù)的空間，并在此空間存放元素。

特點(diǎn)：

查找元素快：通過索引，可以快速訪問指定位置的元素
增刪元素慢：數(shù)組無法改變長度，增刪數(shù)組元素時，需要創(chuàng)建新數(shù)組，原數(shù)組元素根據(jù)新數(shù)組新的索引位置一一復(fù)制。

場景：

學(xué)校宿舍房間號，按照一層層從左往右一間間的順序依次排好，根據(jù)房間號找到對應(yīng)宿舍的人很快。但是要是更換房間號，就需要將全部樓層的都更換一次。

鏈表（Linked list）

概述：

由一系列結(jié)點(diǎn)Node（鏈表中每一個元素稱為一個結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。

特點(diǎn)：

查找元素慢：想查找某個元素，需要通過連接的節(jié)點(diǎn)，依次向后查找指定元素。
增刪元素快：只需要修改連接元素的地址值即可。

場景：

我們手機(jī)上都存儲有別人的手機(jī)號，要聯(lián)系之前認(rèn)識的一個人，但是沒有他的手機(jī)號，就需要打電話找到有他手機(jī)號的人，再聯(lián)系他。
我們要想以后繼續(xù)聯(lián)系，但是手機(jī)號碼存儲滿了，就需要刪除一個來保留這個手機(jī)號。

樹(Tree)

概述：

樹是典型的非線性結(jié)構(gòu)，它是由n（n>0）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?#xff0c;也就是說它是根朝上，而葉朝下的。

特點(diǎn)：

沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，每個數(shù)有且只有一個根節(jié)點(diǎn)。
每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)。
每個節(jié)點(diǎn)有零個或多個子節(jié)點(diǎn)。

場景:

平衡二叉樹(紅黑樹)