C++ 循环队列

2022-12-08 22:53:49

文章目录

- - 总结归纳
  - 代码实现

总结归纳

队列实际上就是现实生活中的排队，队头的人先走，新来的人排到队尾。先进先出，后进后出。
队列的实现，需要一个队头指针，一个队尾指针，用于入队和出队。对于循环队列，初始化时需将 Q.front = Q.rear = 0，Q.front 指向队头，Q.rear 指向新元素入队的位置。
循环队列，物理上仍然是申请一片连续的内存空间，但通过 (Q.rear + 1) % MaxSize == Q.front 的判断条件从逻辑上模拟环状空间，从而实现循环队列。
代码中值得一提的是 GetLength(SqQuene &Q, ElemType &len) 函数（获取队列长度），当有元素出队时，实际上只是将 Q.front 前移，从逻辑上出队，原先的队头仍然存在，当下次有新元素入队时直接进行覆盖，所以长度的遍历应从 Q.front 开始；而在队列的初始化中，我们设置的是 Q.front = Q.rear = 0 ，例如：当队列中有一个元素时，Q.front = 0，而 length = 1，所以我们需要将这个 1 补回来，才是真正的队列长度。
以往的 GetLength 代码，总是通过指针来进行遍历，而循环队列能不能用指针获取长度，我的看法是不可以（如果可以麻烦告诉我）。之前的数据结构能用指针遍历，是因为 struct 结构体中就定义了指针，所以可以申请一个结构体指针指向该结构体，通过 p = p->next 来进行遍历；而循环队列的实质仍然是一片连续的内存空间，诚然你可以申请一个数组指针 int *p = Q.data，但又回到了刚才的问题：在已有元素出队的情况下，Q.data 的第一个元素就不是队头，这会影响到队列长度的判断。而对于链式数据结构，删了就是删了，直接 delete / free ，就没有这个问题。

// 获取队列长度
bool GetLength(SqQuene &Q, ElemType &len) {
    if (Q.front == Q.rear) {
        len = 0;
    } else {
        len = Q.front; // 指向队头
        while ((len + 1) % MaxSize != Q.rear) {
            len++;
        }
        len = len - Q.front + 1; // 如果有元素出队，会导致Q.front不为0，影响长度的判断，且初始化队列时，Q.front置为0，同样影响长度
    }
    return true;
}

代码实现

/*
循环队列
*/

#include <iostream>

#define MaxSize 10 // 队列中元素的最大个数

using namespace std;

typedef int ElemType;

struct SqQuene {
    ElemType data[MaxSize]; // 队列中元素的最多个数
    int front, rear;        // 队头指针，队尾指针
};

// 初始化队列
void InitQuene(SqQuene &Q) { Q.front = Q.rear = 0; }

// 队列判空
bool QueneEmpty(SqQuene &Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

// 入队
bool EnQuene(SqQuene &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) { // 队满
        return false;
    } else {
        Q.data[Q.rear] = x; // 赋值给下一队尾
        Q.rear = (Q.rear + 1) %
                 MaxSize; // 在逻辑上将存储空间变为“环状”，物理上仍然是静态数组
        return true;
    }
}

// 出队
bool DeQuene(SqQuene &Q, ElemType &x) {
    if (Q.rear == Q.front) { // 队空
        return false;
    } else {
        x = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize; // 队头指针后移
        return true;
    }
}

// 获取队头元素
bool GetHead(SqQuene &Q, ElemType &x) {
    if (Q.rear == Q.front) { // 队空
        return false;
    } else {
        x = Q.data[Q.front];
        return true;
    }
}

// 获取队列长度
bool GetLength(SqQuene &Q, ElemType &len) {
    if (Q.front == Q.rear) {
        len = 0;
    } else {
        len = Q.front; // 指向队头
        while ((len + 1) % MaxSize != Q.rear) {
            len++;
        }
        len = len - Q.front + 1; // 如果有元素出队，会导致Q.front不为0，影响长度的判断，且初始化队列时，Q.front置为0，同样影响长度
    }
    return true;
}

int main() {
    SqQuene Q;
    InitQuene(Q);

    ElemType head, pop, length;

    for (int i = 1; i < 6; i++) {
        EnQuene(Q, i);
    }

    GetHead(Q, head);
    cout << "队头元素：" << head << endl;

    GetLength(Q, length);
    cout << "队列长度：" << length << endl;

    DeQuene(Q, pop);
    cout << "出队元素：" << pop << endl;

    GetHead(Q, head);
    cout << "队头元素：" << head << endl;

    GetLength(Q, length);
    cout << "队列长度：" << length << endl;
}

码农公寓

文章目录

总结归纳

代码实现

相关文章