首页 > 代码库 > 链式队列总结
链式队列总结
基本数据结构之-链式队列
链式队列就是一个操作受到限制的单链表，学会了单链表再来写这个就是轻松加愉快，但是貌似我去用了两个小时搞定，主要是基础差！
队列的基本操作就是入栈和出栈，还可以看到对头和对尾
如果维护了长度参数，那么也可以返回一个长度
不说理论了，直接上代码吧！
首先定义基本数据结构的结构体：
typedef struct _LINKQUEUENODE
{
struct _LINKQUEUENODE *next;
}LinkQueueNode;
typedef struct _LINKQUEUE
{
LinkQueueNode head;
int size;
}LinkQueue;
呵呵，其实和单链表的没什么区别
// 初始化
// 初始化
int Init_LinkQueue(void ** Queue)
{
// 对传入的参数进行检测
if (Queue == NULL)
exit(-1); // 为什么不返回错误码了，初始化不成功，后面的操作都会错
// 开辟一个LinkQueue结构体，
LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
if (queue == NULL)
{
exit(-2);// 原因同exit(-1);
}
// 对开辟的空间的值初始化
queue->head.next = NULL;
queue->size = 0;
// 指针间的间接赋值
*Queue = queue;
return 0;
}
接下来需要你去排队了
// 入对
int Push_LinkQueue(void * Queue, void * Data)
{
if (Queue == NULL)
{
return -1;
}
if (Data =http://www.mamicode.com/= NULL)
{
return -2;
}
// 将传入的参数Queue转化为可以被我们操作的类型LinkQueue *queue,其实在传递形参时，实参就是LinkQueue *；
LinkQueue *queue = (LinkQueue *)Queue;
// 转化数据
LinkQueueNode *data = http://www.mamicode.com/(LinkQueueNode *)Data;
/*
* 这个为什么这样就可以把数据连接起来
* 把链表头结点这边看做队列的对尾，每次入队都是对对尾的操作，
* 我们前面是定义了一个 linkQueue 类型的结构体，里面含有有个 head ，入队就是对head指向的修改
* 为了将 head 原来后面的数据串起来，所以首先需要用 data 的 next 域来接收head的next域
* 最后将 head 指向 data
*/
data->next = queue->head.next;
queue->head.next = data;
// 链式对列维护了一个长度变量，入队是长度加一
++ queue->size;
return 0;
}
// 出队操作
int Pop_LinkQueue(void * Queue)
{
if (Queue == NULL)
{
return -1;
}
LinkQueue *queue = (LinkQueue *)Queue;
// 出队时，一定要检查队列的长度，当对列为空时，对对列进行出队的操作，或出BUG
if (queue->size == 0)
{
return -2;
}
LinkQueueNode *pCurrent = &(queue->head);
// 为什么需要检查怎么远
/*
* 如果只写条件 pCurrent != NULL 那么最后指针将移动到最后一个元素的后面，那么不用说，就知道会发生什么情况
* 只检测 pCurrent->next != NULL 指针将指向最后一个元素，后面pCurrent->next = NULL或者 pCurrent = NULL;都是无用的,
* 在讨论一下就是pCurrent->next->next != NULL的检测，这个主要是保证让指针最后停到对头的后面一个元素的位置上，保证将最后的元素指针置空
*/
while (pCurrent != NULL && pCurrent->next != NULL && pCurrent->next->next!=NULL)
{
pCurrent = pCurrent->next;
}
// 将最后一个元素的前面一个元素的指针置空
pCurrent->next = NULL;
// 维护对列的长度
-- queue->size;
// 因为之后将queue->head->next 置空，而不会将queue->head置空，那么访问对列时，也可以访问一个元素
if (queue->size == 0)
{
queue->head.next = NULL;
}
return 0;
}
我要知道队列的长度，满足您
// 返回对列的大小
int Size_LinkQueue(void * Queue)
{
if (Queue == NULL)
{
return -1;
}
LinkQueue *queue = (LinkQueue *)Queue;
return queue->size;
}
//我看这个对列不爽，我要干掉
// 销毁队列
int Destroy_LinkQueue(void * Queue)
{
if (Queue == NULL)
return -1;
LinkQueue *queue = (LinkQueue *)Queue;
// 即使知道queue不可能为空，但是还是对它做一次检测
if(queue!=NULL)
free(queue);
return 0;
}
哎呀，这个对是谁在前面带队，谁在最后了？？？
// 返回对尾数据的指针
void* Back_LinkQueue(void * Queue)
{
if (Queue == NULL)
return NULL;
LinkQueue *queue = (LinkQueue *)Queue;
return queue->head.next;
}
// 返回队首数据的指针
void* Front_LinkQueue(void * Queue)
{
if (Queue == NULL)
{
return NULL;
}
LinkQueue *queue = (LinkQueue *)Queue;
if (queue->size == 0)
{
return NULL;
}
LinkQueueNode *pCurrent = &(queue->head);
while (pCurrent != NULL && pCurrent->next != NULL)
{
pCurrent = pCurrent->next;
}
return pCurrent;
}
相信聪明的您已经知道怎么遍历这个队列了吧，可不是现实生活中的，你可以看一遍哈！
你需要在定义一个队列，从对头将每个数据看一遍之后再让他们去另一个队列，知道看到最后一个数据，让后把对头的指针指向新的队列，那么你就遍历了整个队列！代码就不给出了，什么不给，根本就没写！
源码在文章 http://www.cnblogs.com/bkcarlos/p/5890903.html 中提到，如果没有上传，那么可能忘记了！哈哈哈！肯定会上传的
独乐乐，不如众乐乐！
链式队列总结