队列的表示和操作的实现

  • 队列是仅在表尾进行插入操作，在表头进行删除操作的线性表。

  • 表尾即$a_n$端，称为队尾；表头即$a_1$端，称为队头。

  • 它是一种先进先出（FIFO）的线性表。

  • 插入元素称为入队；删除元素称为出队。

  • 队列的存储结构为链队或顺序队（常用循环顺序队）。

队列的抽象数据类型定义


ADT Queue{

    数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}

    数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}	约定其中a1端为队列头，an端为队列尾。

        基本操作：

        InitQueue(&Q)	操作结果：构造空队列Q

        DestroyQueue(&Q)条件：队列Q已存在；操作结果：队列Q被销毁

        ClearQueue(&Q)	条件：队列Q已存在；操作结果：将Q清空

        QueueLength(Q)	条件：队列Q已存在；操作结果：返回Q的元素个数，即队长

        GetHead(Q,&e)	条件：Q为非空队列；操作结果：用e返回Q的队头元素

        EnQueue(&Q,e)	条件：队列Q已存在；操作结果：插入元素e为Q的队尾元素

        DeQueue(&Q,&e)	条件：Q为非空队列；操作结果：删除Q的队头元素，用e返回值

        ......还有将队列置空、遍历队列等操作.….

}ADT Queue

循环队列的顺序表示——用一维数组base[MAXQSIZE]


#define MAXQSIZE 100	//最大队列长度

Typedef struct{

    QElemType *base;	//初始化的动态分配存储空间

    int front;	//头指针

    int rear;	//尾指针

}SqQueue;
注意：

  • 若front = 0,rear = MAXQSIZE时再入队——真溢出

  • 若front ≠ 0,rear = MAXQSIZE时再入队——假溢出

20

解决假上溢的方法——引入循环队列

base[0]接在base[MAXQSIZE-1]之后，若rear+1==M,则令rear=0;

实现方法：利用模(mod,C语言中：%)运算。

  • 插入元素：Q.base[Q.rear]=x;

    ​ Q.rear=(Q.rear+1)%MAXQSIZE;

  • 删除元素：x=Q.base[s.front]

    ​ Q.front=(Q.front+1)%MAXQSIZE

  • 循环队列：循环使用为队列分配的存储空间

如何判断队空还是队满

队空和队满的条件都是：font == rear如何区分呢？

解决方案：

  1. 另外设一个标志以区别队空、队满

  2. 另设一个变量，记录元素个数

  3. 少用一个元素空间

image-20230823095744639