🎯目的：
1、掌握队列的顺序表示和实现(循环队列)。
2、掌握队列的链式表示和实现。
🎯内容：
1、队列的顺序表示和实现(循环队列)。
2、队列的链式表示和实现。
🎯环境：
TC或VC++。
🎯步骤
1.队列的顺序表示和实现(循环队列)
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
- 循环队列初始化：front=rear=0；
- 入队操作：rear=(rear+1)%size;
- 出队操作：front=(front+1)%size;
- 判断是否为空队列：front==rear；//程序中的if语句体现，没有单独写一个函数
- 判断队列是否已满：front=(rear+1)%size；//程序中的if语句体现，没有单独写一个函数
(6）遍历队列各元素。
要求：采用空闲一个位置的方式，即N个元素空间的循环队列最多只能存放N-1个有效元素。
循环队列结构定义：
typedef struct SqQueue { QElemType *base; int front;//头指针 int rear;//尾指针 }SqQueue,*SqQueuePtr;
程序：
#include "iostream" using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define MAXSIZE 100 typedef char QElemType; typedef char SElemType; typedef int Status; typedef struct{//循环队列的构建 QElemType *base; int front; int rear; }SqQueue; int tag=0; Status InitQueue(SqQueue &Q){//循环队列的初始化 Q.base=new QElemType[MAXSIZE]; if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e){//循环队列的入队 if((Q.rear+1)%MAXSIZE==Q.front)//判断是否为满 return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; } Status DeQueue(SqQueue &Q,QElemType &e){//循环队列的出队 if(Q.front==Q.rear)//判断是否为空 return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; } void QueueTraverse(SqQueue Q){//遍历各元素 int p=Q.front; if(Q.front==Q.rear) cout<<"队列已空"<<endl; else{ cout<<"队列元素为:"<<endl; while(p!=Q.rear){ cout<<Q.base[p]<<" "; p=(p+1)%MAXSIZE; } } cout<<endl; } int main(){ int choose; SqQueue Q; QElemType e; cout<<"1.初始化\n"; cout<<"2.入队\n"; cout<<"3.出队\n"; cout<<"4.遍历队列\n"; cout<<"5.判断队列是否为空\n"; cout<<"6.判断队列是否为满\n"; cout<<"0.退出\n"; choose=-2; while(choose!=0){ cout<<"请输入你的选择:"; cin>>choose; switch(choose){ case 1: if(InitQueue(Q)){ cout<<"初始化已成功"<<endl; } else cout<<"初始化失败"<<endl; break; case 2: cout<<"请输入您要入队的字符(单个字符)： "; cin>>e; if(EnQueue(Q,e)){ cout<<"入队成功"<<endl; } else cout<<"入队失败"<<endl; break; case 3: if(DeQueue(Q,e)){ cout<<"出队的元素为:"; cout<<e<<endl; } else cout<<"出队失败，对列已空"<<endl; break; case 4: QueueTraverse(Q); break; case 5: if(Q.front==Q.rear) cout<<"该队列为空"<<endl; else cout<<"该队列不为空"<<endl; break; case 6: if((Q.rear+1)%MAXSIZE==Q.front) cout<<"该队列为满"<<endl; else cout<<"该队列没有满"<<endl; case 0: cout<<"退出成功"; break; default: "输入错误，请重新输入"; } } }
2.队列的链式表示和实现
编写一个程序实现链式队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
队列的链式存储结构定义
typedef struct LinkNode{ ELEMTYPE data; struct LinkNode *next; }LinkNode; typedef struct{ LinkNode *front,*rear; }LinkQuene;
- 初始化
- 判空
- 入队
- 出队
(5) 队列的遍历
程序：
#include "iostream" using namespace std; #define OK 1 #define ERROR 0 typedef int Status; typedef char QElemType; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue(LinkQueue &Q){//初始化 Q.front=Q.rear=new QNode; Q.front->next=NULL; return OK; } Status QueueEmpty(LinkQueue Q){//判空 if(Q.front==Q.rear) return ERROR; return OK; } Status EnQueue(LinkQueue &Q,QElemType e){//入队 QueuePtr p; p=new QNode; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e){//出队 if(Q.rear==Q.front) return ERROR; QueuePtr p; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; delete p; return OK; } Status TraverseQueue(LinkQueue Q){//队列的遍历 if(Q.rear==Q.front){ cout<<"队为空"<<endl; return ERROR; } QueuePtr s=Q.front->next; cout<<"队中元素为: "; while(s){ printf("%-3c ",s->data); s=s->next; } cout<<endl; return OK; } int main(){ LinkQueue Q; int choose; QElemType e; cout<<"1.初始化\n"<<endl; cout<<"2.判空\n"<<endl; cout<<"3.入队\n"<<endl; cout<<"4.出队\n"<<endl; cout<<"5.队列的遍历\n"<<endl; cout<<"0.退出\n"<<endl; choose=-1; while(choose){ cout<<"请输入你的选择:"; cin>>choose; switch(choose){ case 1: if(InitQueue(Q)) cout<<"初始化成功"<<endl; else cout<<"初始化失败"<<endl; break; case 2: if(QueueEmpty(Q)) cout<<"队列为不空"<<endl; else cout<<"队列为空"<<endl; break; case 3: cout<<"请输入要插入的字符(单个字符)："; cin>>e; if(EnQueue(Q,e)) cout<<"入队成功"<<endl; else cout<<"入队失败"<<endl; break; case 4: if(DeQueue(Q,e)) cout<<"出队元素为"<<e<<endl; else cout<<"队为空"<<endl; break; case 5: TraverseQueue(Q); break; case 0: cout<<"退出成功"<<endl; break; deflaut: cout<<"输入错误，请重新输入!"<<endl; } } }
[附加题]
（必做）假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag= 0 和tag= 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空” 还是“满＂。试编写与此结构相应的插入(Enqueue) 和删除(Dequeue) 算法。
