什么是队列

对于n个数据元素构成的一个线性序列，如果在其一端只允许插入数据元素，且在另一端只允许删除数据元素，这种逻辑结构称为队列（Queue）。

只允许插入的一端称为队尾（Rear），只允许删除的一端称为队首（Front）。

队列是一种"先进先出"的数据结构，在操作系统的进程调度管理网络数据包的存储发等多个领域中被广泛引用。

---

运算

队列的基本运算包括入队，出队和判断。

• 入队：在队列中插入一个新的数据元素。插入在队尾进行，新插入的元素会产生新的队尾。入队需要保证空间足够，否则溢出。
  

  入队操作

• 出队：在队列中删除一个数据元素。删除在队首进行，-并把出队的数据传递给用户程序，原队首后继的元素成为新的队首*。出队时必须保证队列不为空，否则队列也会发生溢出。
  

  出队操作

• 判断：用来检查队列是否为空，即检验头指针和尾指针是否重合。返还结果是一个逻辑值。

---

循环队列的实现

队列可以用数组或者链表来实现。因为队列的大小有限制，不断的插入新的数据可能导致队尾的位置从计算机内存中合法的存储空间中溢出，因此通常采用循环队列，也称环状缓冲区（ring buffer）的方式。

循环队列

实际饮应用中，随着数据的入队，队尾向末端延伸的同时，队首不断在出队，导致空间起始端的空白储存单元逐渐增多。因此，当队尾到达末端时，就可以把新入队的数据插入到原来的起始端也就是空白的储存单元，从而队尾指向储存空间的起始端，并随着队列的增长继续向末端延伸。

环状缓冲区