队列考点（经过gcc调试）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

   以前一直以为队列在自己的编程中不会有应用的时候，这次再次复习这个知识点时，才发现队列在嵌入式编程中也很重要，在实习公司的一个sel日志模块就用了一个数组做循环队列做缓存，来保证日志来得及写入文件而不会丢失，下面将链队列的实现代码贴出，供大家交流。

#include <stdio.h>
#include <stdlib.h>


/*定义单链队列----队列的链式存储结构*/
typedef struct node
{
int data;
struct node *next;
}qnode;


/*定义队列类型，包括队头和队尾指针*/
typedef struct linkqueue
{
qnode *frist;
qnode *last;
}queue;


/*****************************************************************
 *功能描述：插入元素val为队列新的队尾元素
 *传入参数：hq：指向队列的指针，val:入队元素的值
 *传出参数：无
 *返回值： 更新后的队列指针
 ****************************************************************/
queue *in_queue(queue *hq, int val)
{
qnode *s = (qnode *)malloc(sizeof(qnode));
if(!s)
{
printf("malloc error\n");/*存储分配失败*/
return NULL;
}
s->data = val;
s->next = NULL;
/*判断队列是否为空，为空则将队头和队尾指针同时更新*/
if(NULL == hq->last)
{
hq->frist = hq->last = s;
}
else
{
hq->last->next = s;/*将新元素插入到队尾并更新队尾指针*/
hq->last = s;
}


return hq;
}




/*****************************************************************
 *功能描述：删除队列的队头元素，用e返回其值
 *传入参数：hq:需要更新的队列指针
 *传出参数：e:出队元素的值
 *返回值： 更新后的队列指针
 ****************************************************************/
queue *out_queue(queue *hq, int *e)
{
qnode *p = NULL;
/*判空*/
if(!hq->frist)
{
printf("over flow\n");
exit(1);
}
else
{
*e = hq->frist->data;
p = hq->frist;
/*队中只有一个元素，直接把队列清空；否则队头元素出队后释放空间*/
if(hq->frist == hq->last)
{
hq->frist = hq->last = NULL;
}
else
{
hq->frist = hq->frist->next;
free(p);
}
}
return hq;
}




/*****************************************************************
 *功能描述：初始化队列，建立一个有六个元素的队列
 *传入参数：队列指针
 *传出参数：无
 *返回值： 无
 ****************************************************************/
void init_queue(queue *hq)
{
int i, a;
hq->frist = hq->last = (qnode *)malloc(sizeof(qnode));
hq->frist = hq->last = NULL;


for(i=0; i<6; i++)
{
printf("please input queue item:\n");
scanf("%d", &a);
in_queue(hq, a);
}
return;
}


/*****************************************************************
 *功能描述：打印队列元素
 *传入参数：队列指针
 *传出参数：无
 *返回值： 无
 ****************************************************************/
void print(queue *hq)
{
int val;
qnode *p = hq->frist;
while(p)
{
/*由于用出队操作，破坏了队列，使下面的操作无法执行，所以采用了更新指针 的方式；注意此处不能直接用hq->frist进行操作，否则会破坏队列唯一的队头 指针，采用临时指针将队头指针拷贝一份可以避免破坏队列*/
//out_queue(hq, &val);
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}


/*****************************************************************
 *功能描述：销毁队列
 *传入参数：队列指针
 *传出参数：无
 *返回值： 无
 ****************************************************************/
void destroy_queue(queue *hq)
{
while(hq->frist)
{
hq->last = hq->frist->next;
free(hq->frist);


hq->frist = hq->last;
}
}




/*****************************************************************
 *功能描述：求队列长度
 *传入参数：队列指针
 *传出参数：无
 *返回值： 队列的长度
 ****************************************************************/
int queue_length(queue *hq)
{
int j = 0;
qnode *p = NULL;
/*队列为空，返回0*/
if(!hq->frist)
{
printf("empty queue\n");
return 0;
}
p = hq->frist;
while(p)
{
p = p->next;
++j;
}
return j;
}


int main(void)
{
int d;
queue *p = NULL;
queue *hq = (queue *)malloc(sizeof(queue));


init_queue(hq);


print(hq);
d = queue_length(hq);
printf("the length of queue: %d\n", d);


p = out_queue(hq, &d);
printf("out data from queue: %d\n", d);
print(p);
destroy_queue(hq);


return 0;
}