队列的操作实验（数据结构）

一、实验目的

1．掌握队列存储结构的表示和实现方法。
2．掌握队列的入队和出队等基本操作的算法实现。
3．了解队列在解决实际问题中的简单应用。

二、实验内容

1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作（验证性内容）。
2．建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。
3．实现键盘输入循环缓冲区问题（应用性设计内容）。

三、实验的软硬件环境要求

硬件环境要求：
PC机（单机）使用的软件名称、版本号以及模块： Windows环境下的TurboC2.0以上或VC++

四、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。

五、验证性实验

1．实验要求

编程实现如下功能：
（1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。
（2）将数据元素e入队，并输出入队后的队列中各元素值。
（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。

2. 实验相关原理：

队列是一种插入操作限制在表尾，而删除操作限制在表头进行的特殊线性表，它的操作具有“先进先出”的特性。采用顺序存储结构的队列称为顺序队列，顺序队列的存储结构描述如下：

#define MAXQSIZE 100/*顺序循环队列的最大长度*/typedef  struct
{ Qelemtype base[MAXQSIZE]; /*存放队列元素的数组空间*/
int front;  /*头指针，若队列不空，则指向队列头元素*/
int rear; /*尾指针，若队列不空，则指向队列尾元素的下一个存储单元*/}Sqqueue;

【核心算法提示】
1．顺序循环队列入队操作的基本步骤：首先判断队列是否为满，如果队列满，则函数返回ERROR，否则将待入队的数据元素e存放在尾指针rear所指示的存储单元中，再使尾指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。
2．顺序循环队列出队操作的基本步骤：首先判断队列是否为空，如果队列空，则函数返回ERROR，否则将头指针所指示的队首元素用e返回其值，再使头指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。
【核心算法描述】

status enqueue(Sqqueue &Q,Qelemtype e) 
/*在循环队列Q中，插入新元素使其成为队尾元素*/{  if ((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR; /*若队列满，插入操作不能进行，函数返回ERROR*/Q.base[Q.rear]=e;  /*新元素成为队尾元素*/Q.rear=(Q.rear+1)%MAXQSIZE;/*利用模运算,“尾指针”加1,使尾指针后移一个位置*/return OK;}
status dequeue(Sqqueue &Q，Qelemtype &e)
/*在循环队列Q中，删除Q的队首元素*/{  if (Q.front==Q.rear)  
return ERROR;/*若队列空，删除操作不能进行，函数返回ERROR*/e=Q.base[Q.front];/*将队首元素用e保存其值*/Q.front=(Q.front+1)%MAXQSIZE;/*利用模运算,“头指针”加1,使头指针后移一个位置*/return OK;
}

3．源程序代码参考

#define MAXQSIZE 100
typedef struct{ int base[MAXQSIZE];int front;int rear;} Sqqueue;
Sqqueue enqueue(Sqqueue Q,int e)/*队列的入队函数*/{ if ((Q.rear+1)%MAXQSIZE==Q.front)printf("ERROR\n");else{Q.base[Q.rear]=e;Q.rear = (Q.rear+1)%MAXQSIZE;    //队尾指针+1}return Q;
}
Sqqueue dequeue(Sqqueue Q,int *e)/*队列的出队函数*/{  int x;if (Q.front==Q.rear)printf("ERROR\n ");else{ e=Q.base[Q.front];            //保存队头元素Q.front=(Q.front+1)%MAXQSIZE;//对头指针+1}return Q;}
void display(Sqqueue Q)/*队列元素输出函数*/{ int k,m;k=Q.front;m=Q.rear;while(k!=m){ printf("%4d",Q.base[k]);k=(k+1)%MAXQSIZE;}printf("\n");}
main()/*主函数*/{ Sqqueue Q;int i,n,x,y,e;Q.rear=Q.front=0; /*初始化顺序队列，使其成为空队列*/printf("\nplease input the length:");/*请求输入队列的长度*/scanf("%d",&n);printf("please input create data:\n  ");/*请求输入队列中各个元素*/for(i=1;i<=n;i++){scanf("%d",&x);Q=enqueue(Q,x);}/*调用队列插入函数*/printf("the queue is:\n");display(Q);/*调用队列元素输出函数*/printf("please input a insert data:");/*请求输入需要插入的元素*/scanf("%d",&y);Q=enqueue(Q,y);/*调用队列插入函数*/printf("the queue after insert is:\n");/*提示显示执行入队操作后的队列*/display(Q);/*调用队列元素输出函数*/Q=dequeue(Q,&e);/*调用队列删除函数*/printf("the delete data is:%d\n",e); /*显示被删的队首元素值*/printf("the queue after delete is:\n");/*提示显示执行出队操作后的队列*/display(Q);/*调用队列元素输出函数*/}

4．运行结果参考如图4-1所示：

在这里插入图片描述

                  图4-1: 验证性实验运行结果

六、设计性实验

1．编程实现对循环链队列的入队和出队操作。

⑴ 实验要求
①根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。
②将数据元素e入队，并输出入队后的队列中各元素值。
③将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。
⑵ 核心算法分析
采用链式存储结构的队列称为链队列，链队列的存储结构描述如下：

typedef   struct  CQnode {
Qelemtype   data;/*数据域*/struct  CQnode  *next;/*指针域*/
}CQNODE,*CQLink;

如果队列中元素序列为{a1,a2，…,an}，则带头结点的循环链队列的存储结构如下图4-1所示：
在这里插入图片描述

从图4-1可看出，队列的循环链式存储结构与循环单链表的存储结构相同，所有在循环链队列上进行入队和出队操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：
①此循环链队列是通过一个指向队尾结点的指针rear来标识的,则rear指向队尾元素结点，rear->next指向队头结点，而rear->nexnt->next指向队首元素结点。
②队列的入队操作是在链表的表尾（队尾）进行，而出队操作则在链表的表头（队首）进行。
③在出队操作时要注意：如果当链表中只有一个结点，即被删结点既是队首结点，又是队尾结点时，要进行尾指针的修改。
⑶ 核心算法描述

void InitCiQueue(CQLink  &rear)
/*初始化循环链表表示的队列rear,其中rear指向队尾元素*/
{ rear=(CQNODE*)malloc(sizeof(CQNODE)); /*产生一个头结点，并使队尾指针指向它*/
rear->next=rear;   /*形成循环*/
}

入队操作：

status  EnCiQueue(CQLink &rear,  int x)
/*把元素x插入到循环链表表示的队列rear中*/
{  p=(CQNODE*)malloc(sizeof(CQNODE));If 
p->data=x;           /*产生一个新结点p*/p->next=rear->next;   /*直接把p插入到rear的后面*/rear->next=p;rear=p;         /*修改尾指针,使p成为新的队尾结点*/
}
status DeCiQueue(CQLink &rear, int  &x)
/*从用队尾指针rear表示的循环链表删除一个队首元素，并用x返回其数据域的值。*/
{ if(rear==rear->next)  return ERROR;  /*如果队列为空，则函数返回ERROR*/p=rear->next->next;/*用p指针指向队首结点,也是待删结点*/x=p->data;   /* 用x保存待删队首结点的数据域的值*/rear->next->next=p->next;/*修改链，使p的后继成为新的队首结点*/if (rear==p) /*如果待删的结点p是队尾结点,则要使队尾指针指向原来队尾结点的后继(头结点)*/rear=rear->next;
free(p);    /*释放待删结点的空间*/return OK;
}

2．编程实现键盘输入循环缓冲区问题。

⑴ 实验要求
有两个进程同时存在于一个应用程序中。其中一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户链入的字符并保存到缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号“，”时表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键入字符，直到用户输入一个分号“；”键，才结束第一个进程，同时也结束整个进程。

⑵ 核心算法提示
在操作系统中，循环队列经常用于实时应用程序。例如，当程序正在执行其他任务时，用户可以从键盘上不断键入所要输入的内容。很多字处理软件就是这样工作的。系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。在当前工作的进程结束后，系统就从缓冲区中取出键入的字符，并按要求进行处理。所以，这里的键盘输入缓冲区可采用循环队列。队列保证了输入字符先输入、先保存、先处理的要求，循环结构又有效地限制了缓冲区的大小，并避免了假溢出问题。
在这里插入图片描述