队列的存储结构和常见操作（c 语言实现）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一、队列（queue）

队列和栈一样，在实际程序的算法设计和计算机一些其他分支里，都有很多重要的应用，比如计算机操作系统对进程 or 作业的优先级调度算法，对离散事件的模拟算法，还有计算机主机和外部设备运行速度不匹配的问题解决等，很多很多。其实队列的本质还是线性表！只不过是一种特殊的或者说是受限的线性表，是这样的：

StartFragment

1）、限定在表的一端插入、另一端删除。插入的那头就是队尾，删除的那头就是队头。也就是说只能在线性表的表头删除元素，在表尾插入元素。形象的说就是水龙头和水管，流水的水嘴是队头，进水的泵是队尾，管子中间不漏水不进水。这样呲呲的流动起来，想想就是这么个过程。

2)、先进先出 (FIFO结构)。显然我们不能在表（队列）的中间操作元素，只能是在尾部进，在头部出去，还可以类似火车进隧道的过程。（first in first out = FIFO 结构）

EndFragment

注意，当队列没有元素的时候，我们就说队列是空队列。

1、双端队列

double-ended queue：限定插入和删除在表的两端进行，也是先进先出 (FIFO)结构，类似铁路的转轨网络。实际程序中应用不多。

这种结构又细分为三类：

1）、输入受限的双端队列：一个端点可插入和删除，另一个端点仅可删除。

2）、输出受限的双端队列：一个端点可插入和删除，另一个端点仅可插入。

3）、等价于两个栈底相连接的栈：限定双端队列从某个端点插入的元素，只能在此端点删除。

2、链队（有链的地方，就有指针）

StartFragment

用链表表示的队列，限制仅在表头删除和表尾插入的单链表。一个链队列由一个头指针和一个尾指针唯一确定。（因为仅有头指针不便于在表尾做插入操作）。为了操作的方便，也给链队列添加一个头结点，因此，空队列的判定条件是：头指针和尾指针都指向头结点。

之前的链式结构，总是使用一个结点的结构来表示链表，其实不太方便，这里使用新的存储结构。定义一个结点结构，和一个队列结构。两个结构嵌套。

 #ifndef queue_Header_h

 #define queue_Header_h

 #include <stdio.h>

 #include <stdlib.h>

 #include <stdbool.h>

 //队列的结点结构

 typedef struct Node{

     int data;

     struct Node *next;

 } Node, *Queue;

 //队列的结构，嵌套

 typedef struct{

     Queue front;

     Queue rear;

 } LinkQueue;

 //初始化

 //开始必然是空队列，队尾指针和队头指针都指向头结点

 void initQueue(LinkQueue *queue)

 {

     //初始化头结点

     queue->front = queue->rear = (Queue)malloc(sizeof(Node));

     if (NULL == queue->front) {

         exit();

     }

     queue->front->next = NULL;

 }

 //判空

 bool isEmpty(LinkQueue queue)

 {

     return queue.rear == queue.front ? true : false;

 }

 //入队,只在一端入队，另一端出队，同样入队不需要判满

 void insertQueue(LinkQueue *queue, int temp)

 {

     Queue q = (Queue)malloc(sizeof(Node));

     if (NULL == q) {

         exit();

     }

     //插入数据

     q->data = temp;

     q->next = NULL;

     //rear 总是指向队尾元素

     queue->rear->next = q;

     queue->rear = q;

 }

 //出队，需要判空

 void deleteQueue(LinkQueue *queue)

 {

     Queue q = NULL;

     if (!isEmpty(*queue)) {

         q = queue->front->next;

         queue->front->next = q->next;

         //这句很关键，不能丢

         if (queue->rear == q) {

             queue->rear = queue->front;

         }

         free(q);

     }

 }

 //遍历

 void traversal(LinkQueue queue)

 {

     int i = ;

     Queue q = queue.front->next;

     while (q != NULL) {

         printf("队列第%d个元素是：%d\n", i, q->data);

         q = q->next;

         i++;

     }

 }

 //销毁

 void destoryQueue(LinkQueue *queue)

 {

     while (queue->front != NULL) {

         queue->rear = queue->front->next;

         free(queue->front);

         queue->front = queue->rear;

     }

     puts("销毁成功！");

 }

 #endif

测试

 #include "queue.h"

 int main(int argc, const char * argv[])

 {

     LinkQueue queue;

     puts("初始化队列 queue");

     initQueue(&queue);

     traversal(queue);

     puts("队尾依次插入0 1 2 3");

     insertQueue(&queue, );

     insertQueue(&queue, );

     insertQueue(&queue, );

     insertQueue(&queue, );

     traversal(queue);

     puts("先进先出，删除队列从头开始， 0 ");

     deleteQueue(&queue);

     traversal(queue);

     puts("先进先出，删除队列从头开始， 1 ");

     deleteQueue(&queue);

     traversal(queue);

     puts("先进先出，删除队列从头开始， 2 ");

     deleteQueue(&queue);

     traversal(queue);

     puts("先进先出，删除队列从头开始， 3");

     deleteQueue(&queue);

     traversal(queue);

     destoryQueue(&queue);

     return ;

 }

结果：

初始化队列 queue

队尾依次插入 0 1 2 3

队列第 1 个元素是： 0

队列第 2 个元素是： 1

队列第 3 个元素是： 2

队列第 4 个元素是： 3

先进先出，删除队列从头开始， 0

队列第 1 个元素是： 1

队列第 2 个元素是： 2

队列第 3 个元素是： 3

先进先出，删除队列从头开始， 1

队列第 1 个元素是： 2

队列第 2 个元素是： 3

先进先出，删除队列从头开始， 2

队列第 1 个元素是： 3

先进先出，删除队列从头开始， 3

销毁成功！

Program ended with exit code: 0

3、顺序队列

StartFragment

限制仅在表头删除和表尾插入的顺序表，利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的，所以也要设头、尾指针。

StartFragment

初始化时的头尾指针，初始值均应置为 0。入队尾指针增 1 ，出队头指针增 1 。头尾指针相等时队列为空，在非空队列里，头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

初始为空队列，那么头尾指针相等。

入队，那么尾指针加1，头指针不变。先进先出，J1先进队，则 rear+1，尾指针始终指向队尾元素的下一位！如，J2进队，rear 继续+1，J3进队，尾指针继续加1，如图

出队，则尾指针不变，头指针加1，注意这里都是加1，先进先出原则，J1先删除，front+1，指向了 J2，J2删除，front+1指向了 J3，如图

最后，J3删除，则头指针再次和尾指针相等，说明队列空了。如图

在顺序队列中，当尾指针已经指向了队列的最后一个位置的下一位置时，若再有元素入队，就会发生“溢出”。如图位置，再次入队，就会溢出。

4、循环队列的诞生

顺序队列的 “假溢出” 问题：队列的存储空间未满，却发生了溢出。很好理解，比如 rear 现在虽然指向了最后一个位置的下一位置，但是之前队头也删除了一些元素，那么队头指针经历若干次的 +1 之后，遗留下了很多空位置，但是顺序队列还在傻乎乎的以为再有元素入队，就溢出呢！肯定不合理。故循环队列诞生！

解决“假溢出”的问题有两种可行的方法：

(1)、平移元素：把元素平移到队列的首部。效率低。否决了。

(2)、将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。操作效率高、空间利用率高。

虽然使用循环队列，解决了假溢出问题，但是又有新问题发生——判空的问题，因为仅凭 front = rear 不能判定循环队列是空还是满。比如如图：

这是空循环队列的样子

这是满循环队列的样子

解决办法：

(1)、另设一个布尔变量以区别队列的空和满；

(2)、少用一个元素的空间，约定入队前测试尾指针在循环下加 1 后是否等于头指针，若相等则认为队满；（最常用）

(3)、使用一个计数器记录队列中元素的总数。

对于第2个方案，必须牺牲一个元素的空间，那么入队的时候需要测试，循环意义下的加 1 操作可以描述为：

     if (rear +  = MAXQSIZE)

            rear = ;

      else

           rear ++;

StartFragment

利用模运算可简化为：

EndFragment

 rear = (rear + )% MAXQSIZE

基本操作

 #ifndef ___queue_Header_h

 #define ___queue_Header_h

 #include <stdio.h>

 #include <stdlib.h>

 #define MAX_SIZE 5

 typedef struct{

     int *base;

     int rear;//如果队列不空，指向队尾元素的下一个位置

     int front;//初始的时候指向表头

 } CirularQueue;

 //初始化

 void initQueue(CirularQueue *queue)

 {

     queue->base = (int *)malloc(MAX_SIZE*sizeof(int));

     if (NULL == queue->base) {

         exit();

     }

     queue->front = queue->rear = ;

 }

求长度

//求长度

int getLength(CirularQueue queue)

{

    //这样把所以的情况都考虑到了

    return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE;

}

第一种情况，长度的求法

第二种情况，长度的求法，利用模运算，两个情况合二为一！

//入队，先判满

void insertQueue(CirularQueue *queue, int e)

{

    if ((queue->rear + ) % MAX_SIZE == queue->front) {

        puts("循环队列是满的！");

    }

    else

    {

        queue->base[queue->rear] = e;

        queue->rear = (queue->rear + ) % MAX_SIZE;

    }

}

如下时为满，损失一个空间，不存储元素。方便判满

 //出队

 void deleteQueue(CirularQueue *queue)

 {

     if (queue->front == queue->rear) {

         puts("队列是空的！");

     }

     else

     {

         queue->front = (queue->front + ) % MAX_SIZE;

     }

 }

 //遍历

 void traversal(CirularQueue queue)

 {

     int q = queue.front;

     for (int i = ; i < getLength(queue); i++) {

         printf("循环队列的第%d个元素为%d\n", i + , queue.base[q]);

         q++;

     }

 }

 #endif

测试

 #include "Header.h"

 int main(int argc, const char * argv[]) {

     CirularQueue queue;

     puts("循环队列初始化：");

     initQueue(&queue);

     puts("循环队列初始化后长度：");

     printf("%d\n", getLength(queue));

     puts("循环队列5个元素入队，总长度为5，但是损失一个位置空间，实际存储4个元素。先进先出原则：");

     puts("循环队列元素0入队");

     insertQueue(&queue, );

     puts("循环队列元素1入队");

     insertQueue(&queue, );

     puts("循环队列元素2入队");

     insertQueue(&queue, );

     puts("循环队列元素3入队");

     insertQueue(&queue, );

     puts("循环队列元素遍历：");

     traversal(queue);

     puts("循环队列元素继续入队，无法完成：");

     insertQueue(&queue, );

     puts("循环队列元素0出队之后，先进先出原则：");

     deleteQueue(&queue);

     traversal(queue);

     puts("循环队列元素1出队之后，先进先出原则：");

     deleteQueue(&queue);

     traversal(queue);

     puts("循环队列元素2出队之后，先进先出原则：");

     deleteQueue(&queue);

     traversal(queue);

     puts("循环队列元素3出队之后，先进先出原则：");

     deleteQueue(&queue);

     traversal(queue);

     puts("4个元素全部删除，循环队列已经空了：");

     deleteQueue(&queue);

     traversal(queue);

     return ;

 }

结果；

循环队列初始化：

循环队列初始化后长度：

循环队列 5 个元素入队，总长度为 5 ，但是损失一个位置空间，实际存储 4 个元素。先进先出原则：

循环队列元素 0 入队

循环队列元素 1 入队

循环队列元素 2 入队

循环队列元素 3 入队

循环队列元素遍历：

循环队列的第 1 个元素为 0

循环队列的第 2 个元素为 1

循环队列的第 3 个元素为 2

循环队列的第 4 个元素为 3

循环队列元素继续入队，无法完成：

循环队列是满的！

循环队列元素 0 出队之后，先进先出原则：

循环队列的第 1 个元素为 1

循环队列的第 2 个元素为 2

循环队列的第 3 个元素为 3

循环队列元素 1 出队之后，先进先出原则：

循环队列的第 1 个元素为 2

循环队列的第 2 个元素为 3

循环队列元素 2 出队之后，先进先出原则：

循环队列的第 1 个元素为 3

循环队列元素 3 出队之后，先进先出原则：

4 个元素全部删除，循环队列已经空了：

队列是空的！

Program ended with exit code: 0

小结：

若用户需要循环队列，那么要设置队列的最大长度，否则无法完成判断空，如果用户不知道最大长度是多少，那么应该使用链队。队列在程序设计中和栈一样，应用很多，未完待续。

EndFragment

欢迎关注

dashuai的博客是终身学习践行者，大厂程序员，且专注于工作经验、学习笔记的分享和日常吐槽，包括但不限于互联网行业，附带分享一些PDF电子书，资料，帮忙内推，欢迎拍砖！

正文

欢迎关注

相关阅读

go语言char，go语言常见面试题

java中常见的设计模式，java中常见的设计模式有哪些

mysql查询常见错误，mysqljoin查询

html5交互式图像，html5中常见的交互标签有哪些

面试python爬虫实习，爬虫常见面试题

redis分布式保持数据一致性，redis分布式存储的2种常见方案

嵌入式最常见架构设计，嵌入式架构有哪些

go语言常见编码问题，go语言的编译器

目录[+]