数据结构(C语言版)朱昌杰.pdf

第 3 章 栈 和 队 列 本章知识要点： 栈和队列的基本概念 栈和队列的顺序存储结构和链式存储结构 栈和队列的应用 3.1 栈 栈是一种特殊的线性表，它的逻辑结构和存储结构与线性表相同，其特殊性体现在 “运算受限 ，即无论往表中插入元素还是删除表中已有元素，都被限制在线性表的一端 进行。一般将表尾作为操作端，如图 3.1 所示。 图 3.1 操作仅在表一端进行 3.1.1 栈的定义 栈是限制在表的一端进行插入和删除操作的线性表。能够进行操作的一端是浮动端， 称为栈顶，通常用一个“栈顶指针”指示，它的位置会随着操作而发生变化；与此相对， 表的另一端是固定端，称为栈底 。如同线性表可以为空表一样，当栈中没有元素时称为 空栈。往栈中插入元素的操作称为入栈，删除栈中元素的操作称为出栈。如图 3.2 表示 了一个栈。 图 3.2 栈的示意图 根据栈的运算特性，所有操作都只在栈顶进行。如果将数据元素按照 a , a , a , …, a 1 2 3 n 的顺序依次入栈，则此时 a1 在栈底，an 在栈顶，如图 3.2 所示。当要取出数据时，则必 须按 an, an− 1, …, a1 的顺序进行。由此可知，an 作为栈顶元素总是最后入栈的，而最先出 栈；a1 作为栈底元素总是最先入栈的，而最后出栈。栈按照这种后进先出(LIFO，Last In First Out)或者先进后出(FILO，First In Last Out) 的原则来组织数据的，因此，它也被称为 46 数据结构（C 语言版） 后进先出或先进后出的线性表。 基于栈的特性，栈的抽象数据类型定义如下： ADT Stack { 数据对象 D：D＝{ a |a ∈ ElemSet, i=1,2,…,n, n≥0 } i i 数据关系 R：R＝{ a , a |a , a ∈ D, i=2,…,n } i-1 i i-1 i 约定 a 端为栈顶，a 端为栈底。 n 1 基本操作 P： InitStack(S) 操作结果：构造一个空栈 S StackEmpty(S) 初始条件：栈 S 已存在 操作结果：若栈 S 为空栈,则返回 TRUE,否则返回 FALSE StackFull(S) 初始条件：栈 S 已存在 操作结果：若栈 S 满,则返回 TRUE,否则返回 FALSE GetTop(S, e) 初始条件：栈 S 已存在 操作结果：若栈 S 非空,用 e 返回 S 的栈顶元素 Push(S, e) 初始条件：栈 S 已存在 操作结果：若栈 S 不满,插入元素 e 为新的栈顶元素 Pop(S, e) 初始条件：栈 S 已存在且非空 操作结果：若栈 S 非空,删除 S 的栈顶元素,并用 e 返回其值 } ADT Stack 3.1.2 栈的顺序存储结构 采用顺序存储结构的栈称为顺序栈，它需要一段连续的存储空间来存储栈中元素。 1. 顺序栈的类型定义 类似于顺序表的定义，通常用预先设定的足够大的一维数组来存放数据。由于栈顶 会随着插入和删除操作而发生变化，用整型变量 top 作为栈顶指针指示栈顶的当前位置。 栈底位置固定不变，可以设置在数组的任意端，一般将数组的下标端作为栈底。 顺序栈的类型描述如下：