第三章堆栈和队列 31堆栈( Stack) 基本概念、抽象数据类型、顺序表示和实现、链 式表示和实现 32堆栈应用 括号匹配问题 33队列( Queue) 基本概念、抽象数据类型、顺序队列、顺序循环 队列、链式队列、队列的应用
1 3.1 堆栈（Stack） 基本概念、抽象数据类型、顺序表示和实现、链 式表示和实现 3.2 堆栈应用 括号匹配问题 3.3 队列（Queue） 基本概念、抽象数据类型、顺序队列、顺序循环 队列、链式队列、队列的应用 第三章 堆栈和队列
堆栈的基本概念 1.定义限定只能在表的一端进行插入和删除操作的线性表 特点:后进先出。 2.逻辑结构与线性表相同,仍为一对一(1:1)关系。 3.存储结构用顺序栈或链栈存储均可,但以顺序栈更常见 4.运算规则只能在栈顶运算,且访问结点时依照后进先出 LIFO)或先进后出(FILO)的原则 5.实现方式关键是编写入栈和出栈函数,具体实现依顺 序栈或链栈的存储结构有别而不同。 基本操作有:建栈、判断栈满或栈空、入栈、出栈、 读栈顶元素值等等
2 1. 定义 一、堆栈的基本概念 与线性表相同，仍为一对一( 1:1)关系。 用顺序栈或链栈存储均可，但以顺序栈更常见 只能在栈顶运算，且访问结点时依照后进先出 （LIFO）或先进后出（FILO）的原则。 关键是编写入栈和出栈函数，具体实现依顺 序栈或链栈的存储结构有别而不同。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 限定只能在表的一端进行插入和删除操作的线性表。 特点：后进先出。 基本操作有：建栈、判断栈满或栈空、入栈、出栈、 读栈顶元素值等等
栈“上溢”在栈满时还进行入栈运算,必定会产生空 间的溢出 7、栈“下溢”当栈空时仍进行出栈运算,必定会产生 空间的溢出
3 在栈满时还进行入栈运算，必定会产生空 间的溢出 7、栈“下溢” 6、栈“上溢” 当栈空时仍进行出栈运算，必定会产生 空间的溢出
栈是仅在表尾进行插入、删除操作的线性表 表尾(即an端)称为栈顶/top;表头(即an端)称为栈底/base 例如:栈S=(a0,a2,a3,……an-1,an a1称为栈底元素 an称为栈顶元素 插入元素到栈顶的 强调:插入和删除都只能在表 操作,称为入栈。 的一端(栈顶)进行! 从栈顶删除最后 个元素的操作,称 为出栈 注:堆栈可以完成比较复杂的数据元素特定序列 的转换任务,但它不能完成任何输入输出序列的 转换任务
4 栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶/top ; 表头(即 a1 端)称为栈底/base 例如： 栈 S= (a０ , a2 , a3 , ……….,an-1 , an ) 插入元素到栈顶的 操作，称为入栈。 从栈顶删除最后一 个元素的操作，称 为出栈。 a1称为栈底元素 an称为栈顶元素 强调：插入和删除都只能在表 的一端（栈顶）进行！ 注：堆栈可以完成比较复杂的数据元素特定序列 的转换任务，但它不能完成任何输入输出序列的 转换任务
例1:堆栈是什么?它与一般线性表有什么不同? 堆栈是一种特殊的线性表,它只能在表的一端(即 栈顶)进行插入和删除运算 与一般线性表的区别:仅在于运算规则不同。 般线性表 堆栈 逻辑结构:1:1 逻辑结构:1:1 存储结构:顺序表、链表存储结构:顺序栈、链栈 运算规则:随机存取 运算规则:后进先明LFO “进”=插入=压入 删除=弹
5 例1：堆栈是什么？它与一般线性表有什么不同？ 堆栈是一种特殊的线性表，它只能在表的一端（即 栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 堆栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO) “进”＝插入=压入 “出”＝删除=弹 出