数据结构与算法-队列

#include <iostream>
#include <stdlib.h> 
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char QElemType;
typedef char SElemType;
typedef int Status;

typedef struct {
	QElemType *base;
	int front;
	int rear;
}SqQueue;

Status InitQueue(SqQueue &Q){
	Q.base = new QElemType[MAXQSIZE];
	if(!Q.base)
		exit(OVERFLOW);
	Q.front=Q.rear=0;
	return OK;
} 

int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + MAXQSIZE ) % MAXQSIZE;
} 

Status EnQueue(SqQueue &Q,QElemType e){
	if((Q.rear+1)%MAXQSIZE==Q.front)
		return ERROR;
	Q.base[Q.rear]=e;
	Q.rear = (Q.rear+1)%MAXQSIZE;
	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)%MAXQSIZE;
	return OK;
}

SElemType GetHead(SqQueue Q){
	if(Q.front!=Q.rear)
	return Q.base[Q.front];
} 

int main(){
	int choose=-1,flag=0;
	SqQueue Q;
	QElemType e,j;
	cout<<"1.初始化队列"<<endl;
	cout<<"2.入队"<<endl;
	cout<<"3.取队头元素"<<endl;
	cout<<"4.出队"<<endl;
	cout<<"0.退出程序"<<endl;
	
	while(choose!=0){
		cout<<"请选择功能:";
		cin>>choose;
		switch(choose){
			case 1:
				if(InitQueue(Q)){
					flag=1;
					cout<<"成功对队列初始化"<<endl;
				}
				else
					cout<<"初始化队列失败"<<endl; 
				break;
			case 2:
				if(flag==1){
					cout<<"请输入要入队的元素,用空格隔开,以enter键结束输入:"<<endl;
				cin.ignore();
				while(cin.get(j)&&j!='\n'){
					EnQueue(Q,j);
				} 
				cout<<"入队完成\n";
				}
				else
					cout<<"队未建立\n";
				break;
			case 3:
				if(flag!=-1&&flag!=0)
					cout<<"队头元素为:"<<GetHead(Q)<<endl;
				else
					cout<<"队中无元素请重新选择\n";
				break;
			case 4:
				cout<<"依次弹出的队头元素为\n";
				while(DeQueue(Q,e)) {
					flag=1;
					cout<<e<<" ";
				}
				cout<<endl;
				break;
		}
	}
	return 0;
}

下面是带有注释解释版本,解释每行话的作用

#include <iostream>
#include <stdlib.h> 
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char QElemType;    //把char命名为QElemType来表示队列存储的字符 
typedef char SElemType;  //用SElemType来表示函数的返回状态 
typedef int Status;     //用Status来表示函数的返回状态 

typedef struct {
	QElemType *base; //指向队列元素数组的指针,也就是队列的存储空间 
	int front;        //指向队头的指针,也就是指向队列中的第一个元素 
	int rear;        //这是队尾的尾指针,指向队列中最后一个元素的下一个位置 
}SqQueue;

//队列的初始化
Status InitQueue(SqQueue &Q){
	Q.base = new QElemType[MAXQSIZE];   //为队列动态分配一个最大容量为100的内存空间 
	if(!Q.base)                 //检查内存是否分配成功 
		exit(OVERFLOW);
	Q.front=Q.rear=0;      //将头指针等于尾指针置于0 
	return OK;
} 
//求队列的长度
int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + MAXQSIZE ) % MAXQSIZE; //取余,当队尾操作超过数组末尾时,通过取余可以将其映射在队列头 
} 
//循环队列的入队 
Status EnQueue(SqQueue &Q,QElemType e){
	if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1,判断队列是否满 
		return ERROR;
	Q.base[Q.rear]=e;    //新元素插队队尾 
	Q.rear = (Q.rear+1)%MAXQSIZE;   //更新队尾指针,队尾指针+1 
	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)%MAXQSIZE;  //更新队头指针 
	return OK;
}
//取队头元素
SElemType GetHead(SqQueue Q){
	if(Q.front!=Q.rear)
	return Q.base[Q.front];//返回队头元素的值,队头指针不变 
} 

int main(){
	int choose=-1,flag=0;
	SqQueue Q;
	QElemType e,j; //临时存储用户输入的元素
	cout<<"1.初始化队列"<<endl;
	cout<<"2.入队"<<endl;
	cout<<"3.取队头元素"<<endl;
	cout<<"4.出队"<<endl;
	cout<<"0.退出程序"<<endl;
	
	while(choose!=0){
		cout<<"请选择功能:";
		cin>>choose;
		switch(choose){
			case 1:
				if(InitQueue(Q)){
					flag=1;
					cout<<"成功对队列初始化"<<endl;
				}
				else
					cout<<"初始化队列失败"<<endl; 
				break;
			case 2:
				if(flag==1){
					cout<<"请输入要入队的元素,用空格隔开,以enter键结束输入:"<<endl;
				cin.ignore();  //清除缓冲区,防止接收到多余的换行符
				while(cin.get(j)&&j!='\n'){
					EnQueue(Q,j);
				} 
				cout<<"入队完成\n";
				}
				else
					cout<<"队未建立\n";
				break;
			case 3:
				if(flag!=-1&&flag!=0)
					cout<<"队头元素为:"<<GetHead(Q)<<endl;
				else
					cout<<"队中无元素请重新选择\n";
				break;
			case 4:
				cout<<"依次弹出的队头元素为\n";
				while(DeQueue(Q,e)) {
					flag=1;
					cout<<e<<" ";
				}
				cout<<endl;
				break;
		}
	}
	return 0;
}

评论

《 “数据结构与算法-队列” 》 有 2 条评论

  1. 宿舍义父

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注