1. 队列的定义
所谓队列(queue)就是一种能实现"先进先出"的一种线性存储结构.
跟栈有点类似, 例如栈只有1个出入口, 任何元素进入或者离开栈都必须经过同1个出入口(栈顶), 所以栈能实现"先入后出"的效果.
队列同样有出入口, 只不过出入口分别位于队列的两端, 元素只能从入口进入队列, 而且只能从另一端的出口离开队列, 在队列中间里的元素是不允许插入或删除操作的, 所以先进入队列的元素肯定会比后进入的元素先离开队列, 就是所谓的"先进先出"了.
举个例子, 例如现实中排队买票就是1个队列, 1个人只能从队伍的尾部进入队列, 从队伍的前部(买票窗口)买票离开队列, 中间插队是不允许的.
2. 队列的分类
就如栈可以分成动态栈和静态栈一样.
队列也可以分成静态队列和链式队列.
所谓静态队列就是用数组(连续内存) 作为内核的队列.
而链式队列就是以链表为内核的队列了.
下面会简介链式队列, 而且是单链表的链式队列.
3. 链式队列(单链表)的大概结构
画个图便于理解:
而我们会定义两个指针, 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个头文件
/*
* linkqueue1.h
*
* Created on: 2013-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 assigned
PERSON_LQ * person_lq_new(int id, char * pname);
//print the information of a node
void person_lq_print(PERSON_LQ * pnode);
//create a stuck with dynamic linklist
LQPERSON * lqperson_new(void);
//judge whether the link_queue is empty
BOOL lq_is_empty(LQPERSON * pLq);
//add an element into the queue
void lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode);
//remove an element from the queue, and get the element
BOOL lq_Dequeue(LQPERSON * pLq, PERSON_LQ ** pOutput);
//traverse the queue to print all the elements
void lq_print(LQPERSON * pLq);
//put out and free all the elements from the queue
void lq_clear(LQPERSON * pLq);
//free all the elements, and free the queue
void lq_free(LQPERSON * pLq);
#endif /* LINKQUEUE1_H_ */
4.2 建立1个新节点（元素）函数 PERSON_LQ * person_lq_new(int id, char * pname)
逻辑步骤如下:
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 node
void 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 linklist
LQPERSON * 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 empty
BOOL 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 queue
void 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 element
BOOL 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 one
if(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 elements
void 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 queue
void 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 queue
void 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;
}
输出:
