文章目錄

• 概述
• 重點(diǎn)/難點(diǎn)/要點(diǎn)
• 知識(shí)點(diǎn)整理
• 練習(xí)

概述

棧和隊(duì)列是常用的基本數(shù)據(jù)結(jié)構(gòu)，不僅直接用于描述問題，而且作為輔助數(shù)據(jù)結(jié)構(gòu)大量用于算法實(shí)現(xiàn)中。從數(shù)據(jù)元素間的邏輯關(guān)系看，棧和隊(duì)列是線性結(jié)構(gòu)；從操作方式和操作集合看，棧和隊(duì)列與線性表有很多不同，有各自的特殊性，但都是操作受限的線性表。本章知識(shí)點(diǎn)的組織結(jié)構(gòu)如下圖所示：

重點(diǎn)/難點(diǎn)/要點(diǎn)

本章的重點(diǎn)是：

棧和隊(duì)列的操作特性；

棧和隊(duì)列基本操作的實(shí)現(xiàn)。

本章的難點(diǎn)是：

循環(huán)隊(duì)列的存儲(chǔ)方法；

循環(huán)隊(duì)列中隊(duì)空和隊(duì)滿的判定條件。

棧學(xué)習(xí)要點(diǎn)：
對(duì)于棧要抓住一條明線：棧的邏輯結(jié)構(gòu)→棧的存儲(chǔ)結(jié)構(gòu)→棧的實(shí)現(xiàn)。
對(duì)于棧的邏輯結(jié)構(gòu)，要從棧的定義入手，在與線性表的定義和操作比較的基礎(chǔ)上，得出棧的操作特性，最后給出棧的抽象數(shù)據(jù)類型定義。
對(duì)于棧的存儲(chǔ)結(jié)構(gòu)要把握兩條支線：順序棧和鏈棧，棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)都與線性表類似，本質(zhì)上是線性表的簡(jiǎn)化。
對(duì)于棧的主要抓住以下三條暗線。

順序棧和順序表的比較：將順序棧與順序表的存儲(chǔ)方法進(jìn)行比較，將順序棧的算法實(shí)現(xiàn)與順序表的算法實(shí)現(xiàn)進(jìn)行比較。

鏈棧和單鏈表的比較：將鏈棧與單鏈表的存儲(chǔ)方法進(jìn)行比較，將鏈棧的算法實(shí)現(xiàn)與單鏈表的算法實(shí)現(xiàn)進(jìn)行比較。

順序棧和鏈棧的比較；將順序棧與鏈棧的存儲(chǔ)方法進(jìn)行比較，將順序棧和鏈棧的算法實(shí)現(xiàn)進(jìn)行比較。

隊(duì)列學(xué)習(xí)要點(diǎn)：
對(duì)于隊(duì)列的教學(xué)要抓住一條明線：隊(duì)列的邏輯結(jié)構(gòu)→隊(duì)列的存儲(chǔ)結(jié)構(gòu)→隊(duì)列的實(shí)現(xiàn)。
對(duì)于隊(duì)列的邏輯結(jié)構(gòu)，要從隊(duì)列的定義出發(fā)，在與線性表的定義和操作比較的基礎(chǔ)上，得出隊(duì)列的操作特性，最后給出隊(duì)列的抽象數(shù)據(jù)類型定義。
對(duì)于隊(duì)列的存儲(chǔ)結(jié)構(gòu)要把握兩條支線：循環(huán)隊(duì)列和鏈隊(duì)列，隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)與線性表類似，本質(zhì)上是線性表的簡(jiǎn)化。
隊(duì)列的暗線與棧的暗線類似，此外，還要把握以下兩條暗線。

棧和隊(duì)列的比較：將二者的操作特性進(jìn)行比較，將二者的存儲(chǔ)結(jié)構(gòu)進(jìn)行比較，將二者的基本操作及其實(shí)現(xiàn)進(jìn)行比較，在不斷比較的過程中加深對(duì)棧和隊(duì)列的理解。

循環(huán)隊(duì)列的引入過程：不要直接引入循環(huán)隊(duì)列存儲(chǔ)方法，而要貫徹提出問題、分析問題、解決問題的方式逐漸引入循環(huán)隊(duì)列，一方面訓(xùn)練邏輯思維能力，另一方面也體現(xiàn)了存儲(chǔ)結(jié)構(gòu)的靈活性。

知識(shí)點(diǎn)整理

棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。棧中元素除了具有線性關(guān)系外，還具有后進(jìn)先出的特性。

棧的順序存儲(chǔ)結(jié)構(gòu)稱為順序棧，順序棧本質(zhì)上是順序表的簡(jiǎn)化。通常把數(shù)組中下標(biāo)為0的一端作為棧底，同時(shí)附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

實(shí)現(xiàn)順序?；静僮鞯乃惴ǖ臅r(shí)間復(fù)雜度均為O(1)。

棧的鏈接存儲(chǔ)結(jié)構(gòu)稱為鏈棧，通常用單鏈表表示，并且不用附加頭結(jié)點(diǎn)。

鏈棧的插入和刪除操作只需處理?xiàng)ｍ敿撮_始結(jié)點(diǎn)的情況，其時(shí)間復(fù)雜度均為O(1)。

隊(duì)列是只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。隊(duì)列中的元素除了具有線性關(guān)系外，還具有先進(jìn)先出特性。

順序隊(duì)列會(huì)出現(xiàn)假溢出問題，解決的辦法是用首尾相接的順序存儲(chǔ)結(jié)構(gòu)，稱為循環(huán)隊(duì)列。在循環(huán)隊(duì)列中，凡是涉及隊(duì)頭或隊(duì)尾指針的修改都需要將其求模。

在循環(huán)隊(duì)列中，隊(duì)空的判定條件是：隊(duì)頭指針=隊(duì)尾指針；在浪費(fèi)一個(gè)存儲(chǔ)單元的情況下，隊(duì)滿的判定條件是：（隊(duì)尾指針+1）%數(shù)組長(zhǎng)度=隊(duì)頭指針。

隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)稱為鏈隊(duì)列。鏈隊(duì)列通常附設(shè)頭結(jié)點(diǎn)，并設(shè)置隊(duì)頭指針指向頭結(jié)點(diǎn)，隊(duì)尾指針指向終端結(jié)點(diǎn)。

鏈隊(duì)列基本操作的實(shí)現(xiàn)本質(zhì)上也是單鏈表操作的簡(jiǎn)化，插入只考慮在鏈隊(duì)列的尾部進(jìn)行，刪除只考慮在鏈隊(duì)列的頭部進(jìn)行，其時(shí)間復(fù)雜度均為O(1)。

練習(xí)

棧
在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生上溢，因此對(duì)于入棧操作首先要判斷是否棧滿。（×）
棧結(jié)構(gòu)只允許在棧頂進(jìn)行存取操作，所有基本操作的時(shí)間復(fù)雜度均是O(1)。（√）
三個(gè)元素按a、b、c的次序進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則出棧序列一定是abc。（×）
在順序棧的類定義中，成員變量top是指針類型。（×）
設(shè)top表示棧頂元素所在下標(biāo)，順序棧的棧空條件是（B），棧滿條件是（D）。
A.top=0 B.top=-1 C.top=StackSize D.top=StackSize-1
鏈棧附設(shè)頭結(jié)點(diǎn)不會(huì)使插入、刪除等基本操作更加方便。（√）
在鏈棧中執(zhí)行入棧操作需要修改兩個(gè)指針，同單鏈表的插入操作一樣，修改指針有先后順序。（√）
在順序棧和鏈棧中，語句“top- -；”實(shí)現(xiàn)將top指向當(dāng)前棧頂元素的下一個(gè)元素。（×）

隊(duì)列
有三個(gè)元素按a、b、c的順序入隊(duì)，每個(gè)元素只能入隊(duì)一次，則出隊(duì)序列只能是abc。（√）
在順序隊(duì)列中，入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度均是O(1)。（×）
由于隊(duì)列的單向移動(dòng)性，順序隊(duì)列一定會(huì)發(fā)生假溢出現(xiàn)象。（×）
由于隊(duì)列只允許在線性表的兩端執(zhí)行存取操作，所有基本操作的時(shí)間復(fù)雜度均為O(1)。（√）
設(shè)存儲(chǔ)循環(huán)隊(duì)列的數(shù)組長(zhǎng)度為m，則(rear+1)%m實(shí)現(xiàn)將rear的值在循環(huán)意義下加1。（√）
在鏈隊(duì)列中附設(shè)頭結(jié)點(diǎn)，能夠使入隊(duì)和出隊(duì)操作更加方便。（√）
在循環(huán)隊(duì)列中，設(shè)front指向隊(duì)頭元素的前一個(gè)位置，則當(dāng)前的隊(duì)頭元素是（C）。
A.data[front] B.data[++front] C.data[(front+1)%m] D.data[front++]
在鏈隊(duì)列中，出隊(duì)操作在隊(duì)頭執(zhí)行，與rear指針無關(guān)。（B）（要判空）
若用一個(gè)長(zhǎng)度為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為4和2，則從隊(duì)列中刪除一個(gè)元素，再增加兩個(gè)元素后，rear的值是（0），front的值是（3）。

參考資料：《數(shù)據(jù)結(jié)構(gòu)（從概念到C++實(shí)現(xiàn)）》清華大學(xué)出版社，王紅梅

總結(jié)

以上是生活随笔為你收集整理的栈和队列学习要点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。