队列存储与操作实验报告.doc

实验四 队列存储与操作一、实验目的1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活运用。二、实验内容1顺序队列的实现和运算2链式队列的实现和运算3循环队列的实现和运三、 详细设计：1、顺序队列的实现：#includeusing namespace std;const int Size=100;typedef char DataType;class CirQueue public:CirQueue()front=rear=0;/构造队列，初，front和rear指向CirQueue()void EnQueue(DataType x)if(rear+1)%Size=front)cout队列已经满了endl;return;rear=(rear+1)%Size;/队尾指针在循环的意义下加datarear=x;coutx已入队endl;return;DataType GetQueue()/取队头if(isEmpty()cout队列为空endl;return 0;int i;i=(front+1)%Size;return datai;DataType DeQueue()if(isEmpty()cout队列为空endl;return 0;front=(front+1)%Size;/队头指针在循环的意义下加return datafront;int isEmpty()/是否为空if(front=rear)return 1;elsereturn 0;private:DataType dataSize;int front,rear;int main()CirQueue a;int index;DataType temp;docout*endl;cout1、入队操作endl;cout2、取队头操作endl;cout3、出队操作endl;cout4、判断队列是否为空endl;cout5、退出endl;cout*index;if(index=5)return 0;switch(index)case 1:cout请输入要入队的元素temp;a.EnQueue(temp);break;case 2:temp=a.GetQueue();if(temp!=0)cout队头的元素为temp endl;break;case 3:temp=a.DeQueue();if(temp!=0)cout出队的元素为temp endl;break;case 4:bool temp;temp=a.isEmpty();if(temp)cout空队endl;elsecout非空队endl;break;while(index);return 0;2、循环队列的实现：#include #include #define OK 1#define ERROR 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int QElemType;#define MAXQSIZE 100 / 最大队列长度(对于循环队列，最大队列长度要减1)typedef struct QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针,若队列不空,指向队列头元素 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;Status InitQueue(SqQueue &Q) / 构造一个空队列Q，该队列预定义大小为MAXQSIZEQ.base = (QElemType *)malloc (MAXQSIZE * sizeof(QElemType);if(!Q.base) return ERROR;Q.front = Q.rear = 0;return OK;Status EnQueue(SqQueue &Q,QElemType e) / 插入元素e为Q的新的队尾元素if(Q.rear + 1)% MAXQSIZE = Q.front)return ERROR;Q.baseQ.rear = e ;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;Status DeQueue(SqQueue &Q, QElemType &e) / 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERRORif(Q.front = Q.rear) return ERROR;e = Q.baseQ.front;Q.front = (Q.front +1) % MAXQSIZE;return OK;Status GetHead(SqQueue Q, QElemType &e)/ 若队列不空，则用e返回队头元素，并返回OK，否则返回ERRORif(Q.front = Q.rear) return ERROR;e = Q.baseQ.front;return OK;int QueueLength(SqQueue Q) / 返回Q的元素个数return (Q.rear + MAXQSIZE - Q.front) % MAXQSIZE;Status QueueTraverse(SqQueue Q) / 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.int i;i=Q.front;if(Q.front = Q.rear)printf(空队!); elseprintf(队列为 is: );while(i Q.rear) printf(%d ,Q.basei); i = i+1; printf(n);return OK;int main()int a; SqQueue S;QElemType x, e; if(InitQueue(S) / 判断顺序表是否创建成功printf(创建一个队列.n);while(1)printf(1:入队n2:出队 n3:取队头 n4:队长n5:显示n0:退出n选择:n);scanf(%d,&a);switch(a)case 1: scanf(%d, &x); if(!EnQueue(S,x) printf(Enter Error!n); / 判断入队是否合法 else printf( %d 入队!n, x); break;case 2: if(!DeQueue(S,e) printf(Delete Error!n); / 判断出队是否合法 else printf( %d 出队!n, e); break;case 3: if(!GetHead(S,e)printf(Get Head Error!n); / 判断Get Head是否合法 else printf(取队头 %d!n, e); brea