队列的抽象数据类型的类型定义

image-20220906162541361

队列的表示与实现

  • 队列的物理存储可以用顺序存储结构,也可用链式存储结构。
  • 相应地,队列的存储方式也分为两种,即顺序队列链式队列

顺序队列

队列的顺序表示

用一维数组base[MAXQSIZE]

#define MAXQSIZE 100    //队列的最大长度
Typedef struct{    
    QElemType *base;    // 初始化的动态分配存储空间
    int front;            // 头指针
    int rear;            // 尾指针
}SqQueue;

解决假溢出问题

队列的入队出队示意图如下图:

image-20220906170347591

如果考虑当前对上述队列:J4、J5、J6入队,J3、J4出队;之后,还可以进行入队操作吗?

image-20220906172210979

显然,此时出现了溢出,此时 rear = MAXQSIZEfront != 0,此时如果再入队,称为假溢出;如果 rear = MAXQSIZEfront = 0,则称为真溢出

image-20220906172425914

解决假上溢的方法

  • 将队中元素依次向队头方向移动。

缺点:浪费时间,每移动一次,队中元素都要移动。

  • 将队空间设想成一个循环的表,即分配给队列的 m 个存储单元可以循环使用,当 rearmaxqsize 时,若向量的开始端空着,又可从头使用空着的空间。当 front maxqsize 时,也是一样

image-20220906173319937

引入循环队列:

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

  • base[0] 接在 base[MAXQSIZE-1] 之后,若 rear+1 = MAXQSIZE,则令rear=0
  • 实现方法:利用模(mod,C语言中:%)运算。
  • 插入元素:

如图所示,当没出现溢出的时候也使用取余运算,不影响入队操作:

image-20220906175930007

当在插入一个元素后,我们需要将指针 Q.rear 移到下标 0 的位置,此时,取余运算就起了作用:

image-20220906180031004

  • 删除元素:
x = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;

image-20220906180800820

解决队满队空的条件相同问题

image-20220906181512558

如图所示,可以清晰的看出,队满和队空的条件都是 Q.rear == Q.front成立的时候,因此需要加以区分;

解决方案:

  1. 另外设一个标志以区别队空、队满
  2. 另设一个变量记录元素个数
  3. 少用一个元素空间

这里介绍第三种:少用一个元素空间

即在加入最后一个元素之前进行判断,故而称为少用一个元素空间。

image-20220906182516532

循环队列的的初始化

Status InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXSIZE]; // 分配数组空间
    // Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));
    if(!Q.base) exit(OVERFLOW);    // 存储分配失败
    Q.front = Q,rear = 0;    // 头指针尾指针置为0,队列为空(数组当中首元素的地址就是指针)
    return OK;
}

求队列的长度

int QueueLength(SqQueue Q){
    return ((Q.rear - Q.front +MAXQSIZE)%MAXQSIZE);
}

image-20220906184640200

循环队列入队

Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR; // 队满
    Q.base[Q.rear] = e;    // 新元素加入队尾
    Q.rear = (Q.rear + 1)%MAXQSIZE;    // 队尾指针 +1
}

循环队列出列

Status DeQueue(SqQueue &Q,QElemType e){
    if(Q.rear == Q.front) return ERROR; // 队空
    e = Q.base[Q.rear];    // 保存队头元素
    Q.front = (Q.rear + 1)%MAXQSIZE;    // 队头指针 +1
    return OK;
}

取队头元素

Status GetHead(SqQueue Q){
    if(Q.rear != Q.front) // 队不为空
        return Q.base[Q.front];// 返回队头指针元素的值
}

链队的表示与实现

若用户无法估计所用队列的长度,则宜采用链队列;

image-20220907131855010

链队列的类型定义

#define MAXQSIZE 100    // 最大队列长度·
typedef struct Qnode{
    QElemType data;
    struct Qnode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front; // 队头指针
    QueuePtr rear; // 队尾指针
}LinkQueue;

链队列运算指针变化状况:

image-20220907132242009

链队列的初始化

Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = new QNode;
    // Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

链队列的销毁

Status DestoryQueue(LinkQueue &Q){
    while(Q.front){
        p = Q.front->next;
        delete Q.front;
        Q.front = p;
    }
    return OK;
}

改进:因为尾指针始终没有用到,因此可以用尾指针代替指针 p 的位置

Status DestoryQueue(LinkQueue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}

链队列的入队

由于链式存储一般不会出现内存溢出的情况,因此不判断队列是否已满

image-20220907135107036

Status EnQueue(LinkQueue &Q,QElemType e){
    QueuePtr p = new QNode;
    if(!p) exit(OVERFLOW);// 分配不成功
    p->data = e;
    p->next = NULL;
    Q.rear->next = p; 
    Q.rear = p;
}

链队列的出队

image-20220907135231513

Status DeQueue(LinkQueue &Q,QElemType e){
    
    if(Q.front == Q.rear) return ERROR; // 不能为空队列  
    QueuePtr p = new QNode;
    if(!p) exit(OVERFLOW);// p分配不成功
    
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front; // 删除的恰好是尾指针,则尾指针的位置也需要修改
    delete p;
    return OK;
}

求链队列的队头元素

Status DeQueue(LinkQueue Q,QElemType e){
    if(Q.front == Q.rear) return ERROR; // 不能为空队列  
    e = Q.front->next->data;
    return OK;
}
🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/97.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 24 日
赏杯咖啡