《数据结构初阶》实现顺序循环队列和链式队列

鸿鹄高飞云霄外,剑映豪气贯长虹

一、🌱本章重点

实现顺序循环队列

实现链式队列

总结

二、🌱顺序循环队列

2.1💯什么是队列？

💦队列：一种特殊的线性表，只允许一端进行插入，另一段进行删除。

💦实现队列的方式有多种：静态数组、动态数组、单链表、双链表。

以静态数组实现顺序队列为例。

💦与动态数组相比：静态数组不能增容，而动态数组在空间不够时，可以自动增容。

💦静态数组实现顺序队列：可以采取头删和尾插的方式，该方式：出队列：头删。入队列：尾插。

💦头删：int head记录头的下标，起初为0，如果要出队列，则head++即可。

💦尾插：int tail记录最后元素的下一个下标，初始为0，即代表整个队列元素的个数。

该方式实现队列的结构体为：
#define MAXSIZE 10
typedef int SQDataType;
typedef struct SequenceQueue
{
    SQDataType data[MAXSIZE];
    int head;
    int tail;
}SeqQueue;
尾插视图：

头删视图：

当我们以这这方式删除的时候：当tail==MAXSIZE队列就满了，但前面删除空出来的空间就不好使用了，这种状态我们称之为假溢出。

为了解决假溢出的问题，我们可以这样做，当tail==MAXSIZE时，我们可以把tail置为0，或者对它进行取模操作（tail%=MAXSIZE）。这种方式类似于一个环，因此被叫做顺序循环队列。

2.2💯顺序循环队列

顺序循环队列与顺序队列差不多，只是多了这一步：要完全利用前面删除数据空出来的空间

队列的结构体是一样的
#define MAXSIZE 10
typedef int SQDataType;
typedef struct SequenceQueue
{
    SQDataType data[MAXSIZE];
    int head;
    int tail;
}SeqQueue;
🎲接口1：循环队列初始化函数
void CQueueInit(CQ* p);
初始状态：head==tail=0；

参考代码：
void CQueueInit(CQ* p)
{
    assert(p);
    p->head = p->tail = 0;
}
🎲接口2：实现队列是否为空函数
SeqQueueEmpty(SeqQueue* sqp)
队列为空有两种情况：

第一种：未插入任何数据。

第二种：插入了一些数据，最后都删除了，导致队列为空。

参考代码：
bool SeqQueueEmpty(SeqQueue* sqp)
{
    return sqp->head == sqp->tail
}
🎲接口3：实现队列是否满的函数
bool SeqQueueFull(SeqQueue* seq)
怎么判断队列满呢？

第一种：没有删数据一直入数据满了。

如果在放一个数据，那么tail==head，那么这个判断条件到底是满还是空呢？

为了解决这一判断条件相同的问题，我们就想到了浪费最后一个空间的思路。

因此空间满的判断条件是 ((p->tail+1) % MAXSIZE) == p->head % MAXSIZE。

参考代码：
bool CQueueFull(CQ* p)
{
    assert(p);
    return ((p->tail+1) % MAXSIZE) == p->head % MAXSIZE;
}
🎲接口4：循环队列插入函数
bool CQueuePush(CQ* p, CQDataType x);
首先p不能为空，要assert断言一下。

然后判断该队列是否满了，如果满了则返回false。

最后插入x，由于tail记录的是下一个要插入位置的下标，但一直插入x，tail会一直增大，因此要对tail取模。

所以插入操作为：
p->data[p->tail % MAXSIZE] = x;
p->tail++;
参考代码：
bool CQueuePush(CQ* p, CQDataType x)
{
    assert(p);
    if (CQueueFull(p))
    {
        return false;
    }
    p->data[p->tail % MAXSIZE] = x;
    p->tail++;
    return true;
}
🎲接口5：删除头部的数据，即出队列。
bool CQueuePop(CQ* p);
出队列好办，直接p->head++；即可。

但在之前要判断队列是否为空，为空就不能出队列了，返回false。

同时也要判断p不能为NULL。

因为你不能防止别人这样调用函数：CQueuePop（NULL）；

参考代码：
bool CQueuePop(CQ* p)
{
    assert(p);
    if (CQueueEmpty(p))
    {
        return false;
    }
    p->head++;
    return true;
}
🎲接口6：取对头数据的函数
CQDataType CQueueFront(CQ* p);
取对头数据也好办，p->[p->head]即可，要不要取模呢？

答案是要，因为可能在此之前，插入了很多数据，也删除了很多数据。head是有可能大于MAXSIZE-1的，因此要进行取模。

同样的要判断p不为空并且队列也不为空。

参考代码：
CQDataType CQueueFront(CQ* p)
{
    assert(p);
    if (CQueueEmpty(p))
    {
        return -1;
    }
    return p->data[p->head % MAXSIZE];
}
🎲接口7：取对尾数据的函数
CQDataType CQueueRear(CQ* p);
同理，要先保证p不能为空，同时队列不为空。

由于tail%MAXSZIE代表的是下一个元素的下标。队尾数据可以这样取吗？

p-data[tail%MAXSIZE-1]

但如果tail==8时，tail%MAXSIZE==0，那么你取的就是p->data[-1]了，这显然不对。

换种方式:p->data[(tail-1)%MAXSZIE]

所以队尾数据为p->data[(tail-1)%MAXSZIE]

参考代码：
CQDataType CQueueRear(CQ* p)
{
    assert(p);
    if (CQueueEmpty(p))
    {
        return -1;
    }
    return p->data[(p->tail - 1) % MAXSIZE];
}
🎲接口8：计算循环队列元素个数
size_t CQueueSize(CQ* p);
如何计算循环队列的元素个数？

让我们先从简单情况计算。

情况1：只插入数据，不删除数据。

如图连续插入7个数据。

元素个数为tail-head。

情况2：插入了7个数据，删除了3个数据

此时tail=7，head=2。

元素个数为：tail-head。

情况3：先插入7个数据，删除3个，再插入2个数据。

此时tail=7+2=9，head=3

元素个数为：6

可以写成：tail-head

因此：我们可以总结循环队列的元素个数为tail-head。

参考代码：
size_t CQueueSize(CQ* p)
{
    return p->tail - p->head;
}
🎲接口9：打印循环队列元素
void CQueuePrint(CQ* p);
先调用求队列元素的接口求出要打印的元素个数，然后一个for循环语句解决。

参考代码：
void CQueuePrint(CQ* p)
{
    int i = 0;
    int n = CQueueSize(p);
    for (i = 0; i < n; i++)
    {
        printf("%d ", CQueueFront(p));
        CQueuePop(p);
    }
    printf("\n");
}
🎲接口10：destroy循环队列函数
void CQueueFree(CQ* p)
参考代码：
void CQueueFree(CQ* p)
{
    assert(p);
    p->head = p->tail = 0;
}

三、🌱链式队列

💦链式队列：单链表实现的链式队列

为了方便我们实现先进先出，出队：头删，入队：尾插。

💦单链表头删：用head记录头节点的地址，管理队列的头。

💦单链表尾插：需要不断的找尾，为了方便我们可以用tail节点指针记录尾部节点的地址，管理队列的尾。

因此结构体为：
typedef int QTypeData;
typedef struct QueueNode
{
    struct QueueNode* next;
    QTypeData val;
}QN;

typedef struct Queue
{
    QN* head;
    QN* tail;
}Queue;
我们要实现的接口：
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QTypeData x);
void QueuePop(Queue* pq);
QN* QueueBack(Queue* pq);
QN* QueueFront(Queue* pq);
size_t QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
🎲接口1：队列初始化接口
void QueueInit(Queue* pq);
队列头指针和尾指针指向NULL。

参考代码：
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}
🎲接口2：Destroy队列接口
void QueueDestroy(Queue* pq);
链表节点的回收：用一个while循环。

并将head和tail置为空。

参考代码：
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QN* cur = pq->head;
    while (cur)
    {
        QN* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}
🎲接口3：入队列，即尾插
void QueuePush(Queue* pq, QTypeData x);
malloc一个新节点
QN* newnode = (QN*)malloc(sizeof(QN));
    assert(newnode);
    newnode->next = NULL;
    newnode->val = x;
然后尾插至head和tail管理的队列。

尾插有两种情况：

第一种：一个节点都没的情况，即head==tail==NULL
if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
第二种：队列有一个以上的节点。
else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
参考代码：
void QueuePush(Queue* pq, QTypeData x)
{
    assert(pq);
    QN* newnode = (QN*)malloc(sizeof(QN));
    assert(newnode);
    newnode->next = NULL;
    newnode->val = x;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}
🎲接口4：出队列，即头删
void QueuePop(Queue* pq);
1.要保证pq不为空

assert(pq)

2.要保证队列不为空

assert(tail)

4.删除2个及2个以上的节点

node* temp=head。

head=head->next

free（temp）

3.删除一个节点

这样删除行吗？

node* temp=head。

head=head->next

free（temp）

如果这样删除的话，tail会变成野指针，有安全隐患。

因此可以分情况判断

参考代码：
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    QN* next = pq->head->next;
    if (next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        free(pq->head);
        pq->head = next;
    }
}
🎲接口5：取队尾数据
QN* QueueBack(Queue* pq)
先要保证pq和队列不为空

队尾数据：pq->tail

参考代码：
QN* QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    return pq->tail;
}
🎲接口6：取对头数据
QN* QueueFront(Queue* pq)
与取队尾数据一样，先要保证pq和队列不为空。
QN* QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head;
}
🎲接口7：求队列元素个数的接口
size_t QueueSize(Queue* pq);
遍历一遍链表，也可在head和tail的队列结构体多加一个size计数器，在push时，size++。在pop时，size--。

参考代码：
size_t QueueSize(Queue* pq)
{
    assert(pq);
    QN* cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
🎲接口8：判断队列为空接口
bool QueueEmpty(Queue* pq);
参考代码：
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->tail==NULL && pq->head==NULL;
}
这里也可为
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->tail==NULL;
}

四、总结

由于循环队列有多种实现方式：如数组、单链表、双链表。

并且接口的实现也可能是不一样的，但效果是一样的。

有的push或者pop数据之后，函数会把rear或者front进行取模重赋值，让front和rear对应队列头和队列尾下标。不取模重赋值也是完全可以的。

实现接口按照自己思路来就好，同时这要确保考虑是全面的。

标签：数据结构链表 c语言

本文转载自: https://blog.csdn.net/m0_62171658/article/details/123769128
版权归原作者 李逢溪 所有，如有侵权，请联系我们删除。

《数据结构初阶》实现顺序循环队列和链式队列

鸿鹄高飞云霄外,剑映豪气贯长虹

一、🌱本章重点

二、🌱顺序循环队列

2.1💯什么是队列？

2.2💯顺序循环队列

三、🌱链式队列

四、总结

发表评论

“《数据结构初阶》实现顺序循环队列和链式队列”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航