队列

ADT：

• 概念：A queue is a First-In-First-Out (FIFO) list, that is, an ordered list in which insertions take place at one end and deletions take place at the opposite end.
• 对象：A finite ordered list with zero or more elements.
• 操作：
  1. IsEmpty
  2. CreateQueue
  3. DisposeQueue
  4. MakeEmpty
  5. Enqueue
  6. Front
  7. Dequeue

实现：

1. 链表：front处需要出队，即需要索引到下一元素，故将链表头做front
2. 数组：

      struct  QueueRecord {
       int     Capacity ;   /* max size of queue */
       int     Front;          /* the front pointer */
       int     Rear;           /* the rear pointer */
       int     Size;  /* Optional - the current size of queue */
       ElementType  *Array;    /* array for queue elements */
    } ; 
   

循环队列

实现：r = (r + 1) % SIZE

问题：队列满时，r = f - 1；队列空时，r = f - 1，无法区分队列满 / 空状态

• 本质：利用r, f相对位置判断队列状态，而相对位置有N种，队列状态有N + 1种，无法覆盖
• 解决：规定队列具有N - 1个元素时为满，即 判空：(r + 1) % SIZE == f 判满：(r + 2) % SIZE == f

  为降低编程复杂性，将实际队尾后一个元素记作r，则判空：r % SIZE == f 判满：(r + 1) % SIZE == f