第三章栈与队列 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;