目录

一、队列

1.1基本概念

1.2基本操作

1.3 队列分类

1.3.1带头队列

1.3.2不带头队列

1.3.3 循环带头队列

1.3.4 循环不带头队列

1.3.5 总结

二、代码实现

2.1带头队列

2.2不带头队列

2.3循环带头队列

2.4循环不带头队列

---

一、队列

1.1基本概念

        队列（Queue）是一种常见的数据结构，它遵循先进先出（First In First Out, FIFO）的原则，类似于现实生活中排队等待的概念。在队列中，元素按照其插入的顺序排列，最先插入的元素将最先被移除。

• 队列元素：队列中的每个元素称为一个队列元素，可以是任意类型的数据。
• 队列头（front）：队列的头部，即第一个元素所在的位置，通常用于删除元素操作。
• 队列尾（rear）：队列的尾部，即最后一个元素所在的位置，通常用于插入元素操作。

1.2基本操作

        队列的基本操作主要包括入队和出队两种操作，通过这两种操作可以实现对队列中元素的添加和移除。在使用队列时，需要注意保持操作的顺序，遵循 FIFO 的规则，以确保队列的正确性和有效性。

• 入队（enqueue）：将元素插入到队列的末尾，即在队尾添加一个新元素。

• 出队（dequeue）：从队列的头部移除一个元素，并返回该元素的值。

• 判空（isEmpty）：判断队列是否为空，即队列中是否有元素。

• 判满（isFull）：判断队列是否已满，即队列中的元素数量是否达到上限。

• 获取队头元素（peek）：查看队列头部的元素值，但不移除该元素。

• 清空队列（clear）：移除队列中的所有元素，使队列变为空队列。

• 获取队列长度（size）：返回队列中元素的数量。

1.3 队列分类

1.3.1带头队列

• front 和 rear 的初始值：在带头的队列中，front 和 rear 的初始值通常都设置为 0，表示头结点的位置。
• 插入元素：在带头的队列中，插入元素时，先将 rear 加一，再将元素插入到 rear 所指向的位置。
• 删除元素：在带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。

1.3.2不带头队列

• front 和 rear 的初始值：通常情况下，不带头的队列中，front 和 rear 的初始值都为 -1，表示队列为空。
• 插入元素：在不带头的队列中，插入元素时，先将 rear 加一，再将元素插入到 rear 所指向的位置。
• 删除元素：在不带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。

1.3.3 循环带头队列

• front 和 rear 的初始值：通常情况下，front 和 rear 的初始值都为 0，表示队列为空。
• 插入元素：先将 rear 加一，再将元素插入到 rear 所指向的位置。如果 rear 达到数组末尾，可以通过取余运算将 rear 置为 0，实现循环利用数组空间。
• 删除元素：先将 front 加一，返回 front 指向的位置的元素。同样地，如果 front 达到数组末尾，可通过取余运算将 front 置为 0。
• 判空条件：当 front 和 rear 的值相等时，表示队列为空。
• 判满条件：当 (rear + 1) % 数组长度 等于 front 的值时，表示队列满。

1.3.4 循环不带头队列

• front 和 rear 的初始值：通常情况下，front 和 rear 的初始值都为 -1，表示队列为空。
• 插入元素：先将 rear 加一，再将元素插入到 rear 所指向的位置。如果 rear 达到数组末尾，可以通过取余运算将 rear 置为 0，实现循环利用数组空间。
• 删除元素：在不带头的队列中，删除元素时，先将 front 加一，返回 front 指向的位置的元素。
• 判空条件：当 front 和 rear 的值相等且等于 -1 时，表示队列为空。
• 判满条件：当 (rear + 1) % 数组长度 等于 front 的值时，表示队列满。

1.3.5 总结

        总的来说，循环队列带头和不带头在判满和判空上的逻辑是相同的，都是根据指针的位置关系来判断队列状态；而引入头结点的主要作用是简化队列为空和队列满的判断逻辑，使队列操作更加灵活高效。

二、代码实现

2.1带头队列

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

#define SIZE 5


// 定义一个Queue结构体表示队列
typedef struct {
    int items[SIZE];
    int front;   // 队列头指针，指向头结点
    int rear;    // 队列尾指针，指向最后一个元素
} Queue;

// 创建一个空队列并返回其指针
Queue* createQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue)); // 为队列分配内存
    queue->front = 0; // 初始化队列头指针
    queue->rear = 0; // 初始化队列尾指针
    return queue;
}

// 判断队列是否满了
int isFull(Queue *queue) {
    return (queue->rear == SIZE); // 如果队列尾指针指向最后一个元素的下一个位置，则队列已满
}

// 判断队列是否为空
int isEmpty(Queue *queue) {
    return (queue->front == queue->rear); // 如果队列头指针和尾指针相等，说明队列为空
}

// 将元素添加到队列尾部
void enqueue(Queue *queue, int item) {
    if (isFull(queue)) { // 如果队列已满，打印提示信息
        printf("队列已满，无法入队。\n");
    } else {
        queue->rear++; // 队列尾指针加1
        queue->items[queue->rear - 1] = item; // 将元素存储到队列尾部
        printf("%d 入队成功。\n", item); // 打印添加成功信息
    }
}

// 从队列头部移除一个元素并返回其值
int dequeue(Queue *queue) {
    int item;
    if (isEmpty(queue)) { // 如果队列为空，打印提示信息并返回-1表示操作失败
        printf("队列为空，无法出队。\n");
        return -1;
    } else {
        item = queue->items[queue->front]; // 获取队列头部元素的值
        queue->front++; // 队列头指针加1
        printf("%d 出队成功。\n", item); // 打印移除成功信息
        return item; // 返回移除的元素值
    }
}

int main() {
    Queue *queue = createQueue(); // 创建一个新的队列并获取其指针

    // 进行入队列和出队列操作
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);

    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue); // 尝试从空队列中出队列

    free(queue); // 释放队列内存空间

    return 0;
}

2.2不带头队列

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

#define SIZE 5


// 定义一个Queue结构体表示队列
typedef struct {
    int items[SIZE]; // 存储队列元素的数组
    int front; // 队列头指针
    int rear; // 队列尾指针
} Queue;


// 创建一个空队列并返回其指针
Queue* createQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue)); // 为队列分配内存
    queue->front = -1; // 初始化队列头指针
    queue->rear = -1; // 初始化队列尾指针
    return queue;
}

// 判断队列是否满了
int isFull(Queue *queue) {
    return (queue->rear == SIZE - 1); // 如果队列尾指针指向最后一个元素，则队列已满
}


// 判断队列是否为空
int isEmpty(Queue *queue) {
    return (queue->front == -1 || queue->front > queue->rear); // 如果队列头指针指向了最后一个元素（队列为空），或指向的元素已经被出队列了，说明队列为空
}


// 将元素添加到队列尾部
void enqueue(Queue *queue, int item) {
    if (isFull(queue)) { // 如果队列已满，打印提示信息
        printf("队列已满，无法入队。\n");
    } else {
        if (queue->front == -1) { // 如果队列为空，将队列头指针设置为0
            queue->front = 0;
        }
        queue->rear++; // 队列尾指针加1
        queue->items[queue->rear] = item; // 将元素存储到队列尾部
        printf("%d 入队成功。\n", item); // 打印添加成功信息
    }
}


// 从队列头部移除一个元素并返回其值
int dequeue(Queue *queue) {
    int item;
    if (isEmpty(queue)) { // 如果队列为空，打印提示信息并返回-1表示操作失败
        printf("队列为空，无法出队。\n");
        return -1;
    } else {
        item = queue->items[queue->front]; // 获取队列头部元素的值
        queue->front++; // 队列头指针加1
        printf("%d 出队成功。\n", item); // 打印移除成功信息
        return item; // 返回移除的元素值
    }
}


int main() {
    Queue *queue = createQueue(); // 创建一个新的队列并获取其指针

    // 进行入队列和出队列操作
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);

    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue); // 尝试从空队列中出队列

    free(queue); // 释放队列内存空间

    return 0;
}

2.3循环带头队列

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

#define MAX_SIZE 4     // 队列的最大容量，带头

// 循环队列结构体
typedef struct {
    int data[MAX_SIZE];  // 用数组存储队列元素
    int front;           // 队头指针
    int rear;            // 队尾指针
} CircularQueue;

// 初始化循环队列
void initQueue(CircularQueue *queue) {
    queue->front = 0;    // 初始时队头指针指向第一个元素
    queue->rear = 0;     // 初始时队尾指针指向第一个元素
}

// 判断队列是否为空
int isEmpty(CircularQueue *queue) {
    return queue->front == queue->rear;  // 队列为空时，队头指针与队尾指针相等
}

// 判断队列是否已满
int isFull(CircularQueue *queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;  // 队列已满时，队尾指针的下一个位置为队头指针
}

// 入队操作
void enqueue(CircularQueue *queue, int item) {
    if (isFull(queue)) {  // 判断队列是否已满
        printf("队列已满，无法插入新元素\n");
    } else {
        queue->data[queue->rear] = item;  // 将新元素插入队尾
        queue->rear = (queue->rear + 1) % MAX_SIZE;  // 移动队尾指针的位置
        printf("入队成功: %d\n", item);
    }
}

// 出队操作
int dequeue(CircularQueue *queue) {
    int item;
    if (isEmpty(queue)) {  // 判断队列是否为空
        printf("队列为空，无法出队\n");
        return -1;
    } else {
        item = queue->data[queue->front];  // 取出队头元素
        queue->front = (queue->front + 1) % MAX_SIZE;  // 移动队头指针的位置
        printf("出队元素: %d\n", item);
        return item;
    }
}

// 主函数
int main() {
    CircularQueue queue;
    initQueue(&queue);  // 初始化循环队列

    enqueue(&queue, 1);  // 入队操作
    enqueue(&queue, 2);
    enqueue(&queue, 3);
    enqueue(&queue, 3);

    dequeue(&queue);  // 出队操作
    dequeue(&queue);
    dequeue(&queue);
    dequeue(&queue);

    return 0;
}

2.4循环不带头队列

#include <stdio.h>

#define MAX_SIZE 5

// 定义循环队列结构体，不带头
typedef struct {
    int data[MAX_SIZE];  // 用数组存储队列元素
    int front;           // 队头指针
    int rear;            // 队尾指针
} CircularQueue;

// 初始化循环队列
void initQueue(CircularQueue *queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 判断队列是否为空
int isEmpty(CircularQueue *queue) {
    return (queue->front == -1 && queue->rear == -1);
}

// 判断队列是否已满
int isFull(CircularQueue *queue) {
    return ((queue->rear + 1) % MAX_SIZE == queue->front);
}

// 入队操作
void enqueue(CircularQueue *queue, int value) {
    if (isFull(queue)) {
        printf("队列已满，无法入队。\n");
    } else if (isEmpty(queue)) {
        queue->front = 0;
        queue->rear = 0;
        queue->data[queue->rear] = value;
        printf("%d 入队成功。\n", value);
    } else {
        queue->rear = (queue->rear + 1) % MAX_SIZE;
        queue->data[queue->rear] = value;
        printf("%d 入队成功。\n", value);
    }
}

// 出队操作
int dequeue(CircularQueue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队。\n");
        return -1;
    } else {
        int value = queue->data[queue->front];
        if (queue->front == queue->rear) {
            queue->front = -1;
            queue->rear = -1;
        } else {
            queue->front = (queue->front + 1) % MAX_SIZE;
        }
        printf("%d 出队成功。\n", value);
        return value;
    }
}

int main() {
    CircularQueue queue;
    initQueue(&queue);

    // 入队操作
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);
    enqueue(&queue, 60);  // 队列已满，无法入队

    // 出队操作
    dequeue(&queue);
    dequeue(&queue);
    dequeue(&queue);
    dequeue(&queue);
    dequeue(&queue);
    dequeue(&queue);  // 队列已空，无法出队

    return 0;
}