一．实验项目名称
循环队列和链式队列的创建
二、实验目的
1、掌握队列的特点 (先进先出 FIFO) 及基本操作 ,如入队、出队等，
2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在
实际问题背景下灵活应用。

三、实验内容
1．链式队列的实现和运算
2．循环队列的实现和运算
四、主要仪器设备及耗材
VC++6.0 运行环境实现其操作
五．程序算法
(1)循环队列操作的算法
1>进队列
Void enqueue (seqqueue &q, elemtype x)
{
if ((q.rear+1)%maxsize = = q.front)
cout<< ” overflow”;
else {
q.rear=(q.rear+1)%maxsize; // 编号加 1 或循环回第一个单元
q.queue[q.rear]=x;
}
}
2>出队列
Void dlqueue(seqqueue &q )
{
if (q.rear= =q.front)cout<< ” underflow”;
else
q.front =(q.front+1)%maxsize;
}
3>取对头元素
elemtype gethead(seqqueue q )
{ if(q.rear= =q.front)
{ cout<<” underflow；”
return NULL;}
else return q.queue[(q.front+1)%maxsize];
//front 指向队头前一个位置
}
4>判队列空否
int empty(seqqueue q )
{
if (q.rear= =q.front)
else return 0;
reurn 1;
}
（2）.链队列操作的算法
1>.链队列上的初始化
void INIQUEUE( linkqueue&s)
{link *p; p=new
link;
p->next=NULL;//p 是结构体指针类型，用
s.front=p;//s 是结构体变量，用.
s.rear=p;//头尾指针都指向头结点
->
}
2>.入队列
void push(linkqueue &s, elemtype x)
{
link*p;//p 是结构体指针类型，用->
p=new link;
p->data=x;
p->next=s.rear->next;//s 是结构体变量，用s.rear->next=p;
s.rear=p;//插入最后
.
}
3>判队空
int empty( linkqueue s )
{if (s.front= =s.rear) return 1;
else return 0;
}
4>.取队头元素
elemtype gethead( linkqueue s )
{
if (s.front= =s.rear)
else retuen
return NULL; s.front->next->data;
}
5>.出队列
void pop(linkqueue &s)
{ link *p; p=s.front-
>next;
if (p->next= =NULL)//链队列中只有一个元素,需要修改rear 指针{s.front->next=NULL;
s.rear=s.front;}
else
s.front->next =p->next;//rear不用变
delete (p);
}
六 .程序源代码
a.循环队列源代码
#include<iostream.h>
#define MAXN20
struct seq
{
char queue[MAXN];
int front, rear;
};
void iniq(seq&q)
{
q.front=q.rear=MAXN-1;
}
void enq(seq &q,char x)
{
if((q.rear+1)%MAXN==q.front)
cout<<"overflow";
else {
q.rear=(q.rear+1)%MAXN;
q.queue[q.rear]=x;
}
//return(0);
}
void dlq(seq &q)
{
if (q.rear == q.front)
cout<<"underflow";
else
q.front=(q.front+1)%MAXN;
}
int gethead(seq &q)// 取队头元素
{if (q.rear == q.front)// 判断是否队列为空
cout<<"underflow";
else
return q.queue[(q.front+1)%MAXN];
}
main()
{seq q;
int i,y;
iniq(q);
0 为止 "<<endl;
cout<<" 输入元素入队
cin>>i;
while(i)
{
enq( q,i);
cin>>i;
}
y=gethead( q);
cout<<" 队头为 ="<<y<<endl;
dlq( q);
y=gethead( q);
cout<<" 执行一次删除队头后，队头为="<<y<<endl;
}
b.链队列的源代码
#include <iostream.h>
typedef struct QNode
{
char data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode; Q.front->next=NULL;
return 0;
}
EnQueue(LinkQueue &Q,char e)
{
QueuePtr p;
p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 0;
}
void disp(LinkQueue &Q) //打印队列{
QueuePtr p;
p=Q.front->next;
while(p!=NULL)
{
cout<<p->data<<"->";
p=p->next;
}
}
DeQueue(LinkQueue &Q,char &e)
{
QueuePtr p;
if(Q.front==Q.rear)return 1;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete p;
return 0;
}
void main()
{
LinkQueue Q;
char e,e1;
InitQueue(Q);
cout<<" 输入队列元素,0 时结束： "<<endl;
cin>>e;
while(e!='0'){
EnQueue(Q,e);
cin>>e;
}
cout<<" 队列为： "<<endl;
disp(Q);
DeQueue(Q,e1);
cout<<endl<<" 执行一次删除队头，删除的元素是:"<<e1<<endl;
cout<<" 队列为 :"<<endl;
disp(Q);
cout<<endl;
}
六.程序输入数据及实验结果
a.循环队列实验结果
c.链队列实验结果
七、思考讨论题或体会或对改进实验的建议
（1）体会
a．C++语言知识不懂，需要好好学习；
b．对单链表不够熟悉，要多练习创建单链表及其基本操作。

八、参考资料
a.《数据结构》李根强主编中国国水利水电出版社
b.《C++语言程序设计》郑莉董渊何江舟编清华大学出
版社。