经典手机网站,做网站和优化共多少钱?,免费的建站平台,北京vi设计培训文章目录 提要队列的定义队列的认识队列的应用队列的抽象数据类型队列的存储结构队列的链式存储结构与实现链队的进队和出队操作链队的数据类型初始化链队列入队操作出队操作队列的顺序存储结构与实现顺序队列的假溢出问题队列上溢循环队列循环队列取下一相邻单元下标运算队满与… 文章目录 提要队列的定义队列的认识队列的应用队列的抽象数据类型队列的存储结构队列的链式存储结构与实现链队的进队和出队操作链队的数据类型初始化链队列入队操作出队操作队列的顺序存储结构与实现顺序队列的假溢出问题队列上溢循环队列循环队列取下一相邻单元下标运算队满与队空的问题解决方法循环队列入队操作循环队列出队操作总结 提要
队列的定义队列的抽象数据类型队列的链式存储结构与基本运算的实现队列的顺序存储结构与基本运算的实现
队列的定义
队列是一种受限的线性表只能在一端插入在另一端删除队尾rear允许插入的一端队头front允许删除的一端入队enqueue在队尾进行的插入操作出队dequeue在队头进行的删除操作队列特点先进先出FIFO栈的应用非常广泛在CPU内部就有提供栈这个机制。主要用途函数调用和返回数字转字符表达式求值走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回中断时数据保存和返回。在编程语言中主要用来进行函数的调用和返回。在计算机中可以说只要数据的保存满足先进后出的原理都优先考虑使用栈所以栈是计算机中不可缺的机制。
队列的认识
队列是生活中排队的抽象插队是不允许的队列的主要特点是先进先出所以又把队列称为先进先出表。
队列的应用
记录访问或操作的顺序对独占资源的调度安排如打印机电子商务网站的秒杀功能大型信息系统中的消息队列
队列的抽象数据类型
数据元素集合具有相同性质数据元素的有限序列,且只能在称为队尾的一端进行插入操作和在队头的一端进行删除操作。基本操作 初始化队列 (InitQueue)求队列长度 (QueueLength)入队 (EnQueue)出队 (DeQueue)判队空 (QueueEmpty)
队列的存储结构
顺序队列链队列
队列的链式存储结构与实现
链队采用不带头结点的单链表实现队头指针和队尾指针 链队组成: 1存储队列元素的单链表结点 2 指向队头和队尾指针的链队头结点
链队的进队和出队操作
a空队 ba、b、c进队 c出队一次链队的4要素队空条件frontrearNULL队满条件不考虑进队e操作将包含e的结点插入到单链表表尾出队操作删除单链表首数据结点
链队的数据类型
front指针指向头结点rear指针指向最后一个元素结点 初始化链队列
构造一个只有空头结点的链式队列头尾指针均指向头结点
入队操作
生成新结点并插入到链表尾部
出队操作 判断队列是否为空 删除队头元素结点 若被删结点是队尾结点则更新队尾指针指向头结点。
队列的顺序存储结构与实现 使用数组实现队列 头尾指针分别表示队头和队尾
顺序队列的假溢出问题
解释了假溢出现象和解决方法 当rear超出数组最大下标后队列的空间就用尽了。 即使数组下标较小的位置还有空闲空间也不能进行入队操作
队列上溢
真上溢 (rear-frontMaxSize)队列真正满无空位。 假上溢rear已指向队尾但队列前端仍有空位置。 解决假上溢的方法 方法一每次删除队头一个元素后把整个队列往前移一个位置造成时间浪费 方法二构造循环队列
循环队列
首尾相接的队列实现把数组的首尾两个存储单元看成位置相邻的单元即允许队列直接从数组中下标最大的位置前进到下标最小的位置。(设数组长度为Max)
循环队列取下一相邻单元下标运算 数组第一个单元的下标为 0 与下标1的单元相邻 (01) Max1 数组最后一个单元的下标为Max1 其下一相邻的单元的下标为0 (Max-11) Max0 任一位置 X (0≤X≤Max-1) X的下一相邻的单元的下标为 (X1)Max 数据入队前
队满与队空的问题
解释了如何判断队列满和队空
解决方法
少用一个存储单元来区分队满和队空队空frontrear队满(rear 1) % MaxSize front队列长度(rear–frontMaxSize) % MaxSize
循环队列入队操作 循环队列出队操作 总结
循环队列和链队列的比较 时间性能基本操作都需要常数时间 O(1)空间性能循环队列有存储元素个数的限制和空间浪费问题链队列没有队列满的问题但有结构性开销
