队列是一种非常常见的数据结构,日常生活中也能经常看到。一个典型的队列如下图(图片来自 segmentfault):
可以看出队列和我们日常生活中排队是基本一致的。都遵循 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{} }