经过近两年的时间,我终于写完了这一章。
正如我在Algoxy第一章描述的,Queue并非想象的那样简单。尤其是提供一个纯函数式的队列,并且满足常数时间的头部和尾部操作并不容易。
本章中,我们给出几种不同的队列的纯函数式实现。
当然,用常见的imperative语言实现队列很容易,尤其是使用双向链表。但是这是一个overkill的解法,我们先用单向链表实现一个头部尾部都是常数时间的队列;然后我们给出一个ring-buffer的实现;
接着我们给出一个简单的纯函数式解法:它能达到amortized常数时间,但是worst case表现一般,接着我们给出一个基于状态机的real time queue, 最后我们给出一个基于惰性求职的real time queue
全文pdf可以在github下载:
https://github.com/downloads/liuxinyu95/AlgoXY/queue-en.pdf
源代码下载地址:
https://github.com/liuxinyu95/AlgoXY/tree/algoxy/datastruct/elementary/queue/src
分享到:
相关推荐
C语言_初始化队列+入队列+出队列+销毁队列
链队列题目:初始化队列+入队列+出队列+销毁队列
用消息队列实现的简单聊天程序,经行client与sever之间的交互。
进程与消息队列进程与消息队列简单例进程与消息队列进程与消息队列简单例进程与消息队列进程与消息队列简单例进程与消息队列进程与消息队列简单例进程与消息队列进程与消息队列简单例
此文档是C#开发的消息队列系统,适用于消息队列入门与新手。 在Windows 7 上安装消息队列的步骤 打开“控制面板”。 单击“程序”,然后在“程序和功能”下, 单击“打开或关闭 Windows 功能”。 -或者-单击“经典...
java队列实现(顺序队列、链式队列、循环队列)
队列建立和队列的逆置 队列建立和队列的逆置 队列建立和队列的逆置
普通队列 1)将尾指针往后移:rear+1,当front==rear【空】 2)若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数中组元素中,否则无法存入数据。rear==maxSize-1[队列满] 环形队列 1)front变量的...
这是我用c语言写的程序,我的其他资源都是免费的,是对于c语言初学者的帮助比较大的,其中有数据结构,window编程。我也在学c语言,每当我写完一个程序,我都会免费发上来。...这个是队列的最简单的应用
用C语言写的一个简单的循环队列,数据结构实验。
易语言简单的多线程消息队列。@Patek。
● 可以实时查看队列状态(入队列位置、出队列位置、未读队列数量、最大队列数量)。 ● 可以查看指定队列ID(队列点)的内容,包括未出、已出的队列内容。 ● 查看队列内容时,支持多字符集编码。 ● 源...
队列源码,文章《也没想象中那么神秘的数据结构-先来后到的“队列”》系列示例代码
消息队列的简单讲解
易语言简单队列处理源码,简单队列处理,初始化启动,AddrPacketQrList,DelsPacketQrList,ProcessorPacketQ,提交处理事件,设置定时器,销毁定时器,取变量地址_字节集,ASM_写整数,ASM_写短整数,ASM_读短整数,ASM_写字节,...
使用顺序存储实现优先级队列,展示优先级队列和普通队列的区别之处。
要求象队列那样支持在数据末端的回绕。 如果严格禁止调用insertLeft()和removeLeft()方法(或禁用右端的操作),双端队列功能就和栈一样。 禁止调用insertLeft()和removeRight()方法(或相反的另一对方法),它的...
队列的简单介绍,包括循环队列以及迷宫问题等
易语言源码易语言简单队列处理源码.rar 易语言源码易语言简单队列处理源码.rar 易语言源码易语言简单队列处理源码.rar 易语言源码易语言简单队列处理源码.rar 易语言源码易语言简单队列处理源码.rar 易语言源码...
用C#实现任务队列,一个队列存放任务,线程互斥的从任务队列中取,放任务,任务队列为空,线程等待,直到有任务加入队列为止。