ADT简介与代码示例——队列(Queue)
队列是一种先进先出的数据结构,如同现实中的排队。(但没有“插队”操作。)
队列的应用:打印机、cpu、挂号系统等,常常把任务记录在队列中——先进入队列的任务先处理。
符合先进先出的情形通常都使用队列。
对于队列,每一种操作都有O(1)的运行时间(不论是数组实现还是链表实现)。
队列的链表实现非常简单——你只要把中文逐句翻译成代码即可。
这里给出的是数组实现。
数组实现存在需要考虑的问题。
尾指针到达末尾时,再进行入队会越界。
此时队列可能已满,需要阻止入队,但也有可能头指针已经移动过了,数组的前端有部分空间,这就不应该阻止入队。
显而易见的解决方法:将数组的头尾相连,指针到达末尾时就绕回开头。这种方法叫做 循环数组实现(Circular Array)。
关于循环实现:
警惕在队列为空时请求的出队操作。
警惕 队列大小=尾指针-头指针 在某些情况下会出现的错误。
关于代码:
代码为C实现,因为使用vs的缘故是.cpp后缀,改为.c不会产生影响。
typedef.h中定义了元素数据类型,这是为了通过修改头文件就可以使用支持赋值号'='的任意数据类型。
代码的编写者也是一位初学者,难免犯错,敬请谅解。
压缩包内的所有文件(包括本readme文件)都没有传播或修改的限制,转载不需要注明出处,但必须以同样方式共享。
如果你愿意指出代码中可以改进的地方,或者你需要相关的解释,可以发送邮件至rfrith96@gmail.com。