【聲明：本文為原創(chuàng)文章,未經(jīng)同意,嚴(yán)禁轉(zhuǎn)載和抄襲,違者將追究其法律責(zé)任】

/?寫在前面的話?/

蘇世機(jī)試小課堂，考研機(jī)試不再慌！

公主號：蘇世學(xué)社考研? 蘇世計算機(jī)考研

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

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

數(shù)據(jù)結(jié)構(gòu)常用內(nèi)容介紹

1

棧

?

1.1 概念

棧是一種操作受限的線性表，只允許從一端插入和刪除數(shù)據(jù)。棧中的數(shù)據(jù)元素遵守“先進(jìn)后出”（FILO）的原則，允許元素插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的插入操作叫做進(jìn)棧，也叫壓棧、入棧，棧的刪除操作叫出棧、彈棧。

?

1.2 常用操作

?

1.3 棧的應(yīng)用——括號匹配

題目描述

給定一個只包括?(、)、{、}、[、]?的字符串，判斷字符串是否有效。有效字符串需滿足：（1）左括號必須用相同類型的右括號閉合。（2）左括號必須以正確的順序閉合。注意空字符串可被認(rèn)為是有效字符串。

示例

輸入:?“()”

輸出: true

輸入:?“()[]{}”

輸出: true

輸入:?“([)]”

輸出: false

輸入:?“{[]}”

輸出: true

算法思想

①：從左往右遍歷輸入的括號序列，左括號進(jìn)入②，右括號進(jìn)入③

②：入棧

③：出棧一個元素，看看能不能和當(dāng)前的右括號組成一對，如果不可以，則返回false；如果出棧異常（從空棧中出棧）也要返回false

④：如果順利遍歷成功，檢查棧中有沒有剩余元素。如果有，則返回false；如果沒有，則返回true

代碼展示和運(yùn)行結(jié)果

2

優(yōu)先隊(duì)列

2.1?概念

顧名思義，就是優(yōu)先級最大的排在隊(duì)列的頭部，優(yōu)先級是根據(jù)對象的compare方法比較獲取的，保證根節(jié)點(diǎn)的優(yōu)先級一定比子節(jié)點(diǎn)的優(yōu)先級更大。

?

2.2 常用操作

?

2.3?代碼示例

3

二叉樹

3.1?概念

二叉樹是樹中結(jié)點(diǎn)的度不大于2的有序樹，是一種最簡單最重要的樹。二叉樹是一棵空樹，或者是一棵由一個根節(jié)點(diǎn)和兩棵互不相交的分別稱作根的左子樹和右子樹組成的非空樹，左子樹和右子樹同樣都是二叉樹。

?

3.2?特殊類型

滿二叉樹：一個二叉樹只有度為0和2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這個二叉樹稱為滿二叉樹。

完全二叉樹：葉子結(jié)點(diǎn)只可能出現(xiàn)在層序最大的兩層上，并且某個結(jié)點(diǎn)的左分支下子孫的最大層序和右分支下子孫的最大層序相等或大1。

?

3.3?典型問題

利用隊(duì)列實(shí)現(xiàn)層序遍歷

用棧實(shí)現(xiàn)前序

用棧實(shí)現(xiàn)中序

用棧實(shí)現(xiàn)后續(xù)

蘇世學(xué)社旗下品牌，專注于計算機(jī)考研

計算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢前輩丨個性化指導(dǎo)