📝队列的概念及结构
- 队列的概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
- 队列特征如下:
入队(Enqueue):通过尾指针添加元素到队列尾部,即向队列中插入元素。
出队(Dequeue):通过头指针删除队列头部元素,即从队列中移除元素。
空队列:当头指针和尾指针相同时,表示队列为空。
满队列:当尾指针指向队列容量最大位置时,表示队列已满。
- 常用的队列结构包括数组和链表实现:
数组实现队列:使用一维数组存储元素,头指针和尾指针分别指向数组的下标位置。
链表实现队列:每个元素使用一个节点存储,头节点和尾节点通过指针链接实现队列。
🌠 队列的顺序实现
头文件：Queue_order.h
# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int QDataType;
typedef struct Queue
{
QDataType data[MAX_SIZE];
int front;
int rear;
int size;//记录队列中元素数量
}Queue;
//初始化队列
void InitQueue(Queue* pq);
//入队操作
void EnQueue(Queue* pq,int value);
//出队
QDataType DeQueue(Queue* pq);
//获取队首元素
QDataType FrontQueue(Queue* pq);
//获取队尾元素
QDataType RearQueue(Queue* pq);
//获取队列中有效元素个数
QDataType SizeQueue(Queue* pq);
//队列是否为空
QDataType IsEmpty(Queue* pq);
//队列是否为满
QDataType IsFull(Queue* pq);
//销毁队列
void DestroyQueue(Queue* pq);
🌉初始化
//初始化队列
void InitQueue(Queue* pq)
{
pq->front = -1;
pq->rear = -1;
pq->size = 0;
}
front和rear都指向-1,表示队列中没有数据。size为0,表示队列中没有元素。
🌠入队
//入队
void EnQueue(Queue* pq, int value)
{
if (pq->front == MAX_SIZE - 1)
{
printf("队列满了，入队操作失败");//检查队列是否已满,如果front指针指向的下一个位置就是MAX_SIZE-1,表示队列已满,打印错误信息并返回。
return;
}
if (pq->front == -1)
{//如果front为-1,表示队列为空,将front指针置0。
pq->front = 0;
}
pq->rear++;//如果front为-1
pq->data[pq->rear] = value;//表示队列为空
pq->size++;//加完了别忘了size++
}
🌉出队
//出队
QDataType DeQueue(Queue* pq)
{
if (-1 == IsEmpty)
{
printf("队列为空！");
return -1;//返回一个特定的值表示队列为空
}
int value = pq->data[pq->front];
pq->front++;
pq->size--;
return value;
}
检查满是为了防止入队越界,front为-1时,表示队列为空,需要将front置0,rear后移一位指向新的元素位置，将元素值写入data数组，size计数增加。
🌠获取队列首元素
//获取队首元素
QDataType FrontQueue(Queue* pq)
{
if (-1 == IsEmpty)
{
printf("队列为空！");
return -1;//返回一个特定的值表示队列为空
}
return pq->data[pq->front];
}
🌉获取队列尾部元素
//获取队列尾部元素
QDataType RearQueue(Queue* pq)
{
if (0 == IsEmpty)
{
printf("队列为空！");
return -1;//返回一个特定的值表示队列为空
}
return pq->data[pq->rear];
}
🌠获取队列中有效元素个数
//获取队列中有效元素个数
QDataType SizeQueue(Queue* pq)
{
return pq->size;
}
🌉 队列是否为空
//队列是否为空
QDataType IsEmpty(Queue* pq)
{
if (pq->front == -1 || (pq->front > pq->rear))
{
//队列为空
return -1;
}
else
{
//队列不为空
return 1;
}
}
注意：在队列中，如果 front 指针大于 rear 指针，表示队列为空。这是因为 front 指针指向队列的第一个元素，而 rear 指针指向队列的最后一个元素。如果 front 指针大于 rear 指针，意味着队列中没有元素，或者已经出队了所有的元素。
考虑一个队列中有一个元素的情况。初始时 front 和 rear 都指向该元素，而当该元素出队时，front 指针会被移动到下一个位置，这时 front 指针就比 rear 指针大，表示队列已经为空。
🌠查看队列是否为满
//查看队列是否为满
QDataType IsFull(Queue* pq)
{
return (pq->rear == MAX_SIZE - 1);
}
🌉销毁队列
//销毁队列
void DestroyQueue(Queue* pq)
{
InitQueue(pq);//重新初始化队列，清空元素并释放内存
}
🌠测试
源文件Test.c
# define _CRT_SECURE_NO_WARNINGS 1
#include"Queue_order.h"
int main()
{
Queue Pq;
InitQueue(&Pq);
EnQueue(&Pq, 10);
EnQueue(&Pq, 20);
EnQueue(&Pq, 30);
printf("Front element: %d\n", FrontQueue(&Pq));
printf("Rear element: %d\n", RearQueue(&Pq));
printf("Front element: %d\n", SizeQueue(&Pq));
printf("Front element: %d\n", FrontQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq));
printf("Dequeued element: %d\n", DeQueue(&Pq)); // 尝试从空队列中出队
printf("Queue size: %d\n", SizeQueue(&Pq));
printf("Is queue empty? %s\n", IsEmpty(&Pq) ? "Yes" : "No");
}
🌉 顺序队列的假溢出
顺序队列的假溢出指的是，队列在结构上没有真正满溢，但是在逻辑上已经无法再插入新元素了。
在队尾指针已经指向数组的最后一个位置，但数组中仍然有空闲空间时，确实是队列溢出的情况，而不是假溢出。这种情况通常是由于没有充分利用队列所分配的存储空间所导致的，因此会造成队列操作的限制。
“假溢出” 通常用于表示队列中还有空闲空间，但因某种原因无法继续插入元素的情况，这可能是由于某些限制条件或错误的队列操作所导致的。例如，可能存在对队列的错误管理，使得无法正确地判断队列是否已满，导致了插入元素失败的情况。
举个例子：
在一个顺序队列中，队列大小为5，已包含四个元素 value1-2-3-4，rear在队尾4的位置。
当出队两个元素value1-2时，队列前面多出来了两位置
当你想再插入来两个数据时，队列确只能插入一个数据，但是队列其实不能插入数据了。
这是队列在结构上没有真正满溢,但是在逻辑上已经无法再插入新元素了。
怎么优化这个假溢出呢？两种常见的方法：
- 循环队列: 循环队列是一种特殊的顺序队列，通过将队列的数组视为一个循环的环形结构，使得在队列尾部插入元素时可以利用数组头部的空闲空间，从而解决了假溢出的问题。循环队列中，当队尾指针指向数组的末尾时，再插入元素时将其指向数组的起始位置，这样就形成了一个循环。通过这种方式，可以充分利用数组空间，避免了假溢出。
- 动态扩容: 动态扩容是在顺序队列满时，自动增加数组的大小以容纳更多元素。当队列满时，分配一个更大的数组，并将原有的元素复制到新数组中，然后释放原来的数组。这样可以确保队列始终有足够的空间来插入新的元素，从而避免假溢出。动态扩容的关键是选择适当的扩容策略，以及控制扩容时机，以避免频繁的扩容操作带来的性能开销。
🌠循环队列概念
循环队列是一种基于数组实现的队列数据结构，其特点是通过循环利用数组空间来实现队列的操作。循环队列的数组通常被看作一个环形的结构，队列的头部和尾部指针在数组中循环移动，使得当尾部指针到达数组末尾时，可以将其“循环”到数组的起始位置，从而避免了溢出或假溢出的情况。
循环队列看似循环，其实是固定数组不断往复的过程，我们可以模拟普通数组来实现：
如图：data 表示一个数据域，int 为类型，当然你也可以修改为任意自定义的类型，也可以是复杂的结构体类型。
MAX_SIZE ：表示循环最大容量，可进行放数据的操作空间
rear代表尾指针，入队时移动。
front代表头指针，出队时移动。
size记录当前有效数据的多少
代码：
#define MAX_SIZE 5
typedef struct {
int data[MAX_SIZE];
int front; // 队列头指针
int rear; // 队列尾指针
int size; // 队列当前元素个数
} Cir_Queue;
🌉循环队列的初始化
对于循环队列来说,front从0开始是合理的,因为数据数组是环状结构,front从0开始可以实现队列元素的循环利用。
rear从0开始表示队列此时为空,front和rear指针都指向数组第一个位置。
将队列当前元素个数size清零,表示队列为空。
// 初始化队列
void initQueue(Cir_Queue* queue)
{
queue->front = 0;将队列头指针front设置为0。
queue->rear = 0;将队列尾指针rear也设置为0。
queue->size = 0;
}
🌠循环队列的入队操作
入队操作与顺序队列相同，只需将rear向后移动。但要注意，如果rear达到队列的上限，需从头开始移动。建议使用余数法，确保操作在队列空间内进行，避免一次错误导致整体崩溃。
要进行入队操作，得先判断队列是不是满了rear==front来判断队空，也可以用size。
// 入队操作
void enqueue(Cir_Queue* queue, int value)
{
if (queue->size == MAX_SIZE)
{
printf("Queue is full. Enqueue operation failed.\n");
return;
}
queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % MAX_SIZE; // 使用(rear+1)%MAX_SIZE更新rear指针，循环移动
queue->size++;
}
检查队列是否已满，可通过判断size是否等于MAX_SIZE来确定。如果已满，则打印提示信息并返回；将数值value赋给data数组的rear索引位置，并使用(rear+1)%MAX_SIZE更新rear指针。这里使用模运算来实现rear指针的循环移动。当rear指向最后一个位置时，利用模运算使其指向第一个位置，实现循环利用数组。然后将size增加1，表示元素个数加1。
🌉 循环队列的出队操作
// 出队操作
int dequeue(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Dequeue operation failed.\n");
return -1;
}
int value = queue->data[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE; // 循环移动
queue->size--;
return value;
}
使用(front+1)%MAX_SIZE更新front指针，这里也使用模运算实现front指针的循环移动。当front指向最后一个位置时,利用模运算让它指向第一个位置。
🌉 查看队首元素
// 查看队首元素
int front(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Front operation failed.\n");
return -1;
}
return queue->data[queue->front];
}
🌠查看队尾元素
// 查看队尾元素
int rear(Cir_Queue* queue)
{
if (queue->size == 0)
{
printf("Queue is empty. Rear operation failed.\n");
return -1;
}
return queue->data[(queue->rear - 1 + MAX_SIZE) % MAX_SIZE];
}
🌉查看队列是否为空
// 查看队列是否为空
int isEmpty(Cir_Queue* queue)
{
return (queue->size == 0);
}
🌠查看队列是否已满
// 查看队列是否已满
int isFull(Cir_Queue* queue)
{
return (queue->size == MAX_SIZE);
}
🌉 测试下循环队列
int main() {
Cir_Queue queue;
initQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
printf("Front element: %d\n", front(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
enqueue(&queue, 80);
enqueue(&queue, 90);
printf("Front element: %d\n", front(&queue));
printf("rear element: %d\n", rear(&queue));
return 0;
}
🚩总结
感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘文章来源：https://www.toymoban.com/news/detail-850328.html
文章来源地址https://www.toymoban.com/news/detail-850328.html
到了这里，关于【算法与数据结构】队列的实现详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
