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

假溢出-引出循环队列

假设当前队列分配的最大空间为 6, 则当队列处于图(d) 所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为 “假溢出＂。这是由＂队尾入队，队头出队” 这种受限制的操作造成的。

怎样解决这种 “假溢出” 问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，如图所示，称之为循环队列。

base[0]接在hase[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

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

判断循环队列队空队满

少用一个元素空间

队空：front==rear

队满：(rear+1)%MAXQSIZE==front

循环队列的操作

队列的初始化


Status InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXQSIZE]    // 分配数组空间
    // Q.base = (QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base) exit(OVERFLOW);         // 存储分配失败
    Q.front=Q.rear=0;                   // 头指针尾指针置为0，队列为空
    return OK;
}

求循环队列长度

对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。


int QueueLength(SqQueue Q){
    // 返回Q的元素个数，即队列的长度
    return(Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;
}

循环队列入队

入队操作是指在队尾插入一个新的元素。


Status EnQueue(SqQueue &Q, QElemType e) {
    // 插入元素e为Q的新的队尾元素
    if((Q.rear+1) % MAXQSIZE == Q.front)    // 尾指针在循环意义上加1后等于头指针，表明队满
        return ERROR;
    Q.base[Q.rear] = e;                     // 新元素插入队尾
    Q.rear = (Q.rear + 1) % MAXQSIZE;       // 队尾指针加1
    return OK;
}

循环队列出队

出队操作是将队头元素删除。


Status DeQueue(SqQueue &Q, QElemType &e) {
    // 删除Q的队头元素，用e返回其值
    if(Q.front==Q.rear) return ERROR;    // 队空
    e = Q.base[Q.front];                 // 保存队头元素
    Q.front = (Q.front + 1) % MAXQSIZE;  // 队头指针加1
    return OK;
}

取循环队列队头元素

当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。


SElemType GetHead(SqQueue Q) {
    // 返回Q的队头元素，不修改队头指针
    if(Q.front != Q.rear)        // 队列非空
        return Q.base[Q.front];  // 返回队头元素的值，队头指针不变
}

队列-链式队列

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

队列的链式存储结构

链队列的类型定义


#define MAXQSIZE 100    // 最大队列长度
typedef struct Qnode {
    QElemType data;
    stuct Qnode *next;
}QNode, *QueuePtr;
 
typedef struct {
    QueuePtr front;    // 队头指针
    Queueptr rear;     // 队尾指针
}LinkQueue;

链式队列的操作

链队的初始化


Status InitQueue(LinkQueue &Q) {
    // 构造一个空队列Q
    Q.front = Q.rear = new QNode;    // 生成新结点作为头结点，队头和队尾指针指向此结点
    Q.front -> next = NULL;          // 头结点的指针域置空
    return OK;
}

链队的入队


Status EnQueue(LinkQueue &Q, QElemType e) {
    // 插入元素e为Q的新的队尾元素
    p = new QNode;    // 为入队元素分配结点空间，用指针p指向
    p -> data = e;    // 将新结点数据域置为e
    p -> next = NULL; Q.rear -> next = p;    // 将新结点插入到队尾
    Q.rear = p;       // 修改队尾指针
    return OK;
}

链队的出队


Status DeQueue(LinkQueue &Q, QElemType &e) {
    // 删除Q的队头元素，用e返回其值
    if(Q.front == Q.rear) return ERROR;    // 若队列空，则返回ERROR
    p = Q.front -> next;                   // p指向队头元素
    e = p -> data;                         // e保存队头元素的值
    Q.front -> next = p -> next;           // 修改头指针
    if(Q.rear == p) Q.rear = Q.front;      // 最后一个元素被删，队尾指针指向头结点
    delete p;                              // 释放原队头元素的空间
    return OK;
}

需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

取链队的队头元素


SElemType GetHead(LinkQueue Q) {
    // 返回Q的队头元素，不修改队头指针
    if(Q.front != Q.rear){                 // 队列非空
        return Q.front -> next -> data;    // 返回队头元素的值，队头指针不变
    }
}

销毁链队列


Status DestroyQueue(LinkQueue &Q) {
    while(Q.front) {
        p= Q.front -> next; 
        free(Q.front);
        Q.front = p;
    } // Q.rear = Q.front -> next;    free(Q.front);    Q.front = Q.rear;
    return OK;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/636669