数据结构（严蔚敏版）第三章——栈和队列（三）【队列的表示和操作的实现】

voidp(参数) {
if (递归结束条件成立) 可直接求解;      // 递归终止的条件elsep(较小的参数);                 // 递归步骤}
// 例如longFact (longn) {
if (n==0) return1;             // 基本项elsereturnn*Fact(n-1);      // 归纳项}

ADTQueue {
数据对象：D= {ai|ai属于ElemSet, i=1, 2, ... , n, n>=0}
数据关系：R= { <ai-1, ai>|ai-1, ai属于D, i=2, ... , n} // 约定其中a1端为队列头，an端为队列尾基本操作：InitQueue(&Q);
操作结果：构造空队列QDestroyQueue(&Q);
条件：队列Q已存在操作结果：队列Q被销毁ClearQueue(&Q);
条件：队列Q已存在操作结果：将Q清空QueueLength(&Q);
条件：队列Q已存在操作结果：返回Q的元素个数，即队长GetHead(Q, &e);
条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue(&Q, e);
条件：队列Q已存在操作结果：插入元素e为Q的队尾元素DeQueue(&Q, &e);
条件：Q为非空队列操作结果：删除Q的队头元素，用e返回值QueueTraverse(Q);
条件：Q存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素访问}

#define MAXQSIZE 100      // 最大队列长度Typedefstruct {
QElemType*base;        // 初始化的动态分配存储空间intfront;              // 头指针intrear;               // 尾指针}SqQueue;

StatusInitQueue(SqQueue&Q) {
Q.base=newQElemType[MAXQSIZE];           // 分配数组空间// Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));if (!Q.base) exit(OVERFLOW);                // 存储分配失败Q.front=Q.rear=0;                       // 头指针尾指针置为0，队列为空returnOK;
}

intQueueLength(SqQueueQ) {
return (Q.rear-Q.front+MAXQSIZE) %MAXQSIZE;
}

StatusEnQueue(SqQueue&Q, QElemTypee) {
// 插入元素e为Q的新的队尾元素if ((Q.rear+1) %MAXQSIZE==Q.front)         // 尾指针在循环意义上加1后等于头指针，表明队满returnERROR;
Q.base[Q.rear] =e;                             // 新元素插入队尾Q.rear= (Q.rear+1) %MAXQSIZE;               // 队尾指针加1returnOK;
}

StatusDeQueue(SqQueue&Q, QElemType&e) {
// 删除Q的队头元素if (Q.front==Q.rear) returnERROR;            // 队空e=Q.base[Q.front];                            // 保存队头元素Q.front= (Q.front+1) %MAXQSIZE;             // 队头指针加1returnOK;
}

SElemTypeGetHead(SqQueueQ) {
// 返回Q的队头元素，不修改队头指针if (Q.front!=Q.rear)            // 队列非空returnQ.base[Q.front];         // 返回队头元素的值，队头指针不变}

#define MAXQSIZE 100        // 最大队列长度typedefstructQnode {
QElemTypedata;
structQNode*next;
}QNode, *QueuePtr;
typedefstruct {
QueuePtrfront;           // 队头指针QueuePtrrear;            // 队尾指针}LinkQueue;

StatusInitQueue(LinkQueue&Q) {
// 构造一个空队列Q.front=Q.rear=newQNode;             // 生成新结点作为头结点，队头和队尾指针指向该结点Q.front->next=NULL;                     // 头结点的指针域为空returnOK;
}

StatusDestroyQueue (LinkQueue&Q) {
while(Q.front) {
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
  }+returnOK;
}

StatusEnQueue(LinkQueue&Q, QElemTypee) {
// 插入元素e为Q的新的队尾元素p=newQNode;                        // 为入队元素分配结点空间，用指针p指向p->data=e;                        // 将新结点数据域置为ep->next=NULL; Q.rear->next=p; // 将新结点插入到队尾Q.rear=p;                           // 修改队尾指针returnOK;
}

StatusDeQueue(LinkQueue&Q, QElemType&e){
// 删除Q的队头元素，用e返回其值if (Q.front==Q.rear) returnERROR;          // 若队列为空，则返回ERRORp=Q.front->next;                          // p指向队头元素e=p->data;                                // e保存队头元素的值Q.front->next=p->next;                  // 修改头结点的指针域if (Q.rear==p) Q.rear=Q.front;            // 最后一个元素被删，队尾指针指向头结点deletep;                                     // 释放原队头元素的空间returnOK;
}

SElemTypeGetHead(LinkQueueQ) {
// 返回Q的队头元素，不修改队头指针if (Q.front!=Q.rear)                          // 队列非空returnQ.front->next->data;               // 返回队头元素的值，队头指针不变}