📝队列的概念及结构
1.队列的概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出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时，队列前面多出来了两位置
当你想再插入来两个数据时，队列确只能插入一个数据，但是队列其实不能插入数据了。
这是队列在结构上没有真正满溢,但是在逻辑上已经无法再插入新元素了。
怎么优化这个假溢出呢？两种常见的方法：
1.循环队列: 循环队列是一种特殊的顺序队列，通过将队列的数组视为一个循环的环形结构，使得在队列尾部插入元素时可以利用数组头部的空闲空间，从而解决了假溢出的问题。循环队列中，当队尾指针指向数组的末尾时，再插入元素时将其指向数组的起始位置，这样就形成了一个循环。通过这种方式，可以充分利用数组空间，避免了假溢出。
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; }
🚩总结
感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘
