顺序队列

• 队列的判空条件为首尾指针相同 Q.front==Q.rear

循环队列

为了方便指针计算，使用循环队列

• 循环队列入队操作Q.rear = (Q.rear+1) % MaxSize
• 队满条件：(Q.rear+1)%MaxSize==Q.front
• 队中的元素个数：(Q.rear-Q.front+MaxSize)%MaxSize

这样会导致最后一个结点不可用（不然队满和队空时前后指针都是一样，无法判断）

解决结点浪费问题

1. 新增一个属性 size

   xxxxxxxxxx
   26
   1
      typedef struct {
   2
       ElemType data[MaxSize];
   3
       // 队首指针，队尾指针
   4
       int front, rear;
   5
       
   6
       // 用来存放队列大小
   7
       int size;
   8
      } SqQueue;
   9
      bool InitQueue(SqQueue &Q) {
   10
       // 原来的操作
   11
       Q.size = 0;
   12
       return true;
   13
      }
   14
      bool EnQueue(SqQueue &Q, ElemType x) {
   15
       // 原来的操作
   16
       Q.size++;
   17
       return true;
   18
      }
   19
      bool DeQueue(SqQueue &Q, ElemType &x) {
   20
       // 原来的操作
   21
       Q.size--;
   22
       return true;
   23
      }
   24
      bool QueueEmpty(SqQueue Q) {
   25
       return (Q.size==0);
   26
      }
   

   通过size属性为 0 还是 MaxSize 就能判断出队列是否为空

2. 新增一个属性 tag

   xxxxxxxxxx
   26
   1
   typedef struct {
   2
       ElemType data[MaxSize];
   3
       // 队首指针，队尾指针
   4
       int front, rear;
   5
       
   6
       // 用来存放上一个操作是增加还是删除，增加：1，删除：0
   7
       int tag;
   8
   } SqQueue;
   9
   bool InitQueue(SqQueue &Q) {
   10
       // 原来的操作
   11
       Q.tag = 0;
   12
       return true;
   13
   }
   14
   bool EnQueue(SqQueue &Q, ElemType x) {
   15
       // 原来的操作
   16
       Q.tag = 1;
   17
       return true;
   18
   }
   19
   bool DeQueue(SqQueue &Q, ElemType &x) {
   20
       // 原来的操作
   21
       Q.tag = 0;
   22
       return true;
   23
   }
   24
   bool QueueEmpty(SqQueue Q) {
   25
       return (Q.front==Q.rear && Q.tag==0);
   26
   }
   

   只有增加时会导致队满，只有删除时会导致队空

错题集