声明：版权所有，欢迎转载。 联系信箱：yiluohuanghun@gmail.com】
感觉我的这个专题的顺序安排的有点问题，按照我们常规的思维应该是先线性表、队列、堆栈、单链表、双链表、但是我貌似给排反了，主要还是之前没想着要写这么细，那也就算了吧，既然专题名字叫“chaos的算法”，那就实实在在的让它“chaos”一次吧。
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。队列的用途很广泛，一般在工程中比较常用的地方我感觉是消息部分，把N多的消息做成一个消息队列是最好不过的了。
对于队列来说，又分为静态队列结构和链式队列结构，相对而言静态队列结构要容易理解一些，其实队列跟我们下一篇要说的栈是很类似的，都既可以用链表实现、也可以用顺序表实现。但是队列跟栈相反，栈一般我们用顺序表、而队列我们一般采用链表实现，简称链式队列。先看数据结构吧：
|
1
2
3
4
5
6
7
8
9
10
11
|
typedef
int
ElemType;
typedef
struct
LNode
{
ElemType elem;
struct
LNode *next;
}LNode, *LinkList;
typedef
struct
queue
{
LinkList Front;
//队头
LinkList Rear;
//队尾
}QUEUE;
|
我们一般将队头指针指向链队列的头结点，队尾指针指向终端结点。其实在链式队列中队头不是必要的，但是有了队头相对来说操作起来就容易的多了。创建一个队列一般要完成两件事情。一个是在内存中创建一个头结点，二是将队列的头指针(队头)和尾指针都指向这个新生成的头结点，因为此时还未插入任何结点，所以此时的队列为空队列。
|
1
2
3
4
5
6
7
8
|
//初始化队列
void
InitQueue(QUEUE *Q)
{
Q->Front = (LinkList)
malloc
(
sizeof
(LNode));
if
(NULL == Q->Front)
return
;
Q->Rear = Q->Front;
}
|
入队操作时，一般是将队尾结点的next指针指向待插入结点，而后将队尾指针指向待插入结点。思路倒是很简单的。在别的地方找了一个不错的图，就借鉴过来了(http://blog.fishc.com/2139.html/3)
|
1
2
3
4
5
6
7
8
9
10
11
|
//入队
void
EnQueue(QUEUE *Q, ElemType elem)
{
LinkList p = (LinkList)
malloc
(
sizeof
(LNode));
if
(NULL == p)
return
;
p->elem = elem;
p->next = NULL;
Q->Rear->next = p;
Q->Rear = p;
}
|
出队操作时，将队头所指结点的值取出，并申请一个结点内存指向待出队结点，该结点主要用于使队头指针移向下一个结点。先看下代码吧：
|
1
2
3
4
5
6
7
8
9
10
11
|
//出队
void
DeQueue(QUEUE *Q, ElemType *elem)
{
LinkList s = (LinkList)
malloc
(
sizeof
(LNode));
if
(QueueEmpty(*Q))
return
;
*elem = Q->Front->next->elem;
s = Q->Front->next;
Q->Front->next = s->next;
free
(s);
}
|
这里有一个比较重要的地方还没说，我们的Front队头指针是不存放数据的，这点大家一点要看清，要不然在出队和入队操作时回有点小迷糊的。
在某些时候我们还要判断队列是否为空，这个在一些清空下是必须的哟
|
1
2
3
4
5
6
7
|
//判断队列空
bool
QueueEmpty(QUEUE Q)
{
if
(Q.Front == Q.Rear)
return
TRUE;
return
FALSE;
}
|
一般来说对于队列的操作无外乎也就几种，当然了，还有一种叫做获取队头元素
|
1
2
3
4
5
6
7
|
/*获取队头元素内容 */
void
GetFront(QUEUE Q, ElemType *elem)
{
if
(QueueEmpty(Q))
return
;
*elem = Q.Front->next->elem;
}
|
队列的操作也就这么多，在最好还是要强调一点，一定要做个测试程序出来，验证下自己所写程序的可用性。这个是非常的有必要的。
本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/1263369，如需转载请自行联系原作者
