第三章 棧和隊列

一、棧的基本概念

1、棧的定義：

棧：隻允許在一段進行插入和删除的限定性線性表。

棧頂：線性表允許進行插入和删除的那一端。

棧低：不允許插入和删除的那一端。

空棧：不含任何元素的空表。

根據上述定義，每次進棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次出棧的總是目前棧中“最新”的元素，即最後進棧的元素。在下圖所示的棧中，元素是以a1，a2，a3，…，an的順序進棧的，而退棧的次序卻是an，…，a3，a2，a1。棧的修改是按後進先出的原則進行的。是以，棧又稱為後進先出的線性表，簡稱為LIFO表。

2、棧的抽象資料類型

棧的抽象資料類型定義

ADT Stack

資料元素：可以是任意類型的資料，但必須屬于同一個資料對象。

結構關系：棧中資料元素之間是線性關系。

基本操作：

（1）InitStack(S)

操作前提：S為未初始化的棧。

操作結果：将S初始化為空棧。

（2）ClearStack(S)

操作前提：棧S已經存在。

操作結果：将棧S置成空棧。

（3）IsEmpty(S)

操作前