【数据结构】线性表----队列详解

2024-08-05 09:50:34 浏览数 (2)
1. 队列的基本概念

话不多说，直接开始！

队列是一种线性数据结构，同栈类似但又不同，遵循先进先出（FIFO, First In First Out）的原则。换句话说，最先进入队列的元素会最先被移除。这样的特点使得队列非常适合用于需要按顺序处理任务的场景。

在这里插入图片描述在这里插入图片描述

特点：

  • 先进先出：第一个进入队列的元素最先被处理。
  • 操作受限：元素只能从队尾插入，从队头移除。
2. 队列的实现
在这里插入图片描述在这里插入图片描述

队列可以通过多种方式实现，常见的有数组和链表两种。

使用数组实现队列： 使用数组实现队列需要维护两个指针，分别指向队头和队尾，并且需要处理数组的溢出问题。所以数组不是很适合用来实现队列。

使用链表实现队列： 链表不会受到同数组一样的困扰，并且链表实现的队列没有数组的大小限制；但需要额外的指针来管理链表的节点。

4. 队列的基本操作

队列的基本操作包括入队（Enqueue）、出队（Dequeue）、查看队头（Peek）和检查队列是否为空（IsEmpty）。

入队（Enqueue）： 将元素添加到队尾。

出队（Dequeue）： 移除队头的元素。

查看队头（Peek）： 查看队头的元素，但不移除。

检查队列是否为空（IsEmpty）： 检查队列中是否有元素。

5. 队列的高级用法

循环队列： 循环队列是一种优化的队列实现，避免了数组实现中由于出队操作造成的空间浪费。

优先队列： 优先队列中的元素具有优先级，出队时优先级高的元素会被优先移除。

6.两种形式的队列实现
在这里插入图片描述在这里插入图片描述
入队（Enqueue）

将元素添加到队尾。如果使用数组实现，需要检查队列是否已满。如果使用链表实现，只需将新节点添加到链表的末尾。

数组实现的入队操作：

代码语言：javascript复制
void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear  ;
    q->items[q->rear] = value;
}

链表实现的入队操作：

代码语言：javascript复制
void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = newNode;
    } else {
        q->rear->next = newNode;
    }
    q->rear = newNode;
}
出队（Dequeue）

移除队头的元素。如果使用数组实现，需要检查队列是否为空，并调整队头指针。如果使用链表实现，需要移除链表的第一个节点。

数组实现的出队操作：

代码语言：javascript复制
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!n");
        return -1;
    }
    int item = q->items[q->front];
    q->front  ;
    if (q->front > q->rear) {
        initQueue(q);
    }
    return item;
}

链表实现的出队操作：

代码语言：javascript复制
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!n");
        return -1;
    }
    int item = q->front->data;
    Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return item;
}
查看队头（Peek）

查看队头的元素，但不移除。如果队列为空，应返回特定的错误值或抛出异常。

数组实现的查看队头操作：

代码语言：javascript复制
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!n");
        return -1;
    }
    return q->items[q->front];
}

链表实现的查看队头操作：

代码语言：javascript复制
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!n");
        return -1;
    }
    return q->front->data;
}
检查队列是否为空（IsEmpty）

检查队列中是否有元素。这是一个常用的辅助操作，用于确保其他操作的前提条件。

数组实现的检查是否为空操作：

代码语言：javascript复制
int isEmpty(Queue* q) {
    return q->front == -1;
}

链表实现的检查是否为空操作：

代码语言：javascript复制
int isEmpty(Queue* q) {
    return q->front == NULL;
}
队列的高级玩法

除了基本操作外，队列还有一些高级用法，如循环队列和优先队列。

循环队列
在这里插入图片描述在这里插入图片描述

循环队列是一种优化的队列实现，避免了数组实现中由于出队操作造成的空间浪费。循环队列通过将队尾连接到队头，使得数组能够循环使用。

循环队列的实现：

代码语言：javascript复制
#define MAX 100

typedef struct {
    int items[MAX];
    int front, rear;
} CircularQueue;

void initQueue(CircularQueue* q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(CircularQueue* q) {
    return q->front == -1;
}

int isFull(CircularQueue* q) {
    return (q->rear   1) % MAX == q->front;
}

void enqueue(CircularQueue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear   1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initQueue(q);
    } else {
        q->front = (q->front   1) % MAX;
    }
    return item;
}
优先队列

优先队列中的元素具有优先级，出队时优先级高的元素会被优先移除。优先队列可以使用**堆（Heap）**来实现，能够高效地进行插入和删除操作。 而堆我们将会在下一章进行讲解。

队列在实际中的应用

队列在许多实际应用中扮演重要角色，以下是几个常见的例子：

操作系统中的任务调度

操作系统使用队列管理任务的执行顺序。任务调度器将所有待处理的任务放入队列中，并按顺序调度这些任务。

打印队列

打印机使用队列管理打印任务，确保按顺序打印。

广度优先搜索（BFS）

在图的遍历中，BFS使用队列管理待访问的节点。BFS是一种图的遍历算法，它从根节点开始，先访问所有相邻节点，再按层次访问更深的节点。

使用队列时需要注意的问题
  1. 空间复杂度： 数组实现的队列在入队和出队操作后可能会导致空间浪费，使用循环队列可以解决这个问题。
  2. 时间复杂度： 队列的基本操作时间复杂度通常为O(1)，但优先队列的插入和删除操作可能会更耗时，具体取决于实现方式。
  3. 内存管理： 使用链表实现队列时，需要注意内存管理，确保在出队操作后释放已移除节点的内存，避免内存泄漏。
总结

队列作为一种重要的数据结构，具有简单但实用的特性。在本文中，我们介绍了队列的基本概念、实现方法、常见操作、实际应用以及使用时需要注意的问题。通过实践代码示例，相信读者能更好地理解和掌握队列的使用。队列在编程中的应用广泛，相信掌握了它将为你的编程技能打下坚实的基础。

数组 数据结构 队列 管理 链表

0 人点赞