队列是什么

小白 2020-04-25 10:17:54
QA

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列是什么

简介

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

队列的数组实现

队列可以用数组 Q[1…m]来存储,数组的上界 m 即是队列所容许的最大容量。在队列的运算中需设两个指针:head,队头指针,指向实际队头元素;tail,队尾指针,指向实际队尾元素的下一个位置。一般情况下,两个指针的初值设为 0,这时队列为空,没有元素。数组定义 Q[1…10]。Q(i) i=3,4,5,6,7,8。头指针 head=2,尾指针 tail=8。队列中拥有的元素个数为:L=tail-head。现要让排头的元素出队,则需将头指针加 1。即 head=head+1 这时头指针向上移动一个位置,指向 Q(3),表示 Q(3)已出队。如果想让一个新元素入队,则需尾指针向上移动一个位置。即 tail=tail+1 这时 Q(9)入队。当队尾已经处理在最上面时,即 tail=10,如果还要执行入队操作,则要发生"上溢",但实际上队列中还有三个空位置,所以这种溢出称为"假溢出"。

克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动,显然这种方法是很浪费时间的;另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到 n 地址后,下一个地址就"翻转"为 1。在结构上采用这种技巧来存储的队列称为循环队列。

队列和栈一样只允许在断点处插入和删除元素。

循环队的入队算法如下:

1、tail=tail+1;

2、若 tail=n+1,则 tail=1;

3、若 head=tail,即尾指针与头指针重合了,表示元素已装满队列,则作上溢出错处理;

4、否则,Q(tail)=X,结束(X 为新入出元素)。

队列和栈一样,有着非常广泛的应用。

注意:(1)有时候队列中还会设置表头结点,就是在队头的前面还有一个结点,这个结点的数据域为空,但是指针域指向队头元素。

(2)另外,上面的计算还可以利用下面给出的公式 cq.rear=(cq.front+1)/max;

当有表头结点时,公式变为 cq.rear=(cq.front+1)/(max+1)。

队列的链表实现

在队列的形成过程中,可以利用线性链表的原理,来生成一个队列。

基于链表的队列,要动态创建和删除节点,效率较低,但是可以动态增长。

队列采用的 FIFO(first in first out),新元素(等待进入队列的元素)总是被插入到链表的尾部,而读取的时候总是从链表的头部开始读取。每次读取一个元素,释放一个元素。所谓的动态创建,动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成,遍历也方便。

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 打印任务 print job

    想查看打印任务打印机任务列表在哪里

    查看打印任务列表可以在任务栏的系统托盘中,找到打印机图标并双击,打开的窗口会显示当前的打印队列,包括正在打印的任务和等待打印的任务;还可以打开控制面板选择硬件和声音下的设备和打印机,找到并双击你正在使用的打印机图标,也会打开打印队列窗口。
  • 打印机 Printer

    打印机状态卡在“正在删除”有什么解决办法

    打印机状态卡在正在删除可以重启打印队列服务,打开运行对话框输入services.msc后回车,在服务列表中找到Print Spooler服务,重启服务,不起作用可停止服务,然后手动清除打印队列;还可检查打印机驱动程序,重启电脑和打印机解决。
  • 打印机错误 print error

    打印机显示错误状态应该如何解除

    打印机显示错误状态先检查所有连接线,以及无线连接稳定;重启打印机和电脑;在设备和打印机中清理打印队列,再重新打开文档重新发送打印作业;检查是否有纸张卡住、墨盒或硒鼓是否需要更换;更新或重新安装打印机驱动;确保没有正在运行的软件干扰打印进程。
  • 打印任务卡住 Print task stuck

    打印任务卡住不动怎样取消并重新安排打印任务

    打印任务卡住不动首先检查是否有卡纸、墨水不足、机盖未关的问题,网络打印机要确保网络连接正常;然后取消打印做任务,在打印列表,右击正在打印的文档选择取消;取消打印任务无效可以尝试关闭打印机;检查并重新安装驱动程序;最后重新安排打印任务。
  • Redis

    Redis,开源的高性能键值对数据库

    Redis是一款开源、基于内存的高性能键值对数据库,支持多种数据结构如字符串、列表、集合等。它以快速的读写速度和高并发处理能力著称,适用于缓存系统、会话存储、消息队列等多种场景。Redis的主要优势包括数据持久化、丰富的数据类型支持和良好的扩展性。特别适合需要快速、复杂数据处理的企业和应用。
  • FileZilla

    FileZilla,免费开源的FTP客户端

    FileZilla是一款高效且用户友好的FTP客户端,支持FTP、SFTP和FTPS协议,适用于各类用户,特别是网站管理员和开发人员。它以直观的界面、强大的文件管理能力、高效的传输速度和稳定性著称。FileZilla还提供断点续传和远程文件编辑功能,增强了其实用性。在安全性方面,它通过多种加密选项确保文件传输的安全。