【数据结构】队列、环形队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。

3.队列的相关实现函数与源代码

对其使用的结构体的定义：

typedef  int QDataType;

//用单链表实现队列

// 链式结构：表示队列 
typedef struct QListNode
{
    struct QListNode* next;
    QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
    QNode* front;
    QNode* rear;
}Queue;

通过队头队尾front、rear这两个指针来访问队列，执行队列的基本操作。

3.1初始化队列

// 初始化队列
void QueueInit(Queue* q)
{
    assert(q);
    q->front =q->rear= NULL;
}

3.2 队尾入队列

分两种情况队列为空和队列不为空。

在创建新节点的时候直接把新节点的next初始化为空，后续链接就不用重新把尾结点置为空

QNode* AddNode(QDataType data)
{
    QNode* p = (QNode*)malloc(sizeof(QNode));
    if (p == NULL)
    {
        perror("malloc error\n");
        exit(-1);
    }
    p->data = data;
    p->next = NULL;//直接把新节点的next初始化为空，后续链接就不用重新把尾结点置为空
    return p;
}
//从队尾添加数据
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    //情况1.如果是空队列
    if (q->front == NULL)
    {
        q->front = q->rear = AddNode(data);
    }
    //情况2.队列不为空
    else
    {
        QNode* tail = AddNode(data);
        q->rear->next = tail;
        q->rear = tail;
    }
}

3.3 队头出队列

删除掉队头的数据

请注意如果队列中只有一个元素时，需要进行判断。

释放这个节点之后把指向队列的头尾指针都置为空，否则只是单纯的q->front=q->front->next,q->rear不变的话，就会造成q->rear指向一个已经释放的节点的情况，会造成野指针的问题。

// 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    assert(q->front);

    //如果删除的是最后一个
    if (q->front->next == NULL)
    {
        free(q->front);
        q->front = q->rear = NULL;
    }

    QNode* head = q->front;
    q->front = q->front->next;

    free(head);
    head = NULL;

}

3.4获取队列头部元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(q->front);

    return q->front->data;
}

3.5 获取队列队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(q->front);

    return q->rear->data;
}

3.6 获取队列中有效元素个数

遍历整个队列计算长度。

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    int i = 0;
    QNode* head = q->front;

    while (head)
    {
        i++;
        head = head->next;
    }
    return i;
}

也可以直接在一开始定义的时候直接把结构体改为：

// 队列的结构 
typedef struct Queue
{
    QNode* front;
    QNode* rear;
    int size;
}Queue;

在之后的入队列出队列的时候都进行相应的++或者--

3.7检测队列是否为空

如果为空返回非零结果，如果非空返回0

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->front != NULL;
}

3.8销毁队列

记得销毁队列时，把队列的节点全部释放之后，记得在最后把指向队列的前后指针置为空。

// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    assert(QueueEmpty);
    QNode* head = q->front;
    QNode* next = NULL;
    while (head)
    {
        next = head->next;
        free(head);
        head=next;
    }
    q->front = q->rear = NULL;//销毁队列之后记得把头尾指针置为空
}

4.环形队列

4.1环形队列概念

环形队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

环形队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

环形队列可以使用数组实现，也可以使用循环链表实现。如果使用数组实现，注意数组下标访问越界问题。

以下用数组实现环形队列：

4.2实现环形队列

以力扣622.设计循环队列为例：

1. 设计循环队列 - 力扣（LeetCode）https://leetcode.cn/problems/design-circular-queue/在这个题目中我们一共要实现有关环形队列的七个函数：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

4.2.1.实现环形队列的前期准备：相关结构体

在这个结构体中需要定义指向环形队列起始位置的指针、头尾下标以及申请的实际空间的大小。

typedef int QueueDataType;

typedef struct { 
    QueueDataType* a;//指向队列的指针
    QueueDataType front;//头尾下标
    QueueDataType tail;
    int size;//申请的实际空间大小
} MyCircularQueue;

4.2.2.创建环形队列，设置队列长度为 k

4.2.3. 实现循环队列判空函数和判满函数

4.2.5.插入和删除元素

4.2.6.从队首和队尾获取元素

4.3环形队列完整代码

typedef int QueueDataType;

typedef struct { 
    QueueDataType* a;//指向队列的指针
    QueueDataType front;//头尾下标
    QueueDataType tail;
    int size;//申请的实际空间大小
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* point=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //QueueDataType*
    point->a=(QueueDataType*)malloc(sizeof(QueueDataType)*(k+1));//多申请一个空余空间方便判空和满
    point->front=point->tail=0;//头尾下标都为0
    point->size=k+1;
    return point;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    return obj->tail==obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%obj->size==obj->front;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{

//先判断是否非满
if(myCircularQueueIsFull(obj))
{
    return false;
}

//向tail插入数据然后tail++
obj->a[obj->tail]=value;
//小心tail越界问题
obj->tail++;
obj->tail=obj->tail%obj->size;
return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front=(obj->front+1)%obj->size;
    return true;

}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {
    
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //注意obj->tail始终在队列元素的下一个坐标，所以打印最后一个坐标要--
    return obj->a[(obj->tail-1+obj->size)%obj->size];

}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
    obj=NULL;
}

在最后

   好久不见，这里是媛仔~马上开学了，最近不知道为什么就开始摆烂了，好久也没有更新博客了T-T，把这篇博客当中重新开始吧！！加油加油！！

   希望这篇博客对你能够有所帮助，也希望大家可以和媛仔多多交流，谢谢大家！（最后的这个表情包是媛仔自己做的哦，祝你天天开心 ^-^