C 语言数据结构——队列
|
457
|
0
|
Linux C / C++,计算机基础

5484 字
|
39 分钟

队列的定义及其基本操作

队列是一种遵循先进先出（FIFO, First In First Out）原则的线性数据结构，广泛应用于计算机科学和日常生活中。以下是对队列及其基本操作的详细描述：

  1. 入队（Enqueue）：在队列的末端（队尾）添加一个新元素。这个操作总是将新元素放在队列的最后。
  2. 出队（Dequeue）：在队列的前端（队头）删除一个元素。执行出队操作后，原本位于队头之后的元素将成为新的队头。
  3. 访问队头元素（Peek）：访问但不删除队列的第一个元素，允许用户查看队列的前端元素而不影响队列本身。
  4. 判空（IsEmpty）：检查队列是否为空，即队列中是否没有任何元素。
  5. 判满（IsFull）：检查队列是否已满，这通常适用于固定大小的队列实现。对于动态队列，此操作可能不是必需的。
  6. 时间复杂度：所有上述基本操作都应保证在 O(1) 的时间复杂度内完成，以确保队列操作的效率。

202311211052492.png

固定长度循环数组队列的实现（思路）

假如数组的长度固定是 N，将此数组视为一个队列

假如固定数组的开头，也就是索引为 0 的首元素就是队头，然后再用一个索引 rear 标记数组存储元素的末尾，表示队尾

rear 其实是下一个新元素存储的下标

这种设计的话，此时队列的基本操作如下：

  1. 入队：在 rear 索引位置直接插入一个新元素，然后 rear++ 即可，时间复杂度是 O(1)
  2. 出队：直接删除下标为 0 的元素，但需要将数组元素从下标为 1 开始，全部向前移动 1 个位置，时间复杂度 O(n)
  3. 访问队头：直接访问下标为 0 的元素，时间复杂度是 O(1)
  4. 判空：当 rear = 0 时表示队列为空，时间复杂度是 O(1)
  5. 判满：当 rear = N 时，表示队列满了

这种设计是不合理的。

为了使得出队列成为一个 O(1) 时间复杂度的操作，于是新增一个索引 front, 用于标记队头元素，该索引就指示队头元素的位置，其它设计不变

这种设计的话，此时队列的基本操作如下：

  1. 入队：在 rear 索引位置直接插入一个新元素，然后 rear++ 即可，时间复杂度是 O(1)
  2. 出队：将 front 索引直接 ++，将 [front, rear)区间范围内的元素作为队列的元素，这样不需要移动元素，就实现了出队列。操作的时间复杂度是 O(1)
  3. 访问队头：直接访问下标为 front 的元素，时间复杂度是 O(1)
  4. 判空：当 rear = front 时，即两个索引相遇时，表示队列为空，时间复杂度是 O(1)
  5. 判满：当 rear = N 时，表示队列满了

这种设计看似合理，因为它所有的基本操作都满足 O(1) 的时间复杂度，但是存在致命的缺陷：这个队列是一次性的，无法重新利用已经入队井出队的内存区域，所以还需要改进，也就是循环队列。

实现循环队列最核心的问题就是两个索引应该如何移动，可以利用取模运算。

所以 rear 和 front 的移动应该变成：front =(front + 1) % N, rear = (rear+1)% N;

其它设计不变，仍然是 [front, rear) 索引范围内的元素是队列元素

这种设计的话，此时队列的基本操作如下：

  1. 入队：在 rear 索引位置直接插入一个新元素，然后 rear + 1 取模 N 向后移动即可，时间复杂度是 O(1)
  2. 出队：将 front 索引加 1 取模 N，将[front, rear）区间范围内的元素作为队列的元素，把以前入队井出队的内存区域重新利用
    起来，这样不需要移动元素，就实现了出队列，操作的时间复杂度是 O(1)
  3. 访问队头：直接访问下标为 front 的元素，时间复杂度是 O(1)
  4. 判空：当 rear = front 时，即两个索引相遇时，表示队列为空，时间复杂度是 O(1)
  5. 判满：当 rear = front 时，表示队列满了

于是判空判满就没有办法直接处理了，因为它们的条件是一样的。

有两种解决办法：

  1. 教科书上的解决办法，牺牲数组当中的一个存储空间，这个空间不存储元素
    当 (rear + 1) % N = front 时，就代表队列满了，只有当 rear == front 时，代表队列为空。缺点是队列就少了一个存储单元
  2. 更简单粗暴的实现方式（日常最常使用的方式，推荐）：
    直接在数组队列这个结构体类型当中维护一个 size 属性，这个属性代表当前队列中的元素数量，当 size = 0 时，队列是空的当 ；size = N 时，队列是满的。

固定长度循环数组队列的实现

结构体类型的定义

ArrayQueue 是一个使用数组实现的队列结构体类型，它包含以下几个成员：

  1. arr: 一个固定大小的数组，用于存储队列中的元素。
  2. front: 一个整型成员，用作队列的头部索引。
  3. rear: 一个整型成员，用作队列的尾部索引。
  4. size: 一个整型成员，表示队列中当前存储的元素数量。

在函数中，可以创建 ArrayQueue 类型的指针，并通过这个指针访问和操作队列。这种方法允许在函数之间传递队列的引用，而无需复制整个队列。

typedef struct
{
    // 由于是固长数组队列，所以直接把数组作为结构体对象的一个成员
    ElementType elements[QUEUE_CAPACITY];
    int front; // 队头元素的索引
    int rear;  // 队尾元素下一个位置的索引
    int size;  // 队列数组中实际存储元素的个数
} ArrayQueue;

创建和销毁数组队列

创建队列：使用 calloc 函数初始化一个空的 ArrayQueue 结构体。calloc 函数不仅分配内存，还会将内存初始化为 0 值，这为创建空队列提供了便利。

销毁队列：使用 free 函数释放 ArrayQueue 结构体所占用的内存。

在 queue_create 函数中，使用 calloc 分配内存后，应检查返回值是否为 NULL，以确保内存分配成功。如果分配失败，应由函数调用者处理错误。

// 初始化一个空队列
ArrayQueue *queue_create() {
 return calloc(1, sizeof(ArrayQueue));
}
// 销毁一个队列
void queue_destroy(ArrayQueue *q) {
 free(q);
}

判空和判满

判空操作：判空操作检查队列是否为空。如果队列的 size 成员为 0，则队列为空。

判满操作：判满操作检查队列是否已满。如果队列的 size 成员等于队列的容量 QUEUE_CAPACITY，则队列为满。

// 判满
bool is_full(ArrayQueue *q) {
   return q->size == QUEUE_CAPACITY;
}
// 判空
bool is_empty(ArrayQueue *q) {
 return q->size == 0;
}

入队操作

入队操作是在队列末尾添加新元素的过程。

  1. 判满操作：在执行入队之前，首先检查队列是否已满。如果队列已满，则无法执行入队操作。
  2. 添加元素：如果队列未满，将新元素添加到 rear 索引所指向的位置。
  3. 更新 rear 索引：更新 rear 索引到下一个位置，并使用取模运算确保索引在数组范围内循环。
  4. 更新 size：增加 size 成员，以反映队列中的元素数量增加。
  5. 返回结果：操作完成后，返回一个布尔值，指示入队操作是否成功。
// 入队
bool enqueue(ArrayQueue *q, ElementType element) {
    // 判满
    if (is_full(q)) {
        printf("error: queue is full.\n");
        return false;
    }
    // 队列没满时才入队
    q->elements[q->rear] = element;
    // 更新 rear 索引
    q->rear = (q->rear + 1) % QUEUE_CAPACITY;
    // 更新 size
    q->size++;
    return true;    // 入队成功
}

出队操作

出队操作是移除队列头部元素的过程。

  1. 判空操作：在执行出队之前，首先检查队列是否为空。如果队列为空，则无法执行出队操作。
  2. 记录并返回队首元素：如果队列不为空，记录队首元素的值，以便返回。
  3. 更新 front 索引：将 front 索引向前移动到下一个元素，并使用取模运算确保索引在数组范围内循环。
  4. 更新 size：减少 size 成员的值，以反映队列中元素数量的减少。
  5. 返回队首元素：返回记录的队首元素值。
ElementType dequeue(ArrayQueue *q) {
    // 判空
    if (is_empty(q)) {
        printf("error: queue is empty.\n");
        exit(1);
    }
    // 队列非空，记录队首元素以用于返回
    ElementType ret = q->elements[q->front];

    // 更新 front 索引
    q->front = (q->front + 1) % QUEUE_CAPACITY;

    // 不要忘记更新 size
    q->size--;
    return ret;
}

访问队首元素

访问队首元素操作允许查看队列头部的元素而不影响队列本身。

  1. 判空操作：在执行访问操作之前，首先检查队列是否为空。如果队列为空，则无法执行访问操作。
  2. 返回队首元素：如果队列不为空，返回队首元素的值。
// 访问队首元素
ElementType peek(ArrayQueue *q) {
    // 判断队列是否是空的
    if (is_empty(q)) {
        printf("error: queue is empty.\n");
        exit(1);
    }
    // 队列非空返回队首元素
    return q->elements[q->front];
}

链式队列

#ifndef LIST_QUEUE_H
#define LIST_QUEUE_H

#include <stdbool.h>

typedef int ElementType; ///< 定义队列中的元素类型

/**
 * @brief 队列节点的结构
 */
typedef struct node_s {
    ElementType data;
    struct node_s *next;
} QueueNode;

/**
 * @brief 链式队列结构
 */
typedef struct {
    QueueNode *front; ///< 队头结点指针
    QueueNode *rear;  ///< 队尾结点指针
} LinkedListQueue;

/**
 * @brief 创建链式队列
 * @return LinkedListQueue* 队列指针
 */
LinkedListQueue *create_queue();

/**
 * @brief 销毁链式队列
 * @param q 队列指针
 */
void destroy_queue(LinkedListQueue *q);

/**
 * @brief 入队列
 * @param q 队列指针
 * @param element 入队列元素
 * @return bool
 */
bool enqueue(LinkedListQueue *q, ElementType element);

/**
 * @brief 出队列并返回队头元素
 * @param q 队列指针
 * @return ElementType 队头元素
 */
ElementType dequeue(LinkedListQueue *q);

/**
 * @brief 访问队头元素
 * @param q 队列指针
 * @return ElementType 队头元素
 */
ElementType peek_queue(LinkedListQueue *q);

/**
 * @brief 判断队列是否为空
 * @param q 队列指针
 * @return bool
 */
bool is_empty(LinkedListQueue *q);

#endif // !LIST_QUEUE_H

链式队列的创建操作

创建链式队列涉及为队列结构体分配内存，并初始化其成员。

  1. 使用 calloc 分配内存：使用 calloc 函数分配 LinkedListQueue 结构体的内存。calloc 会初始化分配的内存为 0 值。
  2. 初始化队列结构体：
    • 初始化头结点 front 和尾结点 rear 为 NULL，因为新创建的队列是空的。
    • 初始化队列大小 size 为 0。
// 定义队列中的元素类型
typedef int ElementType;

// 队列节点的结构
typedef struct node_s {
    ElementType data;
    struct node_s *next;
} QueueNode;

// 队列的结构
typedef struct {
    QueueNode *front;  // 队头结点指针
    QueueNode *rear;   // 队尾结点指针
} LinkedListQueue;

// 函数声明
LinkedListQueue *create_queue() {
    return calloc(1, sizeof(LinkedListQueue));
}

链式队列的销毁操作

销毁链式队列涉及释放队列中所有结点的内存以及队列结构体本身的内存。

  1. 遍历并销毁结点：从头结点 front 开始遍历链表，逐个释放每个结点。
  2. 释放队列结构体：在所有结点都被释放之后，释放队列结构体 q 所占用的内存。
void destroy_queue(LinkedListQueue *q) {
    if (q == NULL) {
        return;
    }

    // 遍历并销毁结点
    QueueNode *current = q->front;
    while (current != NULL) {
        QueueNode *temp = current->next;
        free(current);
        current = temp;
    }

    // 销毁队列结构体
    free(q);
}

链式队列的入队操作

入队操作是在链式队列的尾部添加新结点的过程。

  1. 分配新结点：使用 malloc 函数为新结点分配内存。
  2. 初始化新结点：将新结点的 data 成员设置为要入队的元素，并将 next 指针初始化为 NULL。
  3. 尾插法插入：根据当前队列是否为空（即 front 是否为 NULL），决定是插入第一个结点还是插入到已有队列的末尾。
  4. 同步头尾指针：
    • 如果插入的是第一个结点，需要同步更新头结点 front 和尾结点 rear。
    • 如果队列已有元素，仅需更新尾结点 rear 指向新结点。
bool enqueue(LinkedListQueue *q, ElementType element) {
    QueueNode *new_node = (QueueNode *)malloc(sizeof(QueueNode));
    if (new_node == NULL) {
        fprintf(stderr, "Error: malloc failed in enqueue.\n");
        return false;
    }
    // 初始化新结点
    new_node->data = element;
    new_node->next = NULL;

    // 尾插法插入结点
    if (q->front == NULL) {
        q->front = new_node;
        q->rear = new_node;
    }
    else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
    q->size++;  // 更新队列大小
    return true;
}

链式队列的出队操作

出队操作是在链式队列的头部删除结点的过程。

  1. 判空操作：在执行出队之前，首先检查队列是否为空。如果队列为空，则无法执行出队操作。
  2. 保存出队结点数据：保存要删除的队首结点的数据，以便返回。
  3. 更新头结点指针：将头结点指针 front 移动到下一个结点。
  4. 更新尾结点指针：如果出队后队列变为空，同步更新尾结点指针 rear 为 NULL。
  5. 释放结点内存：释放原队首结点的内存。
  6. 返回出队结点数据：返回保存的出队结点的数据。
ElementType dequeue(LinkedListQueue *q) {
    if (is_empty(q)) {
        fprintf(stderr, "Error: queue is empty.\n");
        exit(EXIT_FAILURE);
    }

    QueueNode *tmp = q->front;
    // 保存出队的结点数据
    ElementType remove_data = tmp->data;

    // 更新队头指针
    q->front = tmp->next;
    if (q->front == NULL) {
        // 如果队头更新后,队列为空,说明出队的就是最后一个元素
        // 于是同步更新队尾指针
        q->rear = NULL;
    }

    q->size--;  // 更新队列大小
    free(tmp);   // 释放结点内存
    return remove_data;
}

链式队列的访问队首元素操作

访问队首元素操作允许查看链式队列头部的元素而不影响队列本身。

  1. 判空操作：在执行访问操作之前，首先检查队列是否为空。如果队列为空，则无法执行访问操作。
  2. 返回队首元素数据：如果队列不为空，返回队首结点的 data 成员。
ElementType peek_queue(LinkedListQueue *q) {
    if (is_empty(q)) {
        fprintf(stderr, "Error: queue is empty.\n");
        exit(EXIT_FAILURE);
    }
    // 返回队首元素数据
    return q->front->data;
}

链式队列的判空操作

判空操作用于检查链式队列是否为空。

  1. 判空逻辑：如果队列的头结点指针 front 是空指针 NULL，则表示队列为空。
  2. 返回结果：函数返回一个布尔值，如果队列为空，返回 true；否则返回 false。
bool is_empty(const LinkedListQueue *q) {
    // 队头指针是空指针，即表示空队列
    return q->front == NULL;
}

动态数组模型

在动态数组队列中，size 变量用于追踪当前队列中元素的数目。capacity 则表示队列的动态数组所能容纳的最大元素数量，即其实际长度。front 索引指向队列的队头元素，而 rear 索引则指向队尾元素之后的位置，这意味着在队尾添加新元素时，可以直接在 rear 索引处进行插入。

动态数组队列的基本操作与固定长度数组队列类似，它们都采用循环数组的方式进行元素的存储和管理。然而，当队列达到其容量上限时，就需要执行扩容操作。

扩容的条件是当 size 等于 capacity 时。扩容的本质是增加动态数组的长度，可以通过调用内存分配函数并结合适当的扩容策略来实现。但扩容后，原有的 front 和 rear 索引将不再适用，因为它们不再代表队头和队尾的位置。

一种直接的解决方案是对旧的动态数组进行遍历，从队头开始，直到队尾，将所有元素复制到新动态数组的起始位置。完成这一操作后，front 索引将重置为 0，而 rear 索引将更新为当前队列的 size。

为了将现有队列中的元素从队头到队尾复制到新的动态数组中避免在复制过程中发生元素覆盖的问题，需要使用 malloc（动态内存分配函数）为新的动态数组分配空间。在这个过程中不能使用 realloc（重新分配内存的函数），因为它可能会导致原有内存块的移动，从而破坏队列中元素的顺序。

在复制元素时应该从队头开始，逐个元素复制到新数组的起始位置。这样，一旦复制完成，front 索引将被设置为 0，而 rear 索引将根据复制的元素数量进行相应的更新。

#ifndef DYNAMIC_QUEUE_H
#define DYNAMIC_QUEUE_H

#include <stdbool.h>

typedef int ElementType;    ///< 该队列当前存储 int 元素
#define DEFAULT_CAPACITY 10    ///< 数组队列的初始长度是 10
#define THRESHOLD 1000     ///< 超过阈值每次扩容 1.5 倍扩，否则 2 倍的扩

/**
 * @brief 定义队列结构体
 */
typedef struct {
    ElementType *data; ///< 动态数组存储队列元素
    int front;         ///< 标记队头元素的索引
    int rear;          ///< 标记队尾元素下一个位置的索引
    int size;          ///< 当前队列中元素数量
    int capacity;      ///< 队列容量
} DynamicQueue;

/**
 * @brief 创建动态数组队列
 * @return DynamicQueue* 队列数组
 */
DynamicQueue *create_queue();

/**
 * @brief 销毁动态数组队列
 * @param q 队列数组
 */
void destroy_queue(DynamicQueue *q);

/**
 * @brief 判断队列是否为空
 * @param q 队列数组
 * @return bool
 */
bool is_empty(DynamicQueue *q);

/**
 * @brief 判断队列是否满了
 * @param q 队列数组
 * @return bool
 */
bool is_full(DynamicQueue *q);

/**
 * @brief 入队列
 * @param q 队列数组
 * @param data 入队列元素
 * @return bool
 */
bool enqueue(DynamicQueue *q, ElementType data);

/**
 * @brief 出队列并返回队头元素
 * @param q 队列数组
 * @return ElementType 出队列元素
 */
ElementType dequeue(DynamicQueue *q);

#endif // DYNAMIC_QUEUE_H

动态数组队列的创建和初始化

创建动态数组队列涉及分配内存以存储队列结构体和初始化队列的内部数组。

  1. 分配队列结构体内存：使用 calloc 为 DynamicQueue 结构体分配内存。calloc 初始化内存为 0 值，确保 front、rear 和 size 成员被正确初始化。
  2. 分配内部数组内存：使用 calloc 为内部数组 data 分配内存，以存储队列中的元素。使用 DEFAULT_CAPACITY 作为初始容量。
  3. 错误处理：如果 calloc 分配内存失败，打印错误信息，释放已分配的内存（如果有必要），并返回 NULL。
  4. 初始化队列结构体：设置 capacity 成员为初始容量 DEFAULT_CAPACITY。
typedef int ElementType;    // 该队列当前存储 int 元素
#define DEFAULT_CAPACITY 10 // 数组队列的初始长度是 10
#define THRESHOLD 1000     // 超过阈值每次扩容 1.5 倍扩，否则 2 倍的扩

// 定义队列结构体
typedef struct {
    ElementType *data;      // 动态数组存储队列元素
    int front;              // 标记队头元素的索引
    int rear;               // 标记队尾元素下一个位置的索引
    int size;               // 当前队列中元素数量
    int capacity;           // 队列容量
} DynamicQueue;

// 创建并初始化队列
DynamicQueue *create_queue() {
    DynamicQueue *q = calloc(1, sizeof(DynamicQueue));
    if (q == NULL) {
        printf("error: calloc failed in create_queue.\n");
        return NULL;
    }
    // front、rear、size 自动初始化 0 值，无需再手动初始化了
    q->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType));        // 使用 calloc 避免随机值
    if (q->data == NULL) {
        printf("error: calloc failed in create_queue.\n");
        free(q);
        return NULL;
    }
    q->capacity = DEFAULT_CAPACITY;
    return q;
}

动态数组队列的销毁操作

销毁动态数组队列涉及释放队列中所有结点的内存以及队列结构体本身的内存。

  1. 释放内部数组内存：使用 free 函数释放 DynamicQueue 结构体中的 data 数组。
  2. 释放队列结构体内存：使用 free 函数释放 DynamicQueue 结构体本身。
void destroy_queue(DynamicQueue *q) {
    if (q != NULL) {
        free(q->data);  // 释放内部数组内存
        free(q);         // 释放队列结构体内存
    }
}

动态数组队列的判空操作

判空操作用于检查动态数组队列是否为空。

  1. 判空逻辑：如果队列的 size 成员为 0，则表示队列为空。
  2. 返回结果：函数返回一个布尔值，如果队列为空，返回 true；否则返回 false。
bool is_empty(const DynamicQueue *q) {
    return q->size == 0;
}

动态数组队列的判满操作

判满操作用于检查动态数组队列是否已达到其最大容量。

  1. 判满逻辑：如果队列的 size 成员等于 capacity 成员，则表示队列已满。
  2. 返回结果：函数返回一个布尔值，如果队列为满，返回 true；否则返回 false。
bool is_full(const DynamicQueue *q) {
    return q->size == q->capacity;
}

动态数组队列的扩容操作

当动态数组队列达到其最大容量时，需要进行扩容以允许更多的元素被添加。

  1. 扩容策略：根据当前容量和预设的阈值 THRESHOLD 来决定新的容量。如果当前容量小于阈值，则新容量为当前容量的两倍；否则，新容量为当前容量的 1.5 倍。
  2. 内存重新分配：使用 malloc 函数分配一个新的、更大容量的数组。
  3. 复制元素：遍历旧数组，将所有队列元素复制到新数组的开头。
  4. 更新索引和容量：释放旧数组的内存，更新 data、front、rear 和 capacity 成员。
static bool resize_queue(DynamicQueue *q) {
    int old_capacity = q->capacity;
    int new_capacity = (old_capacity < THRESHOLD) ?
        (old_capacity << 1) :
    (old_capacity + (old_capacity >> 1));

    // 重新分配一个新的,更长的动态数组
    ElementType *new_data = malloc(new_capacity * sizeof(ElementType));
    if (new_data == NULL) {
        printf("error: realloc failed in resize_queue.\n");
        return false;
    }

    int curr = q->front;    // curr索引用于遍历整个队列中的元素
    int index = 0;
    while (index < q->size) {
        new_data[index] = q->data[curr];
        curr = (curr + 1) % q->capacity;
        index++;
    } // while循环结束时,new_data就从头开始包含了队列的所有元素 
    free(q->data);
    q->data = new_data;
    q->front = 0;
    q->rear = q->size;
    q->capacity = new_capacity;
    return true;
}

动态数组队列的入队操作

入队操作是在动态数组队列的尾部添加新元素的过程。

  1. 判满操作：在执行入队之前，首先检查队列是否已满。如果队列已满，尝试进行扩容。
  2. 扩容：如果 resize_queue 函数调用失败，表示扩容失败，入队操作也失败，返回 false。
  3. 添加元素：将新元素添加到 rear 索引所指向的位置。
  4. 更新索引和大小：
    • 更新 rear 索引到下一个位置，并使用取模运算确保索引在数组范围内循环。
    • 增加 size 成员的值，以反映队列中元素数量的增加。
  5. 返回结果：如果元素成功添加到队列，返回 true。
bool enqueue(DynamicQueue *q, ElementType data) {
    if (is_full(q)) {
        if (!resize_queue(q)) {
            printf("error: 扩容失败.\n");
            return false; // 队列扩容失败,入队也同步失败
        }
    }
    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % q->capacity;  // 循环队列
    q->size++;
    return true;
}

动态数组队列的出队操作

出队操作是从动态数组队列的头部移除元素的过程。

  1. 判空操作：在执行出队之前，首先检查队列是否为空。如果队列为空，则无法执行出队操作。
  2. 保存并移除队首元素：保存队首元素的值，然后从队列中移除该元素。
  3. 更新索引和大小：
    • 更新 front 索引到下一个位置，并使用取模运算确保索引在数组范围内循环。
    • 减少 size 成员的值，以反映队列中元素数量的减少。
  4. 返回被移除的元素：返回被出队的元素的值。
ElementType dequeue(DynamicQueue *q) {
    if (is_empty(q)) {
        printf("error: 队列为空，无法出队。\n");
        exit(1);
    }
    ElementType item = q->data[q->front];
    q->front = (q->front + 1) % q->capacity; // 循环队列
    q->size--;
    return item;
}

队列的应用

队列的应用场景广泛，其先进先出（FIFO）的特性使其成为处理顺序任务的理想选择。以下是一些典型的应用实例：

  1. 操作系统的任务调度：在操作系统中，进程或线程按照到达的顺序排队，等待获得 CPU 的执行权，确保任务按照先来先服务的原则进行调度。
  2. 数据处理系统中的缓冲区/缓存机制：例如，标准输入（stdin）和标准输出（stdout）的缓冲区，数据首先被输入到缓冲区，然后按照进入顺序从缓冲区输出。
  3. 打印机的任务管理：面对多个打印任务的并发请求，它们在队列中按提交顺序排列，保证了打印作业的有序执行。
  4. 后端应用系统中的消息队列：在分布式系统中，消息队列用于处理和传递消息，确保消息按照接收顺序被依次处理。
  5. 广度优先搜索（BFS）：在图算法中，如二叉树的层次遍历，队列用于记录待访问的节点，确保按照从上到下的顺序进行搜索。
C数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇