数据结构&队列

参考文章

• 看完这篇你还不知道这些队列，我这些图白作了
• Java中的queue和deque对比详解

  总结

• 队列遵循FIFO原则，但是不一定以FIFO的方式排序各个元素。

  非循环队列

• 数据迁移只需要在tail=MaxSize&&head!=0时进行，以节省使用代价。
  
• 判断队列满了的条件，tail = MaxSize,head = 0。
• 链式队列与顺序队列比起来不需要进行数据的迁移，实现相对简单很多，但是链式队列增加了存储成本。

  循环队列

• 对于一个存储空间为n的循环队列，只能存放n-1位数据，令tail与head重合时为队空条件，(tail+1)%MaxSize==head时为队满条件。
• 出入队列都应该取模。比如入队tail=(tail+1)%MaxSize，出队head=(head+1)%MaxSize。
• 队列长度length=(tail-head+MaxSize)%MaxSize。一般队列长度仅需要tail-head，而循环队列中，head可能会比tail大，所以需要加上MaxSize并取模。
• 由长度公式以及队满条件知，显然，循环队列队满时length为MaxSize-1。

  双端队列（Deque）

• 队头、队尾都可以进行入队、出队操作。总之它即有栈的功能，也有队列的功能。
• 在将双端队列用作队列时，将得到FIFO行为；在将双端队列用作堆栈时，将得到LIFO行为；

  优先队列（不遵循FIFO）

• 从队头出队，队尾入队。不过每次入队时，都会按照入队数据项的关键值进行排序。保证优先级最高的最先出队。
• 一般用堆实现。