基于链表的链队
链表结点的存储结构如下:
typedef struct _node
{
int value;
struct _node *next;
}node,*pnode;
其中值的部分存放的是一个整数data,这部分数据可以自己再定义,增减。
node *front=NULL; //队头指针,由于是全局变量,请注意多线程安全
node *rear=NULL; //队尾指针,由于是全局变量,请注意多线程安全
在实现队列的基本操作的时候,最好是先画出队列的图形,如上图所示,然后按照图形来写各种操作的代码,思路就会比较清晰(注意,在多线程环境下,下面的代码没有提供加锁机制,需要另外处理)。
//创建队列
int CreateQueue()
{
front = rear = NULL;//将front和rear置为NULL
return 1;
}
//判断队列是否为空
int IsQueueEmpty()
{
if(front==NULL&&rear==NULL)//front和rear等于NULL是队列为空的标志
{
return 1;
}
return 0;
}
//入队
int EnQueue(int e)
{
node *p = (node *)malloc(sizeof(node));
if(p==NULL)
{
return -1;
}
memset(p,0,sizeof(node));
p->value = e;
p->next = NULL;
if(IsQueueEmpty())//队列为空,直接将rear和front指向该结点
{
rear=front=p;
return 1;
}
//队列不为空,插入尾部
rear->next = p;
rear = p;
return 1;
}
//出队
int DeQueue(int *e)//必须传指针,否则出队的值无法获取
{
if(IsQueueEmpty())
{
return -1;
}
if(e==NULL)
{
return -1;
}
//只有一个结点的时候
if(rear==front && rear!=NULL)
{
*e = rear->value;
free(rear);
front=rear=NULL;
return 1;
}
//多个结点的时候
*e = front->value;
node *q =front;
front = front->next;
free(q);
return 1;
}
//遍历队列
void TraverseQueue()
{
while(!IsQueueEmpty())
{
int value;
DeQueue(&value);
printf("%d ",value);
}
printf("\n");
}
//队列测试代码
int _tmain(int argc, _TCHAR* argv[])
{
int value;
CreateQueue();
EnQueue(3);
EnQueue(1);
EnQueue(0);
EnQueue(5);
DeQueue(&value);
printf("value:%d\n", value);
EnQueue(18);
EnQueue(27);
DeQueue(&value);
printf("value:%d\n", value);
DeQueue(&value);
printf("value:%d\n", value);
TraverseQueue();
return 0;
}