第4章钱和队列
第4章 栈和队列
引例 1.每中一最的子:如果克位是控12的次 必然是依从上往下的次序,即n,2,1。它们遵循的是“后进 先出"的规律,这正是本章要讨论的"栈"的结构特点 2.在日常生活中,为了雏持正常的社会秩序而出现的常 见观象是什么? 是"排队"。在计算机程序中,模拟排队的数据结构是"队列" 栈和队列是两种特殊的线性表,是操作受限的线性表 称限定性数据结构
引例 1. 餐馆中一叠一叠的盘子：如果它们是按 1,2,…,n 的次 序往上叠的，那么使用时候的次序应是什么样的？ 必然是依从上往下的次序，即n,…,2,1。它们遵循的是"后进 先出"的规律，这正是本章要讨论的"栈"的结构特点。 是"排队"。在计算机程序中，模拟排队的数据结构是"队列" 。 栈和队列是两种特殊的线性表,是操作受限的线性表, 称限定性数据结构。 2. 在日常生活中，为了维持正常的社会秩序而出现的常 见现象是什么？
心和队列 4.栈 4.2钱的愈用举例 43队列 4.4队列应用举例
4.1 栈 4.2 栈的应用举例 4.3 队列 4.4 队列应用举例
【学习冒馨 1.掌握栈和队列这两种抽象数据类型的特 点,并能在相应的应用问题中正确选用 它们 2.熟练掌握栈类型的两种实现方法。 3.熟练掌握循环队列和链队列的基本操作 实现算法。 4理解递归算法执行过程中栈的状态变化 过程
【学习目标】 1.掌握栈和队列这两种抽象数据类型的特 点，并能在相应的应用问题中正确选用 它们。 2.熟练掌握栈类型的两种实现方法。 3.熟练掌握循环队列和链队列的基本操作 实现算法。 4.理解递归算法执行过程中栈的状态变化 过程
重点和难点】 栈和队列是在程序设计中被广泛使用的两种线 性数据结构,本章的学习重点在于掌握这两种 结构的特点,以便能在应用问题中正确使用。 【知识点】 顺序栈、链栈、递归、循环队列、链队列 点:栈和队列的基本特征,表示与实现 难点:递归、循环队列 算法:栈和队列的实现及其应用
【重点和难点】 栈和队列是在程序设计中被广泛使用的两种线 性数据结构，本章的学习重点在于掌握这两种 结构的特点，以便能在应用问题中正确使用。 重点：栈和队列的基本特征，表示与实现 难点：递归、循环队列 算法：栈和队列的实现及其应用 顺序栈、链栈、递归、循环队列、链队列 【知识点】
【学习指南】 本章主要是学习如何在求解应用问题中适当 地应用栈和队列栈和队列在两种存储结构中的 实现都不难,但应该对它们了如指掌,特别要 注意它们的基本操作实观时的些特殊情况, 如浅满和栈空、队满和队空的条件以及它们的 述方法。 本章要求必须完成的算法设计题为 41,4.243,44.54.6,4.9411412
【学习指南】 本章主要是学习如何在求解应用问题中适当 地应用栈和队列,栈和队列在两种存储结构中的 实现都不难，但应该对它们了如指掌，特别要 注意它们的基本操作实现时的一些特殊情况， 如栈满和栈空、队满和队空的条件以及它们的 描述方法。 本章要求必须完成的算法设计题为： 4.1, 4.2, 4.3, 4.4, 4.5, 4.6, 4.9, 4.11, 4.12
4。擒 定义:栈一特殊的线性表:操作受限的线性表 般线性表 堆栈 逻辑结构:一对 逻辑结构:一对 存储结构:顺序表、链表存储结构:顺序栈、链栈 运算规则:随机存取 运算规则:后进先出①LIFO) 绕性表 队列 Insert(L,i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n1 Delete(L, 0) Delete(s, n) Delete(Q, 1) 1≤≤n
4.1 栈 是限定仅在表尾进行插入或删除操作的线性表。 允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom) top bottom 出栈 进栈 an . . . . a1 基本操作： 后进先出(LIFO) 定义：栈 ─ 特殊的线性表：操作受限的线性表 逻辑特征： •创建一个空栈； •判断栈是否为空栈； •判断栈是否为满； •往栈中插入(或称推入)一个元素； •从栈中删除(或称弹出)一个元素； •求栈顶元素的值。 •访问栈中每个元素 栈和队列是限定插入和删除只能在表 栈和队列是两种常用的数据类型 的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO)
4。。擒的特赢绿作 1、定义限定只能在表的一端进行插入和删除运 算的线性表(只能在栈顶操作) 2.逻辑结构与线性表相同仍为一对一关系。 3.存储结构用顺序栈或链栈存储均可顺序栈更常见 4.运算规则只能在栈顶运算且访问结点时依照后进 先出(LIFo)或先进后出(FILo的原则。 5.实现方式关键是编写入栈和出栈函数,具体实现依顺序栈 或链栈的不同而不同。 基本操作有入栈、出栈、读栈顶元素值、建栈、 判栈满、判栈空等
1. 定义 与线性表相同,仍为一对一关系。 用顺序栈或链栈存储均可,顺序栈更常见 只能在栈顶运算,且访问结点时依照后进 先出(LIFO)或先进后出(FILO)的原则。 关键是编写入栈和出栈函数，具体实现依顺序栈 或链栈的不同而不同。 基本操作有入栈、出栈、读栈顶元素值、建栈、 判栈满、判栈空等。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 限定只能在表的一端进行插入和删除运 算的线性表(只能在栈顶操作) 4.1.1 栈的特点和操作
4。。擒的特赢绿作 栈是仅在裹尾进行插入、删除操作的线性表。 表尾(即an端)称为栈顶top;表头(即a端)称为栈底base 例如:栈s=(a1,a2,a,…,al,an) a1称为栈底元素a称为栈顶元素 插入元素到栈顶(即表尾)的操作,称为入栈。 从栈顶(即表尾删除最后一个元素的操作,称为出栈。 强调:插入和删除都只能在表的一端(栈顶)进行! “进”=压入=PUSH(x) “出”=弹出=POP(y)
例如： 栈 s = ( a1 , a2, a3, ……, an-1, an ) an 称为栈顶元素 插入元素到栈顶(即表尾)的操作，称为入栈。 从栈顶(即表尾)删除最后一个元素的操作，称为出栈。 强调：插入和删除都只能在表的一端（栈顶）进行！ a1 称为栈底元素 栈是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶top ; 表头(即 a1 端)称为栈底base “进” ＝压入=PUSH（x) “出” ＝弹出=POP ( y ) 4.1.1 栈的特点和操作
栈的基本操作 InitStack&S 操作结果:构造一个空栈S DestroyStack(&S) 初始条件:S已存在。操作结果:栈S被销毁 Clearstack(&s 初始条件:S已存在。操作结果:将S清为空栈 StackEmpty(s) 初始条件:S已存在。操作结果:若栈S为空栈,则返回TRUE,否则FALE。 StackLength(S) 初始条件:S已存在。操作果:返回S的元素个数,即栈的长度。 GetTop(s, &e 初始条件:S已存在且非空。操作结果:用e返回S的栈顶元素 Push(&s, e) 初始条件:S已存在。操作结果:插入元素e为新的栈顶元素。 Pop(as, &e) 初始条件:S已存在且非空。操作果:删除S的栈顶元素并用e返回其值。 StackTraverset 初始条件:S已存在且非空。操作结果:从底到顶依次输出S中的元素
栈的基本操作 InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：S已存在。操作结果：栈S被销毁。 ClearStack(&S) 初始条件：S已存在。操作结果：将S清为空栈。 StackEmpty(S) 初始条件：S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。 StackLength(S) 初始条件：S已存在。操作结果：返回S的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：S已存在且非空。操作结果：用e返回S的栈顶元素。 Push(&S, e) 初始条件：S已存在。操作结果：插入元素e为新的栈顶元素。 Pop(&S, &e) 初始条件：S已存在且非空。操作结果：删除S的栈顶元素,并用e返回其值。 StackTraverse(S) 初始条件：S已存在且非空。操作结果：从底到顶依次输出S中的元素