数据结构--队列

和栈相似，队列（queue）也是表，所不同的是队列的插入在表的一端进行而删除则在另一端进行。与栈的后进先出（LIFO）不同，队列中的元素特性是先进先出（FIFO）。

图 1

队列的基本操作：

入队，在表的末端，也叫队尾（rear），插入一个元素
出队，删除或返回表的开头，也叫队头（front）的元素

队列的实现

如同栈一样，对于队列而言，任何表的实现都是合法的。对于入队和出队操作，链表和数组的实现都能给出 O(1) 的运行时间。

队列的数组slice实现

对于队列数据结构，我们保留一个数组 []interface、队头位置 front、队尾位置 rear 以及队列中元素的个数 size. 如果有元素 X 入队，可以让 size 和 rear 加 1，然后设置 Queue[rear]=X。如果有元素出队，需要返回 Queue[front]，然后size减1，front加1。

图 2

通过数组实现队列有一个潜在的问题，经过几次入队和出队操作之后，front 和 rear 会到数组的边界。简单的解决方式是，如果 front 或 rear 到达数组的尾端，就绕到开头。这种方式叫循环数组实现。

通过 slice 实现队列也需要限制 slice 的容量，在 front 和 rear 到达边界时，可以采用和数组同样的逻辑，以免 slice 不断扩容。

队列的链表实现

和数组的实现方式类似，我们需要定义一个链表，指向队列头元素的指针 front，指向队列尾元素的指针 rear，以及队列元素个数 size。如果有元素 X 入队，可以将 X 添加到链表的尾部，然后将rear 指向 X。如果元素出对，返回并删除 front 指向的元素，然后将 front 指向 front 的前驱元素。

参考资料

数据结构与算法分析