数据结构与算法 教学课件 张晓蕾 第五章.pdfVIP

第5章 栈和队列 第5章 栈和队列 5.1 栈 5.2 模板栈容器 5.3 队列的基本知识 5.4 模板队列容器 5.1 栈 5.1 栈 5.1.1 栈的定义及运算 5.1.1 栈的定义及运算 栈（stack ）是限定仅在表尾一端进行 栈（stack ）是限定仅在表尾一端进行 插入或删除操作的线性表。对于栈来说， 插入或删除操作的线性表。对于栈来说， 允许进行插入或删除的一端称为栈顶 允许进行插入或删除的一端称为栈顶 （top ），而另一端称为栈底（bottom ）。 （top ），而另一端称为栈底（bottom ）。 不含任何元素的栈称为空栈。栈中的元素 不含任何元素的栈称为空栈。栈中的元素 遵从“先进后出（LIFO ）”的原则。该原则 遵从“先进后出（LIFO ）”的原则。该原则 的含义如下： 的含义如下： 设有一个栈 设有一个栈 S＝{a0，a1，……，an-1} S＝{a0，a1，……，an-1} a0先进栈，an-1最后进栈。a0是栈底元素， a0先进栈，an-1最后进栈。a0是栈底元素， an-1是栈顶元素，如图5-1所示。出栈时， an-1是栈顶元素，如图5-1所示。出栈时， an-1最先出，a0最后出。因此，栈也称为 an-1最先出，a0最后出。因此，栈也称为 后进先出（LIFO ）的线性表。 后进先出（LIFO ）的线性表。 进栈 出栈 栈顶 an-1 … a0 a1 栈底 a0 图5-1 栈 图5-1 栈 5.1.2 栈的向量存储结构 5.1.2 栈的向量存储结构 栈也有两种存储结构，即向量存储结 栈也有两种存储结构，即向量存储结 构和链表存储结构。向量栈是顺序存储结 构和链表存储结构。向量栈是顺序存储结 构亦称顺序栈。它是利用地址连续的存储 构亦称顺序栈。它是利用地址连续的存储 单元依次存放从栈底到栈顶的数据元素， 单元依次存放从栈底到栈顶的数据元素， 同时设定一个top指针指向栈顶元素的当 同时设定一个top指针指向栈顶元素的当 前位置。 前位置。 通常用一维数组来实现向量栈，习惯 通常用一维数组来实现向量栈，习惯 上以下标小的一端做栈底。当top －1时为 上以下标小的一端做栈底。当top －1时为 空栈；当元素进栈时top++ ；当top等于最 空栈；当元素进栈时top++ ；当top等于最 大下标值时为栈满。向量存储结构描述如 大下标值时为栈满。向量存储结构描述如 下： 下： #define MAXSIZE 20 #define MAXSIZE 20 struct SqStack struct SqStack { { ELEMTYPE elem[MAXSIZE]; //