队列的学习与应用（数据结构）
一、队列的定义:
[indent][color=#ff0033]队列[/color]是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫[color=#ff0033]队尾[/color]，允许删除的一端则称为[color=#ff0033]队头[/color]。
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
基本操作：
[indent]InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
[/indent]}ADT Queue
[/indent]二、链队列－队列的链式表示和实现
[indent]用链表表示的队列简称为[color=#ff0033]链队列[/color]。一个链队列显然需要两个分别指示队头和队尾的指针。
[table=98%][tr][td=1,1,50%][table=98%][tr][td] [/td][td=1,1,27%]
[/td][td]
[/td][td=1,1,29%] [/td][/tr][tr][td]Q.front ->[/td][td=1,1,27%]
[/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%]
[/td][td][align=center][size=-3]\|/[/size][/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%][align=center]1[/align][/td][td][align=center]|[/align][/td][td=1,1,29%]队头[/td][/tr][tr][td] [/td][td=1,1,27%]
[/td][td][align=center][size=-3]\|/[/size][/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%][align=center]2[/align][/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%]
[/td][td][align=center][size=-3]\|/[/size][/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%][align=center]3[/align][/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td=1,1,33%] [/td][td]
[/td][td=1,1,11%][align=center][size=-3]\|/[/size]
[size=-3]\|/[/size]
[/align][/td][td] [/td][/tr][tr][td=1,1,33%]Q.rear ->[/td][td=1,1,27%][align=center]9[/align][/td][td][align=center]/\[/align][/td][td=1,1,29%]队尾[/td][/tr][/table][/td][td=1,1,50%][table=98%][tr][td] [/td][td=1,1,27%]
[/td][td]
[/td][td=1,1,29%] [/td][/tr][tr][td]Q.front ->[/td][td=1,1,27%]
[/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%]
[/td][td=1,1,11%][align=center][size=-3]\|/[/size][/align][/td][td] [/td][/tr][tr=#ccffcc][td=1,1,33%] [/td][td][align=center]1[/align][/td][td=1,1,11%][align=center]|[/align][/td][td]队头[/td][/tr][tr][td=1,1,33%] [/td][td]
[/td][td=1,1,11%][align=center][size=-3]\|/[/size][/align][/td][td] [/td][/tr][tr][td=1,1,33%] [/td][td=1,1,27%][align=center]2[/align][/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%]
[/td][td][align=center][size=-3]\|/[/size][/align][/td][td=1,1,29%] [/td][/tr][tr][td] [/td][td=1,1,27%][align=center]3[/align][/td][td][align=center]|[/align][/td][td=1,1,29%] [/td][/tr][tr][td=1,1,33%] [/td][td]
[/td][td=1,1,11%][align=center][size=-3]\|/[/size]
[size=-3]\|/[/size]
[/align][/td][td] [/td][/tr][tr][td=1,1,33%]Q.rear ->[/td][td=1,1,27%][align=center]9[/align][/td][td][align=center]/\[/align][/td][td=1,1,29%]队尾[/td][/tr][/table][/td][/tr][/table]
链队列表示和实现：
//存储表示
typedef struct QNode{
[indent]QElemType data;
struct QNode *next;
[/indent]}QNode,*QueuePtr;
typedef struct{
[indent]QueuePtr front;
QueuePtr rear;
[/indent]}LinkQueue;
//操作说明
Status InitQueue(LinkQueue &Q)
[indent]//构造一个空队列Q
[/indent]Status Destroyqueue(LinkQueue &Q)
[indent]//队列Q存在则销毁Q
[/indent]Status ClearQueue(LinkQueue &Q)
[indent]//队列Q存在则将Q清为空队列
[/indent]Status QueueEmpty(LinkQueue Q)
[indent]// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
[/indent]Status QueueLenght(LinkQueue Q)
[indent]// 队列Q存在,返回Q的元素个数,即队列的长度
[/indent]Status GetHead(LinkQueue Q,QElemType &e)
[indent]//Q为非空队列,用e返回Q的队头元素
[/indent]Status EnQueue(LinkQueue &Q,QElemType e)
[indent]//队列Q存在,插入元素e为Q的队尾元素
[/indent]Status DeQueue(LinkQueue &Q,QElemType &e)
[indent]//Q为非空队列,删除Q的队头元素,并用e返回其值
[/indent]Status QueueTraverse(LinkQueue Q,QElemType vivsit())
[indent]//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
[/indent]//操作的实现
Status InitQueue(LinkQueue &Q) {
[indent]//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;}
[/indent]Status Destroyqueue(LinkQueue &Q) {
[indent]//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
[/indent]Status EnQueue(LinkQueue &Q,QElemType e) {
[indent]//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
[/indent]Status DeQueue(LinkQueue &Q,QElemType &e) {
[indent]//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
[/indent][/indent]三、总结
[indent]链队列的存储表示
链队列的操作及实现
[/indent]