【算法与数据结构】队列的实现详解

---

📝队列的概念及结构

1. 队列的概念：
   队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。
   入队列：进行插入操作的一端称为队尾
   出队列：进行删除操作的一端称为队头
   
2. 队列特征如下:

入队(Enqueue):通过尾指针添加元素到队列尾部,即向队列中插入元素。

出队(Dequeue):通过头指针删除队列头部元素,即从队列中移除元素。

空队列:当头指针和尾指针相同时,表示队列为空。

满队列:当尾指针指向队列容量最大位置时,表示队列已满。

3. 常用的队列结构包括数组和链表实现:

数组实现队列:使用一维数组存储元素,头指针和尾指针分别指向数组的下标位置。

链表实现队列:每个元素使用一个节点存储,头节点和尾节点通过指针链接实现队列。

🌠 队列的顺序实现

头文件：Queue_order.h

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef 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为-1pq->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 5typedef 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;
}

---

🚩总结

感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘