一．实验项目名称
循环队列和链式队列的创建
二、实验目的
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
#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 为止 "<cout<<" 输入元素入队
cin>>i;
while(i)
{
enq( q,i);
cin>>i;
}
y=gethead( q);
cout<<" 队头为 ="<dlq( q);
y=gethead( q);
cout<<" 执行一次删除队头后，队头为="<}
b.链队列的源代码
#include
typedef struct QNode
{
char data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
