用go实现常用算法与数据结构——队列(queue)

队列是一种非常常见的数据结构,日常生活中也能经常看到。一个典型的队列如下图(图片来自 segmentfault):

queue


可以看出队列和我们日常生活中排队是基本一致的。都遵循 FIFO(First In First Out)的原则。

实现

队列可以使用链表或者数组实现,使用链表的优点是扩容简单,缺点是无法通过索引定位元素,使用数组则相反,扩容不容易但是可以通过索引定位元素。文章采用双向链表实现。代码放在github:

https://github.com/AceDarkknight/AlgorithmAndDataStructure/tree/master/queue

链表一般有下面这几个基本操作,先定义一个接口,方便开发和测试:

type Queue interface { // 获取当前链表长度。 Length() int // 获取当前链表容量。 Capacity() int // 获取当前链表头结点。 Front() *Node // 获取当前链表尾结点。 Rear() *Node // 入列。 Enqueue(value interface{}) bool // 出列。 Dequeue() interface{} }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpzfwd.html