• 队列的抽象数据类型

    c
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    ADT 队列（queue）
    Data
    Operation
        InitQueue(*Q): 初始化操作，建立一个空队列Q
        DestroyQueue(*Q): 若队列Q存在，则销毁它
        ClearQueue(*Q): 将队列Q清空
        QueueEmpty(Q): 若队列Q为空，返回true，否则返回false
        GetHead(Q, *e): 若队列Q存在且非空，用e返回队列Q的队头元素
        EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素
        DeQueue(*Q, *e): 删除队列Q中队头元素，并用e返回其值
        QueueLength(Q): 返回队列Q的元素个数
    endADT

  • 循环队列

    • 循环队列的结构

      c
      1
      2
      3
      4
      5
      6
      1 typedef int QElemType; // QElemType类型根据实际情况而定，这里假设为int
      2 typedef struct {
      3     QElemType data[MAXSIZE];
      4     int front; // 头指针
      5     int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
      6 } SqQueue;

    • 循环队列的初始化

      c
      1
      2
      3
      4
      5
      6
      1 // 初始化一个空队列Q
      2 Status InitQueue(SqQueue *Q) {
      3     Q->front = 0;
      4     Q->rear = 0;
      5     return OK;
      6 }

    • 求循环队列的长度

      c
      1
      2
      3
      4
      1 // 返回Q的元素个数，也就是队列的当前长度
      2 int QueueLength(SqQueue Q) {
      3     return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
      4 }

    • 循环队列的入队列操作

      c
      1
      2
      3
      4
      5
      6
      7
      8
      1 // 若队列未满，则插入元素e为Q新的队尾元素
      2 Status enQueue(SqQueue *Q, QElemType e) {
      3     if ((Q->rear+1)%MAXSIZE == Q->front) // 队列满的判断
      4         return ERROR;
      5     Q->data[Q->rear] = e; // 将元素e赋值给队尾
      6     Q->rear = (Q->rear+1)%MAXSIZE; // rear指针向后移一位置，若到最后则转到数组头部
      7     return OK;
      8 }

  • 队列的链式存储结构（链队列）

    • 链队列的结构

      c
      1
      2
      3
      4
      5
      6
      7
      8
      9
      1 typedef int QElemType; // QElemType类型根据实际情况，这里假设为int
      2 typedef struct QNode { // 结点结构
      3     QElemType data;
      4     struct QNode *next;
      5 } QNode, *QueuePtr;
      6 
      7 typedef struct { // 队列的链表结构
      8     QueuePtr front, rear; // 队头、队尾指针
      9 } LinkQueue;

    • 链队列的入队操作

      c
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
       1 // 插入元素e为Q的新的队尾元素
       2 Status EnQueue(LinkQueue *Q, QElemType e) {
       3     QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
       4     if (!s) // 存储分配失败
       5         exit(OVERFLOW);
       6     s->data = e;
       7     s->next = NULL;
       8     Q->rear->next = s; // 把拥有元素e新结点s赋值给原队尾结点的后继
       9     Q->rear = s; // 把当前的s设置为队尾结点，rear指向s
      10     return OK;
      11 }

    • 链队列的出队操作

      c
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
       1 // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
       2 Status DeQueue(LinkQueue *Q, QElemType *e) {
       3     QueuePtr p;
       4     if (Q->front == Q->rear)
       5         return ERROR;
       6     p = Q->front->next; // 将欲删除的队头结点暂存给p
       7     *e = p->data; // 将欲删除的队头结点的值赋值给e
       8     Q->front->next = p->next; // 将原队头结点后继p->next赋值给头结点
       9     if (Q->rear == p) // 若队头是队尾，则删除后将rear指向头结点
      10         Q->rear = Q->front;
      11     free(p);
      12     return OK;
      13 }