您的位置:首页 > 文旅 > 美景 > 【数据结构】线性表----队列详解

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

2024/12/23 5:39:36 来源:https://blog.csdn.net/Skrrapper/article/details/140343886  浏览:    关键词:【数据结构】线性表----队列详解
1. 队列的基本概念

话不多说,直接开始!

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

特点:

  • 先进先出:第一个进入队列的元素最先被处理。
  • 操作受限:元素只能从队尾插入,从队头移除。
2. 队列的实现

在这里插入图片描述

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

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

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

4. 队列的基本操作

队列的基本操作包括入队(Enqueue)出队(Dequeue)查看队头(Peek)检查队列是否为空(IsEmpty)

入队(Enqueue):
将元素添加到队尾。

出队(Dequeue):
移除队头的元素。

查看队头(Peek):
查看队头的元素,但不移除。

检查队列是否为空(IsEmpty):
检查队列中是否有元素。

5. 队列的高级用法

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

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

6.两种形式的队列实现

在这里插入图片描述

入队(Enqueue)

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

数组实现的入队操作:

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;
}

链表实现的入队操作:

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)

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

数组实现的出队操作:

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;
}

链表实现的出队操作:

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)

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

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

int peek(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}return q->items[q->front];
}

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

int peek(Queue* q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}return q->front->data;
}
检查队列是否为空(IsEmpty)

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

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

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

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

int isEmpty(Queue* q) {return q->front == NULL;
}

队列的高级玩法

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

循环队列

在这里插入图片描述

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

循环队列的实现:

#define MAX 100typedef 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. 内存管理: 使用链表实现队列时,需要注意内存管理,确保在出队操作后释放已移除节点的内存,避免内存泄漏。

总结

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com