数据结构——队列

文章目录

1. 概念

2. 存储结构

顺序队列

链式队列

对比顺序队列和链式队列

3. 队列操作

顺序队列操作

顺序队列的问题

循环队列操作

4. 函数功能

1. initQueue

2. getSize

3. isEmpty

4. isFull

5. enqueue

6. dequeue

7. destroyQueue

8. printQueue

5. 代码示例

---

1. 概念

队列（Queue）是操作受限的线性表。它限制为仅允许在表的一端进行插入操作（入队或进队），在表的另一端进行删除操作（出队或离队）。队列是具有先进先出（FIFO，First In First Out）特点的线性结构，类似于生活中的排队现象。

组成部分

• 队首（front）：允许进行删除的一端称为队首。
• 队尾（rear）：允许进行插入的一端称为队尾。

操作

• 入队（Enqueue）：在队尾插入元素。
• 出队（Dequeue）：在队首删除元素。

队列元素顺序

在空队列中依次加入元素 a1,a2,…,an 之后，a1a_1a1​ 是队首元素，an 是队尾元素。显然，出队列的次序只能是 a1,a2,…,an​。

空队列

队列中没有元素时，称为空队列。

从图中可以看出：

• 入队操作在队尾进行，元素从队尾进入队列。
• 出队操作在队首进行，元素从队首离开队列。

队列遵循先入先出原则，即先进入队列的元素先离开队列。

队列的基本操作

在实现队列时，通常有以下基本操作：

1. 初始化队列：创建一个空队列。
2. 入队：在队尾添加一个元素。
3. 出队：在队首删除一个元素并返回它的值。
4. 获取队列长度：返回队列中元素的个数。
5. 判断队列是否为空：检查队列中是否有元素。
6. 查看队首元素：返回队首元素但不删除它。

2. 存储结构

队列的存储结构有两种主要实现方式：顺序队列和链式队列。以下是对这两种实现方式的详细解释。

顺序队列

顺序队列使用数组来存储队列元素。由于数组的定长特性，顺序队列在存储和管理队列元素时有一定的限制，但实现相对简单。

特点

• 固定大小：顺序队列的容量在初始化时就固定下来，不能动态扩展。
• 位置固定：队列元素的存储位置是连续的，可以通过索引直接访问元素。
• 容量限制：当队列满时，不能再加入新的元素，需要处理溢出问题。

操作

• 初始化队列：创建一个固定大小的数组。
• 入队：在队尾插入一个元素。
• 出队：在队首删除一个元素并返回其值。
• 获取队列长度：返回当前队列中元素的个数。
• 判断队列是否为空：检查队列中是否有元素。

链式队列

链式队列使用链表来存储队列元素。相比于顺序队列，链式队列可以动态调整容量，更适合需要频繁调整队列大小的场景。

特点

• 动态大小：链式队列可以动态调整大小，不受固定容量的限制。
• 灵活存储：队列元素的存储位置不连续，通过指针链接各个节点。
• 无容量限制：理论上可以存储任意数量的元素，只受限于系统内存。

操作

• 初始化队列：创建一个空的链表。
• 入队：在链表末尾插入一个元素。
• 出队：删除链表头部的元素并返回其值。
• 获取队列长度：返回当前链表中节点的个数。
• 判断队列是否为空：检查链表中是否有节点。

对比顺序队列和链式队列

顺序队列的优缺点

• 优点：
  • 存取效率高，时间复杂度为 O(1)O(1)O(1)。
  • 使用下标访问元素，访问速度快。
  • 内存空间利用率高，不需要额外的指针存储空间。
• 缺点：
  • 容量固定，不利于动态扩展。
  • 队列满时需要处理溢出。
  • 插入和删除操作需要移动大量元素，效率低。

链式队列的优缺点

• 优点：
  • 动态扩展，不受容量限制。
  • 插入和删除操作效率高，时间复杂度为 O(1)O(1)O(1)。
  • 内存利用灵活，只要系统内存足够，可以存储任意数量的元素。
• 缺点：
  • 需要额外的指针存储空间，内存利用率低。
  • 存取速度较慢，需要通过指针访问元素。
  • 需要处理指针的管理，容易出现内存泄漏。

3. 队列操作

队列是一种操作受限的线性表，只允许在表的一端进行插入操作（入队或进队），在表的另一端进行删除操作（出队或离队）。

队列的存储结构

队列可以使用顺序表（数组）或链表来实现，根据存储结构可以分为顺序队列和链式队列两种。

顺序队列操作

顺序队列使用数组来存储队列元素。队首指针指向队列第一个元素的位置，队尾指针指向队列最后一个元素的下一个位置。

• 空队列：front 和 rear 都指向数组的开始位置。
• 入队操作：元素添加到数组中，rear 指针向后移动。
• 出队操作：元素从数组中移除，front 指针向后移动。

顺序队列的问题

顺序队列中可能会出现“假溢出”现象，即队列中实际元素个数远小于数组大小，但由于 rear 已超过数组容量的上界而不能进行入队操作。

为了解决这个问题，有以下两种方法：

1. 使用数组实现，入队时添加到队列的最后，出队时将数组的所有元素左移。
2. 使用循环队列，将队列的存储空间看成是一个首尾相接的圆环，即循环队列。

循环队列操作

循环队列将数组首尾相连，形成一个环形结构，front 和 rear 指针在环形数组中循环移动。这样可以充分利用数组空间，避免“假溢出”现象。

循环队列的常见操作

• 初始化循环队列
• 检查队列是否为空
• 检查队列是否已满
• 入队操作
• 出队操作
• 获取队列中的元素

在循环队列中，入队操作将元素插入队列的最后，rear 指针向后移动；出队操作将元素从队列的前端移除，front 指针向后移动。

4. 函数功能

1. initQueue

功能：初始化队列，为队列分配内存，并设置队首、队尾指针和容量。

void initQueue(Queue *queue, size_t capacity) {
    // 为队列的数据部分分配内存
    queue->data = (int *)malloc(capacity * sizeof(int));
    // 初始化队首指针，指向数组的第一个位置
    queue->front = 0;
    // 初始化队尾指针，指向数组的第一个位置
    queue->rear = 0;
    // 设置队列的容量
    queue->capacity = capacity;
    // 初始化队列的元素个数为0
    queue->size = 0;
}

1. 分配内存：使用 malloc 分配容量大小的内存。
2. 初始化指针：将 front 和 rear 初始化为0。
3. 设置容量：将 capacity 设置为传入的参数值。
4. 设置元素个数：将 size 初始化为0。

2. getSize

功能：返回队列内元素的个数。

size_t getSize(const Queue *queue) {
    return queue->size; // 返回当前队列的元素个数
}

• 直接返回队列的 size 值。

3. isEmpty

功能：检查队列是否为空。

bool isEmpty(Queue *queue) {
    return queue->size == 0; // 如果队列的元素个数为0，则队列为空
}

• 判断 size 是否为0。

4. isFull

功能：检查队列是否已满。

bool isFull(Queue *queue) {
    return queue->size == queue->capacity; // 如果队列的元素个数等于容量，则队列已满
}

• 判断 size 是否等于 capacity。

5. enqueue

功能：在队尾插入元素。如果队列已满，打印错误信息。

void enqueue(Queue *queue, int element) {
    if (isFull(queue)) {
        printf("队列已满，无法入队！\n");
        return;
    }
    // 将新元素添加到队尾位置
    queue->data[queue->rear] = element;
    // 更新队尾指针，指向下一个位置（循环队列）
    queue->rear = (queue->rear + 1) % queue->capacity;
    // 更新队列的元素个数
    queue->size++;
}

1. 检查队列是否已满：调用 isFull 函数。
2. 插入元素：将元素插入到 rear 指针指向的位置。
3. 更新 rear：将 rear 更新为 (rear + 1) % capacity 实现循环。
4. 更新 size：增加元素个数。

6. dequeue

功能：从队首移除元素并返回。如果队列为空，返回-1。

int dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    // 获取队首元素的值
    int value = queue->data[queue->front];
    // 更新队首指针，指向下一个位置（循环队列）
    queue->front = (queue->front + 1) % queue->capacity;
    // 更新队列的元素个数
    queue->size--;
    // 返回被移除的队首元素
    return value;
}

1. 检查队列是否为空：调用 isEmpty 函数。
2. 获取元素：保存 front 指针指向的元素值。
3. 更新 front：将 front 更新为 (front + 1) % capacity 实现循环。
4. 更新 size：减少元素个数。
5. 返回元素值。

7. destroyQueue

功能：释放队列的内存，重置指针和容量。

void destroyQueue(Queue *queue) {
    free(queue->data); // 释放动态数组内存
    queue->data = NULL;
    queue->front = 0;
    queue->rear = 0;
    queue->capacity = 0;
    queue->size = 0;
}

1. 释放内存：使用 free 释放 data 部分的内存。
2. 重置指针和容量：将 data 设置为 NULL，将 front、rear、capacity 和 size 都设置为0。

8. printQueue

功能：打印队列中的所有元素。

void printQueue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空！\n");
        return;
    }
    int i = queue->front;
    for (int count = 0; count < queue->size; count++) {
        printf("%d ", queue->data[i]);
        i = (i + 1) % queue->capacity; // 循环访问队列元素
    }
    printf("\n");
}

1. 检查队列是否为空：调用 isEmpty 函数。
2. 遍历并打印元素：从 front 开始，循环打印每个元素，使用 (i + 1) % capacity 实现循环访问。

5. 代码示例

以下是一个完整代码，实现了创建并初始化队列，进行入队、出队操作，打印队列内容，最后释放队列内存的基本操作。

#include <stdio.h>
#include <stdlib.h>
 
// 队列结构体定义
typedef struct
{
    int *data;       // 动态数组存储队列元素
    size_t size;     // 队列内元素个数
    size_t capacity; // 动态数组的容量
    size_t front;    // 队列头指针
    size_t rear;     // 队列尾指针
} Queue;
 
// 初始化队列函数
void initQueue(Queue *queue, size_t capacity)
{
    queue->data = (int *)malloc(capacity * sizeof(int)); // 分配初始容量的内存
    queue->size = 0;                                     // 初始元素个数为0
    queue->capacity = capacity;                          // 设置容量
    queue->front = 0;                                    // 初始化队列头指针
    queue->rear = 0;                                     // 初始化队列尾指针
}
 
// 返回队列内元素个数函数
size_t getSize(const Queue *queue)
{
    return queue->size;
}
 
// 入队函数
void enqueue(Queue *queue, int element)
{
    // 检查队列是否已满
    if (queue->size == queue->capacity)
    {
        printf("队列已满，添加失败\n");
        return;
    }
    // 将元素添加到队列尾部
    queue->data[queue->rear] = element;
    // 循环更新队列尾指针
    queue->rear = (queue->rear + 1) % queue->capacity;
    // 更新元素个数
    queue->size++;
}
 
// 出队函数
int dequeue(Queue *queue)
{
    // 检查队列是否为空
    if (queue->size == 0)
    {
        printf("队列为空，无法出队！\n");
        return -1; // 队列为空，返回无效值
    }
    // 获取队列头部元素
    int dequeuedElement = queue->data[queue->front];
    // 循环更新队列头指针
    queue->front = (queue->front + 1) % queue->capacity;
    // 更新元素个数
    queue->size--;
    // 返回出队的元素
    return dequeuedElement;
}
 
// 释放队列内存函数
void destroyQueue(Queue *queue)
{
    free(queue->data); // 释放动态数组内存
    queue->data = NULL;
    queue->size = 0;
    queue->capacity = 0;
    queue->front = 0;
    queue->rear = 0;
}
 
// 遍历队列并打印函数
void printQueue(Queue *queue)
{
    // 检查队列是否为空
    if (queue->size == 0)
    {
        printf("队列为空！\n");
        return;
    }
    // 遍历队列元素
    for (int i = queue->front, j = 0; j < queue->size; i++, j++)
    {
        // 打印当前元素
        int data = queue->data[i % queue->capacity];
        printf("%d  ", data);
    }
    printf("\n");
}
 
int main()
{
    Queue myQueue;
 
    // 初始化队列
    initQueue(&myQueue, 2);
    printf("初始化队列,初始容量为2\n");
 
    // 入队元素
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
 
    // 打印队列内元素个数
    printf("队列内元素个数:%zu\n", getSize(&myQueue));
 
    // 打印队列内容
    printf("当前队列内容:");
    printQueue(&myQueue);
 
    // 出队元素
    printf("出队元素:%d\n", dequeue(&myQueue));
 
    // 再次打印队列内容
    printf("当前队列内容:");
    printQueue(&myQueue);
 
    // 再次入队元素
    enqueue(&myQueue, 3);
    printf("再次入队元素3\n");
 
    // 打印队列内容
    printf("当前队列内容:");
    printQueue(&myQueue);
 
    // 释放队列内存
    destroyQueue(&myQueue);
    printf("队列内存已释放\n");
 
    return 0;
}

 

• 定义队列结构体：

  • data：动态数组，用于存储队列元素。
  • size：当前队列中元素的个数。
  • capacity：动态数组的容量。
  • front：队列头指针，指向队列的第一个元素。
  • rear：队列尾指针，指向队列的最后一个元素的下一个位置。

• 初始化队列函数 initQueue：

  • 分配内存：使用 malloc 为队列的数据部分分配内存。
  • 初始化参数：设置 size 为0，capacity 为传入的参数值，front 和 rear 都初始化为0。

• 获取队列大小函数 getSize：

  • 返回队列的 size 值，即当前队列中的元素个数。

• 入队函数 enqueue：

  • 检查队列是否已满：如果 size 等于 capacity，队列已满，打印错误信息。
  • 添加元素：将新元素添加到 rear 指针指向的位置。
  • 更新指针和计数：循环更新 rear 指针，并增加 size。

• 出队函数 dequeue：

  • 检查队列是否为空：如果 size 为0，队列为空，打印错误信息并返回-1。
  • 获取元素：保存 front 指针指向的元素值。
  • 更新指针和计数：循环更新 front 指针，并减少 size。
  • 返回元素值。

• 释放队列内存函数 destroyQueue：

  • 使用 free 释放动态数组的内存，并将相关指针和计数重置为0或NULL。

• 遍历队列并打印函数 printQueue：

  • 检查队列是否为空：如果 size 为0，打印队列为空的信息。
  • 遍历并打印队列中的每个元素，使用循环队列的方式处理 front 和 rear 指针。

• 主函数 main：

  • 创建并初始化队列，进行入队、出队操作，打印队列内容，最后释放队列内存。