考點4 棧和隊列

1.棧及其基本運算

（1）棧的基本概念。

棧實際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入運算與刪除運算都只在線性表的一端進行。

在棧中，允許插入與刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）。若棧中沒有元素稱為空棧，棧也被稱為“先進后出”表，或“后進先出”表。

（2）棧的特點。

根據棧的上述定義，棧具有以下特點。

●棧頂元素總是最后被插入的元素，也是最早被刪除的元素。

●棧底元素總是最早被插入的元素，也是最后才能被刪除的元素。

●棧具有記憶作用。

●在順序存儲結構下，棧的插入和刪除運算都不需要移動表中其他數據元素。

●棧頂指針top動態反映了棧中元素的變化情況。

（3）棧的順序存儲及其運算。

棧的狀態如圖1.1所示。

根據棧的狀態，可以得知棧的基本運算有以下3種。

●入棧運算：在棧頂位置插入一個新元素。

●退棧運算：取出棧頂元素并賦給一個指定的變量。

●讀棧頂元素：將棧頂元素賦給一個指定的變量。

2.隊列及其基本運算

（1）隊列的基本概念。

隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個稱為尾指針（rear）的指針指向隊尾元素；允許刪除的一端稱為排頭，通常用一個頭指針（front）指向頭元素的前一個位置。

因此，隊列又稱為“先進先出”（FIFO-First In First Out）的線性表。插入元素稱為入隊運算，刪除元素稱為退隊運算。

隊列的基本結構如圖1.2所示。

（2）循環隊列及其運算。

所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。

真考鏈接

考核概率為90%，此部分屬于必考知識點。該考點較為基礎，考生要理解棧和隊列的概念和特點，掌握棧和隊列的運算。

在循環隊列中，用尾指針（rear）指向隊列的尾元素，用頭指針（front）指向頭元素的前一個位置。因此，從頭指針（front）指向的后一個位置，直到尾指針（rear）指向的位置之間所有的元素均為隊列中的元素。循環隊列的初始狀態為空，即rear=front。

循環隊列的基本運算主要有兩種：入隊運算與退隊運算。

●入隊運算是指在循環隊列的隊尾加入一個新的元素。

●退隊運算是指在循環隊列的排頭位置退出一個元素，并賦給指定的變量。

小提示

棧是按照“先進后出”或“后進先出”的原則組織數據，而隊列是按照“先進先出”或“后進后出”的原則組織數據。這就是棧和隊列的不同。

真題精選

【例1】下列對隊列的敘述正確的是______。

A）隊列屬于非線性表

B）隊列按“先進后出”原則組織數據

C）隊列在隊尾刪除數據

D）隊列按“先進先出”原則組織數據

【答案】D

【解析】隊列是一種特殊的線性表，它只能在一端進行插入，在另一端進行刪除。允許插入的一端稱為隊尾，允許刪除的另一端稱為隊頭。隊列又稱為“先進先出”或“后進后出”的線性表，體現了“先到先服務”的原則。

【例2】下列關于棧的描述正確的是______。

A）在棧中只能插入元素而不能刪除元素

B）在棧中只能刪除元素而不能插入元素

C）棧是特殊的線性表，只能在一端插入或刪除元素

D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

【答案】C

【解析】棧是一種特殊的線性表。在這種特殊的線性表中，其插入和刪除操作只能在線性表的一端進行。