6、数据结构笔记之六链队列实现
“人生天地之间，若白驹之过隙，忽然而已。”。
1. 定义
如下图所示，和链栈基本一致。
#defineIS_EMPTY(ptr)(!(ptr))
#defineIS_FULL(ptr) (!(ptr))
typedefstructelement{
intkey;
/*otherfields */
}element;
typedefstructqueue *queue_pointer;
typedefstructqueue {
elementitem;
queue_pointerlink;
}queue;
queue_pointer front=NULL,rear=NULL;
2. 增加节点函数
函数如下，增加的节点放在rear中。：
void addq(queue_pointer *front,queue_pointer *rear,elementitem)
{
queue_pointertemp = (queue_pointer ) malloc(sizeof(queue));
if(IS_FULL(temp)){
fprintf(stderr,"Thememory is full\n");
exit(1);
}
temp->item= item;
temp->link=NULL;
if(*front)(*rear)->link= temp;
else *front =temp;
*rear =temp;
}
3. 删除节点函数
删除节点是从front出删除节点，先进先出。增加的都放在了rear，所以出去的都从rear开始。。
element deleteq(queue_pointer *front)
{
queue_pointertemp = *front;
elementitem;
if(IS_EMPTY(*front)){
fprintf(stderr,"Thequeue is empty\n");
exit(1);
}
item= temp->item;
*front =temp->link;
free(temp);
returnitem;
}
4. Main函数
Main函数调用addq和deleteq函数，
void main()
{
inti;
elementtemp ;
//add10 nodes to queue
for(i=0;i<20;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd 10nodes to queue\n");
print_node(front);
printf("\n");
for(i=0;i<10;i++)
{
temp=deleteq(&front);
printf("thedelete node's key is %d\n",temp.key);
}
printf("afterdelete 10 nodes \n");
print_node(front);
printf("\n");
for(i=0;i<1;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd one nodes to queue\n");
print_node(front);
printf("\n");
for(i=0;i<11;i++)
{
temp=deleteq(&front);
printf("thedelete node's key is %d\n",temp.key);
}
printf("afterdelete left 10 nodes \n");
//print_node(front);
printf("\n");
for(i=0;i<3;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd another 3 nodes to queue\n");
print_node(front);
printf("\n");
}
5. 源码
#include"stdio.h"
#include"stdlib.h"
#defineIS_EMPTY(ptr)(!(ptr))
#defineIS_FULL(ptr) (!(ptr))
typedefstructelement{
intkey;
/*otherfields */
}element;
typedefstructqueue *queue_pointer;
typedefstructqueue {
elementitem;
queue_pointerlink;
}queue;
queue_pointer front=NULL,rear=NULL;
void addq(queue_pointer *front,queue_pointer *rear,elementitem)
{
queue_pointertemp = (queue_pointer ) malloc(sizeof(queue));
if(IS_FULL(temp)){
fprintf(stderr,"Thememory is full\n");
exit(1);
}
temp->item= item;
temp->link=NULL;
if(*front)(*rear)->link= temp;
else *front =temp;
*rear =temp;
}
element deleteq(queue_pointer *front)
{
queue_pointertemp = *front;
elementitem;
if(IS_EMPTY(*front)){
fprintf(stderr,"Thequeue is empty\n");
exit(1);
}
item= temp->item;
*front =temp->link;
free(temp);
returnitem;
}
void print_node(queue_pointertop){
if (IS_EMPTY(top)){
fprintf(stderr,"Thestack is empty\n");
return;
}
for(top;top;top=top->link)
{
printf("%d ",top->item);
}
}
void main()
{
inti;
elementtemp ;
//add10 nodes to queue
for(i=0;i<20;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd 10nodes to queue\n");
print_node(front);
printf("\n");
for(i=0;i<10;i++)
{
temp=deleteq(&front);
printf("thedelete node's key is %d\n",temp.key);
}
printf("afterdelete 10 nodes \n");
print_node(front);
printf("\n");
for(i=0;i<1;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd one nodes to queue\n");
print_node(front);
printf("\n");
for(i=0;i<11;i++)
{
temp=deleteq(&front);
printf("thedelete node's key is %d\n",temp.key);
}
printf("afterdelete left 10 nodes \n");
//print_node(front);
printf("\n");
for(i=0;i<3;i++)
{
temp.key=i;
addq(&front,&rear,temp);
}
printf("afteradd another 3 nodes to queue\n");
print_node(front);
printf("\n");
}