2.3 栈及队列

2 3栈和队列 一 栈 四 队列 二 栈的应用举例 三 带链的栈 栈和队列是在程序设计中被广泛使用的两种线性数据结构 它们的特点在于基本操作的特殊性 栈必须按 后进先出 的规则进行操作 而队列必须按 先进先出 的规则进行操作 和线性表相比 它们的插入和删除操作受更多的约束和限定 故又称为限定性的线性表结构 可将线性表和栈及队列的插入和删除操作对比如下 2 3栈和队列 2 3栈和队列 插入删除线性表 Insert L i x Delete L i 1 i n 1 1 i n 栈 Insert L n 1 x Delete L n 队列 Insert L n 1 x Delete L 1 线性表允许在表内任一位置进行插入和删除 而栈只允许在表尾一端进行插入和删除 队列只允许在表尾一端进行插入 在表头一端进行删除 一 栈 1 栈的定义 栈 Stack 是限定只能在表的一端进行插入和删除操作的线性表 在表中 允许插入和删除的一端称作 栈顶 top 不允许插入和删除的另一端称作 栈底 bottom an a2 a1 栈底bottom 栈顶top 入栈 出栈 一 栈 constintmaxsize 10 栈的最大存储空间structStack ETdata maxsize inttop 栈顶的位置 俗称顺序栈 顺序栈的C语言描述如下 如果定义Stacks 则s top 0表示栈空 s top maxsize表示栈满 栈顶元素为 s data s top 1 2 栈的顺序存储及其实现 1 栈的初始化 voidInitStack Stack 空栈长度为0 顺序栈的运算 栈的基本操作有三种 入栈 退栈与读栈顶元素 2 栈的顺序存储及其实现 2 入栈运算 在栈顶位置插入一个新的元素 元素入栈的规则为 在栈不满时 先将栈顶指针进一 再将新元素插入到栈顶位置 voidpush Stack 2 栈的顺序存储及其实现 3 出栈运算 取出栈顶元素并赋给一个指定的变量 出栈时 在栈非空时 先将栈顶元素赋给指定的变量 再将栈顶指针退一 voidpop Stack 2 栈的顺序存储及其实现 2 栈的顺序存储及其实现 4 读栈顶元素 将栈顶元素赋给一个指定的变量 ETtop Stack 二 栈的应用举例 1表达式的计算 计算机系统在具体处理表达式前 首先设置以下两个栈 一个是运算符栈 用于在表达式处理过程中存放运算符 在开始时 运算符栈中先压人一个表达式结束符 二是操作数栈 用于在表达式处理过程中存放操作数 然后从左到右依次读出表达式中的各个符号 运算符或操作数 每读出一个符号按以下原则进行处理 1 若读出的是操作数 则将该操作数压人操作数栈 并依次读下一个符号 2 若读出的是运算符 则作进一步判断 二 栈的应用举例 若读出运算符的优先级大于运算符栈栈顶运算符的优先级 则将读出的运算符压入运算符栈 并依次读下一个符号 若读出的是表达式结束符 且运算符栈栈顶的运算符也是表达式结束符 则表达式处理结束 最后的计算结果在操作数栈的栈顶位置 将计算结果出栈 表达式结束符 也出栈 二 栈的应用举例 若读出的运算符的优先级不大于运算符栈栈顶运算符的优先级 则从操作数栈连续推出两个操作数 并从运算符栈推出一个运算符 然后作相应的运算 并将运算结果压入操作数栈 在这种情况下 当前读出的运算符下次重新考虑 即不再读下一个符号 分析 表达式2 3 4 9 3 的计算过程 二 栈的应用举例 2递归的实现 从递归的基本思想可以看出 计算机执行递归过程时 需要记忆各步的状态 以便问题的返回 这可以用栈来实现 max a 1 4 max a 1 2 2 3 x 3 a 4 2 3 7 5 max a m n if m n x max a m m n 2 y max a m n 2 1 n returnx y x y else returna m max a 3 4 7 5 y 7 7 三 带链的栈 栈的链式存储结构 带链的栈 an An 1 a1 链栈的逻辑状态 S structnode ETdata structnode next 带链的栈的结点表示与单链表相同 1 链栈的初始化 三 带链的栈 voidInitList node 判断链栈是否为空 top NULL an a1 top p newnode 建新的结点 p data e p next top top p 2 入链栈操作 三 带链的栈 e 在栈顶为top的链栈中插入元素e 三 带链的栈 voidpush node 改变栈顶指针 an a1 top 3 退链栈操作 三 带链的栈 e top data p top top p next deletep 在栈顶为top的带链栈中删除栈顶元素 三 带链的栈 voidpop node 释放被删除结点空间 四 队列 队列 Queue 是限定只能在表的一端进行插入和在另一端进行删除操作的线性表 在表中 允许插入的一端称作 队列尾 tail 允许删除的另一端称作 队列头 front 1 队列的定义 这和日常生活中的排队是一致的 最早进入队列的元素最早离开 在队列中 允许插入的一端称为队尾 rear 允许删除的一端则称为队头 front front rear 退队 入队 front rear 退队 front rear 入队 队列示意图 constintmaxsize 10 栈的最大存储空间structqueue ETdata maxsize intfront 指向队列头元素的前一个位置intrear 指向队列尾元素 队列的表示 QueueQ 四 队列 2循环队列 所谓循环队列 就是将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 按上述的做法 有可能出现假溢出 即队尾已经达到一维数组的高端 不能再入队 但因为连续出队 队列中元素的个数并未达到最大值 解决这种问题 可用循环队列 四 队列 Q 1 6 Rearfront 6 1 2 循环队列的初始状态 Q 1 6 front 6 1 2 Rear 入队 先将队尾指针进一 rear rear 1 当rear m 1时 rear 1 再插入新元素 循环队列入A后 Q 1 6 front 6 1 2 Rear Q 1 6 front 6 1 2 Rear 循环队列的队满状态 退队 先将队头指针进一 front front 1 当front m 1时 front 1 再将队头元素赋给指定的变量 循环队列退A后 由上图可以看出在循环队列中 队满和队空时都有frong rear 所以需要区分队空和队满的情况 用front rear表示队空 在牺牲一个单元的前提下 用front rear 1 max表示队满 Q 1 6 front 6 1 2 Rear 队列中元素的个数为 Q rear maxsize Q front maxsize 四 队列 front rear front Y rear X 循环队列运算示例 队满 四 队列 循环队列的基本运算 voidInit queue 初始化时 设置Q front Q rear 0 队空的条件为Q front Q rear 队满的条件为Q front Q rear 1 Queuesize 1 循环队列初始化 四 队列 voidaddcq queue 2 入队操作 在队列未满时 队尾指针先加1 要取模 再送值到队尾指针指向的空闲元素 四 队列 voiddelcq queue 3 出队操作 在队列非空时 对头指针先加1 要取模 再从队头指针指向的队头元素处取值 四 队列 3链队 队列也可以采用链式存储结构 链队实际上是一个同时带有头指针和尾指针的单链表 头指针指向对头结点 尾指针指向队尾结点即单链表的最后一个结点 a1 a2 an 链队的逻辑状态 front rear 四 队列 structnode ETdata structnode next StructLQueue node front node rear LQueue LQ 链队的类型定义 四 队列 链队的说明