【学习指南】 本章主要是学习如何在求解应用问题中适当 地应用栈和队列栈和队列在两种存储结构中的 实现都不难,但应该对它们了如指掌,特别要 注意它们的基本操作实观时的些特殊情况, 如浅满和栈空、队满和队空的条件以及它们的 述方法。 本章要求必须完成的算法设计题为 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中的元素