队列存储与操作实验报告

一、实验目的

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

1．顺序队列的实现和运算 2．链式队列的实现和运算 3．循环队列的实现和运

三、详细设计：

1、顺序队列的实现：

#include using 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<<\"队列已经满了\"<rear=(rear+1)%Size;//队尾指针在循环的意义下加 data[rear]=x;

cout<DataType GetQueue()//取队头 {

if(isEmpty()) {

cout<<\"队列为空\"<int i;

i=(front+1)%Size; return data[i]; }

DataType DeQueue() {

if(isEmpty()) {

cout<<\"队列为空\"<front=(front+1)%Size;//队头指针在循环的意义下加 return data[front]; }

int isEmpty()//是否为空 {

if(front==rear) {

return 1; } else{

return 0; } } private:

DataType data[Size]; int front,rear; };

int main() {

CirQueue a; int index; DataType temp; do {

cout<<\"**********************************\"<cout<<\"4、判断队列是否为空\"<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=a.DeQueue(); if(temp!=0) {

cout<<\"出队的元素为\"<bool temp;

temp=a.isEmpty(); if(temp) {

cout<<\"空队\"<cout<<\"非空队\"<break; }

}while(index); return 0;

}

2、循环队列的实现：

#include #include #define OK 1 #define ERROR 0

typedef 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，该队列预定义大小为MAXQSIZE

Q.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.base[Q.rear] = e ;

Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; }

Status DeQueue(SqQueue &Q, QElemType &e) {

// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR

if(Q.front == Q.rear) return ERROR; e = Q.base[Q.front];

Q.front = (Q.front +1) % MAXQSIZE;

return OK; }

Status GetHead(SqQueue Q, QElemType &e) {

// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR

if(Q.front == Q.rear) return ERROR; e = Q.base[Q.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(\"空队!\"); else{

printf(\"队列为 is: \"); while(i < Q.rear) {

printf(\"%d \ 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\ switch(a) {

case 1: scanf(\"%d\

if(!EnQueue(S,x)) printf(\"Enter Error!\\n\"); // 判断入队是否合法

else printf(\" %d 入队!\\n\ break;

case 2: if(!DeQueue(S,e)) printf(\"Delete Error!\\n\"); // 判断出队是否合法

else printf(\" %d 出队!\\n\ break;

case 3: if(!GetHead(S,e))printf(\"Get Head Error!\\n\"); // 判断Get Head是否合法

else printf(\"取队头 %d!\\n\ break;

case 4: printf(\"队长为 %d!\\n\ break;

case 5: QueueTraverse(S) ; break;

case 0: return 1; } } }

四、调试分析：

1、顺序队列：

主界面

入队操作

取队头操作

出队操作

判空操作

2循环队列

主界面

入队

出队

队长

显示