c语言|《数据结构初阶》实现顺序循环队列和链式队列数据结构|链表|c语言|数据结构

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

文章图片

目录
一、本章重点
二、顺序循环队列
2.1什么是队列？
2.2顺序循环队列
三、链式队列
四、总结

一、本章重点

实现顺序循环队列

实现链式队列

总结

二、顺序循环队列 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语言|《数据结构初阶》实现顺序循环队列和链式队列】实现接口按照自己思路来就好，同时这要确保考虑是全面的。