1. 队列的定义
所谓队列(queue)就是一种能实现"先进先出"的一种线性存储结构.
跟栈有点类似, 例如栈只有1个出入口, 任何元素进入或者离开栈都必须经过同1个出入口(栈顶), 所以栈能实现"先入后出"的效果.
队列同样有出入口, 只不过出入口分别位于队列的两端, 元素只能从入口进入队列, 而且只能从另一端的出口离开队列, 在队列中间里的元素是不允许插入或删除操作的, 所以先进入队列的元素肯定会比后进入的元素先离开队列, 就是所谓的"先进先出"了.
举个例子, 例如现实中排队买票就是1个队列, 1个人只能从队伍的尾部进入队列, 从队伍的前部(买票窗口)买票离开队列, 中间插队是不允许的.
2. 队列的分类
就如栈可以分成动态栈和静态栈一样.
队列也可以分成静态队列和链式队列.
所谓静态队列就是用数组(连续内存) 作为内核的队列.
而链式队列就是以链表为内核的队列了.
下面会简介链式队列, 而且是单链表的链式队列.
3. 链式队列(单链表)的大概结构
画个图便于理解:
如上图, 我们会将1个单链表的首节点作为队列的前端(front), 就是队列的出口啦. 而会将单链表的尾节点作为队列的尾端(Rear), 就是队列的入口.
而我们会定义两个指针, Front指针来存放队列出口元素的地址, Rear指针来存放队列入口元素的地址.
之所以这样设定是为了方便出列操作, 如上图, 当节点0 要出列时, 0 作为1个首节点, 出列后Front指针就必须指向出列元素的下1个节点地址(节点1), 而这个地址恰好保存于节点0的尾部指针中啊.假如在单链表的尾部出列, 如上图, 加入节点4出列后, Front就必须指向节点3, 但是节点3的尾部指针指向节点4, 而根据节点4是找不到节点4上1个元素的地址的, 只能遍历链表啊.
而在尾节点入列同样方便, 如上图, 当节点4入列时, 只需要将队列原来的入口元素(Rear指针)的尾部地址指向入列节点, 然后 Rear指针指向这个新的入口元素!
上面就是1个最基本的链式队列结构, 但是有1个弊端, 就是当这个队列为空(所有元素出列后), 这个链表就消失了, 再入列时就无从下手!
所以实际操作我们会给在队列的前部(出口)加上1个不存放实际数据的头节点, 做为列表的出口, 这个头节点指向队列的真正的出口元素(pHead->pnext). 这样当队列所有元素出列后, 队列的Rear指针就手动指向不存放实际数据的头节点, 这样的话我们会认为这个队列是空队列.(pHead == pRear)
如下图:
4. 一个简单的链式队列的C语言代码实现
4.1 首先就是编写1个头文件
在这个头文件里我们会定义两个结构体, 1个是对应于队列的元素的, 所以这个结构体具有1个pNext 指针成员。 另1个结构体是对应于链式队列的, 具有4个成员, 分别是: pHead 头结点地址 pRear 存放入口元素的地址 len存放链表的长度信息 is_inited 用于判断链表结构体是否被初始化(里面的指针成员是否野指针)此外, 这个头文件也会生命一些算法函数, 别的文件引用这个头文件, 就可以使用这些函数了。
代码如下:
/** linkqueue1.h** Created on: -4-15*Author: gateman*/#include <bool_me.h>#ifndef __LINKQUEUE1_H_#define __LINKQUEUE1_H_struct person_linkqueue1{int id;char name[16];struct person_linkqueue1 * pNext;};typedef struct person_linkqueue1 PERSON_LQ;struct linkqueue1_person{PERSON_LQ * pHead;PERSON_LQ * pRear;int len;BOOL is_inited;};typedef struct linkqueue1_person LQPERSON;//create a new node with dynamic memory assignedPERSON_LQ * person_lq_new(int id, char * pname);//print the information of a nodevoid person_lq_print(PERSON_LQ * pnode);//create a stuck with dynamic linklistLQPERSON * lqperson_new(void);//judge whether the link_queue is emptyBOOL lq_is_empty(LQPERSON * pLq);//add an element into the queuevoid lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode);//remove an element from the queue, and get the elementBOOL lq_Dequeue(LQPERSON * pLq, PERSON_LQ ** pOutput);//traverse the queue to print all the elementsvoid lq_print(LQPERSON * pLq);//put out and free all the elements from the queuevoid lq_clear(LQPERSON * pLq);//free all the elements, and free the queuevoid lq_free(LQPERSON * pLq);#endif /* LINKQUEUE1_H_ */
下面会用列出上面声明的函数定义代码.
4.2 建立1个新节点(元素)函数 PERSON_LQ * person_lq_new(int id, char * pname)
这个函数作用就是动态分配1个新的内存给1个节点结构体, 既然是动态分配的, 那么这个节点很容易被其他函数访问。 而且必要时也可以手动释放。逻辑步骤如下:
1. 新建1个节点类型指针. 并动态分配一段内存.
2. 如果分配不成功, 退出程序
3. 设置参数传入的成员值(id, name)
4. 尾部指针设成NULL
5. 返回这个指针
代码如下:
PERSON_LQ * person_lq_new(int id, char * pname){PERSON_LQ * pnode = (PERSON_LQ *)malloc(sizeof(PERSON_LQ));if (NULL == pnode){base_error("fail to assign memory to a new node!");}pnode->id = id;strncpy(pnode->name, pname+0, 15);pnode->pNext=NULL;return pnode;}
4.3 打印1个节点的信息 void person_lq_print(PERSON_LQ * pnode)
这个不讲解了, 很简单
代码如下:
//print the information of a nodevoid person_lq_print(PERSON_LQ * pnode){printf("id is %d, name is %s\n",pnode->id, pnode->name);}
4.4 新建并初始化1个链式队列 LQPERSON * lqperson_new(void)
这个函数就是动态分配1段内存给1个链式队列, 并执行初始化, 最后返回这个结构体指针
步骤:
1. 新建1个链式队列结构体指针, 并动态分配1个内存
2. 若分配内存失败, 退出程序
3. 初始化链式队列的 pHead 头节点成员( 利用上面的 person_lq_new函数)
4. pRear 成员指向 pHead (代表空队列)
5. len长度设为0
6. is_inited 成员设为TRUE
7. 返回链式队列结构体指针
代码如下:
//create a stuck with dynamic linklistLQPERSON * lqperson_new(void){LQPERSON * pLq = (LQPERSON *)malloc(sizeof(LQPERSON));if (NULL == pLq){base_error("fail to assign memory to a linkqueue!");}pLq->pHead = person_lq_new(-1,"Head");pLq->pRear = pLq->pHead; //empty queue;pLq->len=0;pLq->is_inited = TRUE;return pLq;}
4.5 判断链式队列是否为空 BOOL lq_is_empty(LQPERSON * pLq)
这个很简单, 判断 pRear 是否指向 pHead就ok了, 当然判断len ==0 也可以..
代码如下:
//judge whether the link_queue is emptyBOOL lq_is_empty(LQPERSON * pLq){if (TRUE != pLq->is_inited){base_error("the linkqueue is not initailed yet!");}if (pLq->pRear == pLq->pHead){return TRUE;}return FALSE;}
4.6 入列函数 void lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode)
作用就是把1个节点元素放入队列, 逻辑并不复杂. 上面图解过了嘛
步骤:
1.入口元素地址 pRear的尾部指针指向这个入列元素
2,pRear 指向 这个入列元素, 这个入列元素就成为新的入口元素了
3. 这个入列元素的尾部指针指向NULL
4. 链表长度len+1
代码如下:
//add an element into the queuevoid lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode){if (TRUE != pLq->is_inited){base_error("the linkqueue is not initailed yet!");}pLq->pRear->pNext = pnode;pLq->pRear = pnode;pnode->pNext=NULL;pLq->len++;}
4.7 出列函数 BOOL lq_Dequeue(LQPERSON * pLQ, PERSON_LQ ** pOutput)
注意这个函数, 返回值是BOOL 也就是出列函数有可能失败, 因为如果1个空队列, 出列就肯定失败嘛
而且接受1个以地址传递的指针, 也就是指针的指针了, 用于接受出列元素的地址.
逻辑如下:
1. 判断是否为空队列, 否则返回FALSE
2. pOutput 指向出列元素(pHead 下1个元素)
3. pHead 头节点的尾部指针指向出列元素的下1个元素, 那个就是新的出口元素, 也就是说下次出列就轮到它啊
4. 如果出列元素是最后1个元素, 出列后 pRear 指向pHead, 代表成为1个空队列了
5. 队列长度len -1
6. 返回TRUE
代码如下:
//remove an element from the queue, and get the elementBOOL lq_Dequeue(LQPERSON * pLq, PERSON_LQ ** pOutput){if (TRUE != pLq->is_inited){base_error("the linkqueue is not initailed yet!");}if (TRUE == lq_is_empty(pLq)){printf("the linkqueue is empty!\n");return FALSE;}*pOutput = pLq->pHead->pNext;pLq->pHead->pNext = (*pOutput)->pNext;//if it's the last oneif(pLq->pRear == *pOutput){pLq->pRear = pLq->pHead; //empty}pLq->len--;return TRUE;}
4.8 打印1个队列函数 lq_print(LQPERSON * pLq)
这个函数作用就是从出口开始打印队列的存放有效数据的函数, 就是从Front 到 Rear啦.
相当于1个遍历,
代码如下:
//traverse the queue to print all the elementsvoid lq_print(LQPERSON * pLq){if (TRUE != pLq->is_inited){base_error("the linkqueue is not initailed yet!");}if (TRUE == lq_is_empty(pLq)){printf("the linkqueue is empty!\n");}PERSON_LQ * pnode = pLq->pHead;while(NULL != pnode->pNext){pnode=pnode->pNext;person_lq_print(pnode);}}
4.9 删除所有队列元素函数 lq_clear
当然, pRear 指向 pHead, 这样这个队列马上就是1个空队列, 但是这样里面的节点就容易丢失, 也就是内存泄露啊
所以我们要逐个地释放里面节点的内存, 然后才把 pRear 指向 pHead
//put out and free all the elements from the queuevoid lq_clear(LQPERSON * pLq){if (TRUE != pLq->is_inited){base_error("the linkqueue is not initailed yet!");}PERSON_LQ * pnode = pLq->pHead;PERSON_LQ * pnext = pnode->pNext;while(NULL != pnext){pnode = pnext;pnext = pnode->pNext;free(pnode);}pLq->pHead->pNext=NULL;pLq->pRear = pLq->pHead;pLq->len=0;}
4.9 销毁队列函数 lq_free
这个更简单, 首先执行清空.
然后把头节点的内存释放
最后把队列结构体释放
代码如下:
//free all the elements, and free the queuevoid lq_free(LQPERSON * pLq){lq_clear(pLq);free(pLq->pHead);free(pLq);}
4.10 写个程序测试上面的函数
纯粹测试下啦:
代码如下:
int linkqueue1(){PERSON_LQ * pnode = person_lq_new(1,"JasonPoon111212121212");person_lq_print(pnode);free(pnode);LQPERSON * plq1 = lqperson_new();lq_Enqueue(plq1, person_lq_new(1,"Jason"));lq_Enqueue(plq1, person_lq_new(2,"Cindy"));lq_Enqueue(plq1, person_lq_new(3,"Fiana"));lq_Enqueue(plq1, person_lq_new(4,"Gateman"));lq_print(plq1);int i=0;int j=plq1->len-1;for (i=0; i < j; i++){lq_Dequeue(plq1,&pnode);printf("the out node is\n");person_lq_print(pnode);printf("\n");free(pnode);}lq_print(plq1);lq_Dequeue(plq1,&pnode);printf("the out node is\n");person_lq_print(pnode);printf("\n");free(pnode);lq_print(plq1);lq_Enqueue(plq1, person_lq_new(1,"Jason"));lq_Enqueue(plq1, person_lq_new(2,"Cindy"));lq_Enqueue(plq1, person_lq_new(3,"Fiana"));lq_Enqueue(plq1, person_lq_new(4,"Gateman"));lq_print(plq1);printf("now clear the linkqueuei!\n");lq_clear(plq1);lq_print(plq1);lq_free(plq1);printf("linkq1 done\n");return 0;}
输出: