【数据结构与算法】队列

原文作者 寒江独钓

点击原文链接，可进入原文。

基本概念

队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构，如下图：

和Stack一样，他也有链表和数组两种实现，理解了Stack的实现后，Queue的实现就比较简单了。关于栈,有兴趣的同学请查看【数据结构与算法】栈。

对于Queue 我们希望至少要对外提供以下几个方法：

队列的链表实现

Dequeue方法就是返回链表中的第一个元素，这个和Stack中的Pop方法相似：

Enqueue和Stack的Push方法不同，他是在链表的末尾增加新的元素：

队列的数组实现

同样地，现在再来看如何使用数组来实现Queue，首先我们使用数组来保存数据，

并定义变量head和tail来记录Queue的首尾元素。

和Stack的实现方式不同，在Queue中，我们定义了head和tail来记录头元素和尾元素。当enqueue的时候，tial加1，将元素放在尾部，当dequeue的时候，head减1，并返回。

队列的应用

在现实生活中Queue的应用也很广泛，最广泛的就是排队了，”先来后到” First come first service ，以及Queue这个单词就有排队的意思。

还有，比如我们的播放器上的播放列表，我们的数据流对象，异步的数据传输结构(文件IO，管道通讯，套接字等)

还有一些解决对共享资源的冲突访问，比如打印机的打印队列等。消息队列等。交通状况模拟，呼叫中心用户等待的时间的模拟等等。