队列是个很常见的数据结构,我来简单介绍一下。从链队列入手,之后再介绍顺序队列,环形队列,双端队列等。全程用C语言描述,并养成画逻辑图的好习惯。
我先引用头文件,定义宏。后续有开空间的操作要引用 stdlib.h,宏可以增强代码的可读性。
#include<stdio.h> #include<stdlib.h> #define OK 0 #define ERR -1
队列是一种先进先出的数据结构。栈是一个桶,我们把序号为 1、2、3 的节点依次放进桶里保存,取节点时从最外面的 3 开始取;而队列是一个通道,如果将 1、2、3 节点依次存在队列中,取数据时就要到通道的另一侧,从 1 开始取。
队列节点的结构如下:
/* 队列节点结构 */ typedef struct QNode { //队列节点数据域 int data; //队列节点指针域 struct QNode *link; } QNode, *QueuePtr;
最简单的链队列具有两个指针 — 队头指针和队尾指针。构造空的链队列时,这两个指针都指向一个指针域为空的节点,即链队列的头节点。
![](http://dongweihang.com/wp-content/uploads/image-3.png)
注意下面代码中函数的参数是结构体 Q 的地址 &Q,为什么这里不直接用 Q ? 这里用到了C++的引用,作用是避免了指针的使用。
/* 链队列结构 */ typedef struct Queue { // front指向队列首元素 QueuePtr front; // rear指向队列末尾元素 QueuePtr rear; } LinkQueue; /* 构造空链表 */ int initQueue(LinkQueue &Q) { //构造空链表时,这两个指针都需要开辟空间,并且都指向一个空节点,即头节点 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if(Q.front == NULL) return ERR; //置空头指针指向的节点的指针域,即头节点的指针域不能乱指,应该指向空 Q.front->link = NULL; return OK; }
链队列的基本操作 ——> 创造一个新节点,让该节点入队:
![](http://dongweihang.com/wp-content/uploads/image-4.png)
/* 链队列 元素入队 */ int statusEnQueue(LinkQueue &Q, int e) { //首先声明一个指向某个节点的指针p,让他指向空 QNode *p = NULL; //给p指针指向的区域开辟空间,之前p指向空,赋值后指向的区域大小等于一个节点的大小 p = (QNode *)malloc(sizeof(QNode)); if(p == NULL) return ERR; //p指针指向的节点数据域赋值为e p->data = e; //p指针指向的节点指针域置空,因为不置空会可能会指向一个随机地址 p->link = NULL; //队列尾节点指向新节点p Q.rear->link = p; //队尾指针指向新节点p,即p成为了新的队尾节点 Q.rear = p; return OK; }
链队列的基本操作 ——> 节点出队。简而言之是让头节点指向第二个节点。
![](http://dongweihang.com/wp-content/uploads/image-5-1024x285.png)
/* 链队列 元素出队 */ int exitQueue(LinkQueue &Q) { QNode *p = NULL; /* 判断队列是否为空(当且仅当队列为空时,队列头指针和尾指针都指向队列头节点) */ if (Q.front == Q.rear) { printf("no elements in Queue"); return ERR; } /* 找到队列第一个元素,即头节点的下一个元素 */ p = Q.front->link; /* 头节点指针指向从头节点往后数的第二个节点,实现头节点下一个节点出队,即去除队列的第一个元素 */ Q.front->link = p->link; /* 易错点:出队之后,如果队列为空,说明尾指针还指着出队的节点,需要让它指向头节点 */ if (Q.rear == p) Q.front = Q.rear; /* 释放出队的节点。如果要用出队的这个节点,就不用free了,但记得不释放的话 p->link 还在指向第二个节点,记得改一下,可见画图很重要,没画图这个指针可能就忘记处理了 */ free(p); return OK; }
看到这儿·,可能有人会有个问题,如果队列中只有一个元素,那么刚才 Q.front->link = p->link 这行代码,我们让第二个元素变成了第一个元素,但是第二个元素根本就不存在啊,这是怎么回事?
第二个元素虽然不存在,但这行代码的含义是将 p 节点的指针域赋给头节点的指针域,所以 p 节点的指针域可以是空嘛。p->link 是 p 指针指向的节点的指针域里存放的地址,而不是 p 指针指向的节点的下一个节点,这个问题就是概念不清导致的。
参考资料:《数据结构与算法考研复习指导》— 王道考研系列