数据结构揭秘：如何用数组实现循环队列

目录

什么是循环队列？

数组实现的优势

代码实现

代码解析

代码执行流程

总结

在计算机科学中，队列是一种重要的数据结构，遵循先进先出（FIFO）的原则。本文将介绍如何使用数组实现一个循环队列，并提供相应的代码示例。

什么是循环队列？

循环队列是一种特殊的队列结构，它的尾部连接到头部，形成一个环形结构。这种设计可以有效利用存储空间，避免因队列前端出队而导致的空间浪费。与线性队列相比，循环队列能够更好地利用数组的空间。

数组实现的优势

使用数组实现队列的一个主要优势是可以通过索引直接访问元素，具有较高的访问效率。然而，数组的大小是固定的，因此在设计时需要考虑队列的最大容量。

代码实现

以下是一个使用数组实现的循环队列的代码示例：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; // 数组存放 MaxSize 个元素
    int front, rear; // 队列头和队列尾
} SqQueue;

void InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0; // 初始化循环队列，让头和尾都指向零号
}

bool isEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) { // 判断循环队列是否满
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize; // rear + 1 如果大于数组最大下标回到开头
    return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.rear == Q.front) {
        return false; // 队列为空
    }
    x = Q.data[Q.front]; // 出队
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

int main() {
    SqQueue Q;
    InitQueue(Q);
    bool ret;
    ret = isEmpty(Q);
    if (ret) {
        printf("SqQueue is Empty\n");
    } else {
        printf("SqQueue not is Empty\n");
    }
    
    // 入队操作
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    ret = EnQueue(Q, 6); // 尝试入队第六个元素
    ret = EnQueue(Q, 7); // 尝试入队第七个元素
    if (ret) {
        printf("EnQueue success\n");
    } else {
        printf("EnQueue failed\n");
    }
    
    ElemType element; // 存储出队元素
    ret = DeQueue(Q, element);
    if (ret) {
        printf("DeQueue success element = %d\n", element);
    } else {
        printf("DeQueue failed\n");
    }

    ret = EnQueue(Q, 8); // 尝试入队第八个元素
    if (ret) {
        printf("EnQueue success\n");
    } else {
        printf("EnQueue failed\n");
    }
    
    return 0;
}

代码解析

1. 数据结构定义：

   • SqQueue 结构体定义了循环队列，包含一个数组 data 用于存储元素，以及两个整数 front 和 rear 用于指示队列的头和尾。

2. 初始化队列 (InitQueue)：

   • 将队列的头和尾都初始化为 0，表示队列为空。

3. 判断队列是否为空 (isEmpty)：

   • 通过比较 front 和 rear 的值来判断队列是否为空。

4. 入队操作 (EnQueue)：

   • 检查队列是否已满。如果满，则返回 false。
   • 否则，将元素添加到 rear 指向的位置，并更新 rear 的位置。

5. 出队操作 (DeQueue)：

   • 检查队列是否为空。如果为空，则返回 false。
   • 否则，返回 front 指向的元素，并更新front 的位置。

代码执行流程

在 main 函数中，我们首先初始化队列并检查其是否为空。接着，我们进行一系列的入队和出队操作，展示了循环队列的基本功能。

1.初始化队列：

SqQueue Q;
InitQueue(Q);

 这段代码创建了一个队列 Q 并将其初始化。

2.检查队列是否为空：

ret = isEmpty(Q);
if (ret) {
    printf("SqQueue is Empty\n");
} else {
    printf("SqQueue not is Empty\n");
}

通过调用 isEmpty 函数，我们可以确认队列在初始化后确实为空 。

3.入队操作：

EnQueue(Q, 3);
EnQueue(Q, 4);
EnQueue(Q, 5);
ret = EnQueue(Q, 6);
ret = EnQueue(Q, 7);

我们依次将元素 3、4 和 5 入队。接着尝试入队 6 和 7。由于队列的最大容量为 5，因此在尝试入队第六个元素时，队列会返回失败。

4.出队操作：

ElemType element; // 存储出队元素
ret = DeQueue(Q, element);
if (ret) {
    printf("DeQueue success element = %d\n", element);
} else {
    printf("DeQueue failed\n");
}

 我们从队列中出队一个元素，并打印出该元素的值。如果队列为空，则会返回失败。

5.再次入队：

ret = EnQueue(Q, 8);
if (ret) {
    printf("EnQueue success\n");
} else {
    printf("EnQueue failed\n");
}

在出队一个元素后，我们再次尝试入队一个新元素 8。由于队列现在有空间，这次入队操作会成功。 

总结

通过使用数组实现循环队列，我们能够高效地管理数据，避免了固定大小数组的限制。循环队列的设计使得我们可以在队列的两端进行操作，而不必担心空间的浪费。

在实际应用中，循环队列可以用于任务调度、缓冲区管理等场景。希望本文能帮助你理解循环队列的实现及其应用。