（1）实验目的

        通过该实验，使学生理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C语言中指针操作。

（2）实验内容

        用链式存储结构，实现教材定义的队列的基本操作。

（3）参考界面

 菜单中包括以下功能：

1.初始化队列，2.销毁队列，3.清空队列，4. 队列判空，5.求队列长度，6.获取队头元素，7.插入一个 元素，8.删除一个元素，9输出所有元素。

（4）验收/测试用例

通过菜单调用各个操作，测试点：

1. 没有初始化前进行其他操作，程序是否能控制住；
2. 初始化一个队列；
3. 判队列空，屏幕显示队列为空；
4. 3个数入队， 3、5、7；
5. 队头长度，屏幕输出3；
6. 取队头元素，再判队列是否空，然后再判队列长度，（让学生知道取队头元素不改变队列中的内容，队头指针不发生改变）；
7. 出队，再判队列长度和显示队列中剩余的元素；（多次出队，队列为空之后再执行出队操作，是否提示队列为空）；
8. 入队一个元素2，再出队，再判断队列是否为空，（主要测试出队操作中特殊情况下的那两行代码是否写了）；
9. 销毁队，再做其他操作，判断程序是否能控制。

#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#include<malloc.h>
#include<iostream>
using namespace std;
typedef int QElemType; 
typedef int Status;typedef struct QNode{QElemType data;struct QNode *next;
}QNode,*QueuePtr;typedef struct{QueuePtr front;//队头指针QueuePtr rear;//队尾指针 
}LinkQueue;Status InitQueue(LinkQueue &Q);//队列的初始化
Status DestoryQueue(LinkQueue &Q);//队列的销毁 
Status ClearQueue(LinkQueue &Q);//清空 
Status QueueEmpty(LinkQueue &Q);//判断是否为空 
int QueueLength(LinkQueue Q);//求队列长度 
Status GetHead(LinkQueue Q,QElemType &e);//获取队列头元素
Status EnQueue(LinkQueue &Q,QElemType e);//为队列插入队尾元素 
Status DeQueue(LinkQueue &Q,QElemType &e);//删除队头元素
Status QueueTraverse(LinkQueue Q);//遍历队列int main()
{LinkQueue Q;int e;int a;cout<<"----持续犯困盐盐子----"<<endl;cout<<"1.----初始化队列"<<endl;cout<<"2.----销毁队列"<<endl;cout<<"3.----清空队列"<<endl;cout<<"4.----判断队列是否为空"<<endl;cout<<"5.----求队列的长度"<<endl;cout<<"6.----获取队尾元素"<<endl;cout<<"7.----插入元素进入队头"<<endl;cout<<"8.----删除队列元素"<<endl;cout<<"9.----输出所有元素"<<endl;cout<<"     退出：输入一个负数！"<<endl;cout<<endl<<"请输入操作代码：";while((cin>>a)!=0){if(a<0)  break;else{switch(a){case 1:InitQueue(Q);cout<<endl<<"请输入操作代码：";break;case 2:DestoryQueue(Q);cout<<endl<<"请输入操作代码：";break;case 3:ClearQueue(Q);cout<<endl<<"请输入操作代码：";break;case 4:QueueEmpty(Q);cout<<endl<<"请输入操作代码：";break;case 5:QueueLength(Q);cout<<endl<<"请输入操作代码：";break;case 6:cout<<"队头元素为："<<GetHead(Q,e)<<endl;cout<<endl<<"请输入操作代码：";break;case 7:cout<<"请输入您需要插入的元素：";scanf("%d",&e);EnQueue(Q,e);printf("插入成功！"); cout<<endl<<"请输入操作代码：";break;case 8:e=DeQueue(Q,e); printf("%d\n",e);printf("删除队头元素成功！");cout<<endl<<"请输入操作代码：";break;case 9:QueueTraverse(Q);cout<<endl<<"请输入操作代码：";break;}}} 
}//1、队列的初始化
Status InitQueue(LinkQueue &Q)
{//构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front) return FALSE;//存储空间分配失败Q.front->next=NULL;printf("初始化成功！");return TRUE; 
}//2、队列的销毁 
Status DestoryQueue(LinkQueue &Q)
{while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}printf("销毁成功！");return TRUE;} //3、清空 
Status ClearQueue(LinkQueue &Q)
{//先将队尾指针指向对头指针的下一个结点Q.rear=Q.front->next;while(Q.front->next){//队尾指针后移Q.rear=Q.rear->next; //释放对头指针和队尾指针中间的结点free(Q.front->next);//连接队列Q.front->next=Q.rear; } //队列为空时，调整队尾指针Q.rear=Q.front; printf("清空成功！");} //4、判断是否为空 
Status QueueEmpty(LinkQueue &Q)
{if(Q.front==Q.rear){printf("队列为空！\n");}printf("该队列不为空！"); } //5、求队列长度 
int QueueLength(LinkQueue Q)
{int i=0;while(Q.front!=Q.rear){i++;Q.front=Q.front->next;}printf("该队列长度为：%d",i);
//	return i;
}//6、获取队列头元素
Status GetHead(LinkQueue Q,QElemType &e)
{//先判断是否为空if(Q.front==Q.rear) return FALSE;else{e=Q.front->next->data;return e;}} //7、为队列插入队尾元素 
Status EnQueue(LinkQueue &Q,QElemType e)
{//为新元素e分配空间QNode *p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)  return FALSE;p->data=e;p->next=NULL;Q.rear->next=p;//修改队尾指针，插入新队尾结点 Q.rear=p; return TRUE;
}//8、删除队头元素
Status DeQueue(LinkQueue &Q,QElemType &e)
{QNode *p;if(Q.front==Q.rear)  return FALSE;//判断队列是否为空 p=Q.front->next;//p指向队头元素结点 e=p->data;Q.front->next=p->next;//修改队列头结点指针，则删除队头元素结点 if(Q.rear==p)  Q.rear=Q.front;//对于队列只有一个元素结点，要同时修改队尾指针 free(p);return TRUE;
}//9、遍历队列
Status QueueTraverse(LinkQueue Q)
{QNode *p;if(Q.front==Q.rear)  return FALSE;p=Q.front->next;//存储头元素printf("该队列元素有：\n");while(p!=NULL){printf("%d \n",p->data);p=p->next;} 
}

 作者：盐盐子