武汉理工大学：《数据结构》 第三章 栈与队列

第三章栈与队列 3.1概述 栈与队列是两种特殊的线性表。即:在一般线性表的 操作时,插入或删除结点的位置是任意的,在表的中 间或两端都可以进行插入或删除操作,这样,每进行 个结点的插入或删除时必须先要定位(确定其被执 行操作结点的地址),因此实现操作比较费时。 而作为限定性的线性表栈和队列,其主要特点 是限定了操作位置,即不能随意在表的任意结点上进 行插入或删除操作而只能在表的一端或两端进行操作, 这样节省了定位时间并有特定规则。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 第三章 栈与队列 3.1 概述 栈与队列是两种特殊的线性表。即:在一般线性表的 操作时，插入或删除结点的位置是任意的，在表的中 间或两端都可以进行插入或删除操作，这样，每进行 一个结点的插入或删除时必须先要定位（确定其被执 行操作结点的地址），因此实现操作比较费时。 而作为限定性的线性表—栈和队列，其主要特点 是限定了操作位置，即不能随意在表的任意结点上进 行插入或删除操作而只能在表的一端或两端进行操作， 这样节省了定位时间并有特定规则

栈 它是一种只能在表的一端进行插入(称为进栈) 或删除(称为岀栈)操作的线性表,显然,这是一种 先进后出或后进先出型结构的线性表 二队列 它是一种只能在表的一端进行插入(称为进队) 操作,表的另一端进行删除(称为出队)操作的线性 表,显然,这是一种先进先出型结构。 栈与队列在许多求解非数值计算问题的程序中要 用到,在很多场合对各数据的处理有先后顺序要求时 经常使用栈或队列作为数据的暂存器来实现,当先产 生的数据先处理,后产生的数据后处理时,则利用队 列作为暂存器实现;若先产生的数据后处理,后产生 的数据先处理时则利用钱作为暂存器实现

武汉理工大学华夏学院-信息工程 系 二 队列 它是一种只能在表的一端进行插入（称为进队） 操作，表的另一端进行删除（称为出队）操作的线性 表，显然，这是一种先进先出型结构。 栈与队列在许多求解非数值计算问题的程序中要 用到，在很多场合对各数据的处理有先后顺序要求时， 经常使用栈或队列作为数据的暂存器来实现，当先产 生的数据先处理，后产生的数据后处理时，则利用队 列作为暂存器实现；若先产生的数据后处理，后产生 的数据先处理时，则利用栈作为暂存器实现。 一 栈 它是一种只能在表的一端进行插入（称为进栈） 或删除（称为出栈）操作的线性表，显然，这是一种 先进后出或后进先出型结构的线性表

三、栈与队列的存储结构 栈与队列有顺序存储结构和链式存储结构两 种。用顺序存储的方法存储的栈或队列称为顺 序栈或顺序队列; 用链式存储的方法存储的栈或队列称为链 式栈或链式队列。 下面分别阐述。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 栈与队列有顺序存储结构和链式存储结构两 种。用顺序存储的方法存储的栈或队列称为顺 序栈或顺序队列； 用链式存储的方法存储的栈或队列称为链 式栈或链式队列。 下面分别阐述。 三、栈与队列的存储结构

3.2栈 顺序栈 1.定义用顺序方法存储的栈称为顺序栈。 2.术语 栈顶允许进行操作的一端,称为栈顶。 栈底不允许进行操作的一端,称为栈底。 栈指针指向栈顶元素位置的一个整型变量,称 为栈指针。一般用top表示。 空栈栈中无元素的栈即栈指针指向零,即top=0 时的栈,称为空栈。 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 一、顺序栈 1. 定义 用顺序方法存储的栈称为顺序栈。 2. 术语 栈顶 允许进行操作的一端，称为栈顶。 栈底 不允许进行操作的一端，称为栈底。 栈指针 指向栈顶元素位置的一个整型变量，称 为栈指针。一般用top表示。 空栈 栈中无元素的栈即栈指针指向零,即top=0 时的栈，称为空栈。 3.2 栈

<心 3.顺序栈的描述 顺序栈一般用一个一维数组进行描述 且定义一个整型变量top作为栈指针。其 说明如下: 用C语彦描述为: #define n0 50 #define datatype datatype s/no/ Int top 定义的機构驷3所尔。 系

武汉理工大学华夏学院-信息工程 系 3. 顺序栈的描述 顺序栈一般用一个一维数组进行描述， 且定义一个整型变量top作为栈指针。其 说明如下： 定义的栈结构如图3-1所示。 用C语言描述为: #define n0 50 #define datatype datatype s[no]; int top;

进栈 no 出栈 栈顶 D C B mA-二栈底回 图3-1顺序栈示意图 <心D 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 A 3 n0 栈顶 图3-1顺序栈示意图 B C D · · · 栈底 进栈 2 1 0 出栈 top 3

4.顺序栈的操作 (1)构造一个空栈 设置(定义)一个数组后,将栈指针 置为零既可。top=-1 (2判断一个栈是否为空:top==-1? (3)判断一个栈是否为满 top==n0-1? (4)取栈J元素:W=stop] 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 4. 顺序栈的操作 (1)构造一个空栈 设置（定义）一个数组后，将栈指针 置为零既可。 top＝－1 （2)判断一个栈是否为空：top＝＝－1？ （3)判断一个栈是否为满： top＝＝n0－1？ （4)取栈顶元素： w＝s[top]

(5)进栈(又称压入)进栈就是在栈顶位 置往栈中添加元素。 操作原则是:首先判栈满否?若满,则上 溢;(这是要避免的)否则,可以进栈。进 栈时是先移动指针〔top=top+1)再进栈 例如,设有一栈区为s,n0=3,将ABC三个 元素依次进栈操作过程为:图3-2所示 图3-2顺序 栈进栈示意 图( top 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 （5） 进栈（又称压入）进栈就是在栈顶位 置往栈中添加元素。 操作原则是： 首先判栈满否？若满，则上 溢；（这是要避免的）否则，可以进栈。进 栈时是先移动指针（top=top+1)再进栈。 例如，设有一栈区为s ,n0=3 ，将A,B,C三个 元素依次进栈操作过程为： 图3-2所示 初态 top －1 栈 图3-2顺序 栈进栈示意 图

栈 A进栈 A top 栈 B进栈 B A top 栈 C进 B fon 2 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 A进栈 A top 0 栈 B进栈 B A top 1 栈 C进栈 C B A top 2 栈

图3-3进栈算法流程图 图3-出栈算法流程图 匚给x赋值 top top==nO 出栈操作* top-top+ /*栈空无 X=STope /*栈上溢错 元素出栈* SIt topI=X top=top /*进栈完成* /*出栈完成* 返回 返回 武汉理工大学华夏学院-信息工程 系

武汉理工大学华夏学院-信息工程 系 图3-3进栈算法流程图 top=top+1 S[top]=x /*进栈完成*/ /*栈上溢错*/ 给X赋值 返回 /*栈空无 元素出栈*/ X=S[top] top=top-1 /*出栈完成*/ 返回 /*出栈操作*/ 图3-5出栈算法流程图 是 是 top= =n0-1 top= = -1