队列存储结构及实现

一、目的

掌握队列的概念及实现方式熟悉队列的存储结构及运算

二、内容

编写一个程序sqqueue.cpp，实现环形队列（假设栈中元素类型ElemType为char）的各种基本运算，并在此基础上设计一个程序exp3-3.cpp，完成如下功能： （1） 初始化队列q。 （2） 判断队列q是否非空。 （3） 依次进队元素a、b、c。 （4） 出队一个元素，输出该元素。 （5） 依次进队元素d、e、f。 （6） 输出出队序列。 （7） 释放队列。编写一个程序liqueue.cpp，实现链队（假设栈中元素类型ElemType为char）的各种基本运算，并在此基础上设计一个程序exp3-4.cpp，完成如下功能： （1）初始化链队q。 （2）判断链队q是否非空。 （3）依次进队元素a、b、c。 （4）出队一个元素，输出该元素。 （5）依次进队元素d、e、f。 （6）输出出队序列。 （7）链队释放队列。

三、源代码

环形队列 #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int front,rear; }SqQueue; void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=0; } void DestroyQueue(SqQueue *&q) { free(q); } bool QueueEmpty(SqQueue *q) { return(q->front==q->rear); } bool enQueue(SqQueue *&q,ElemType e) { if((q->rear+1)%MaxSize==q->front) return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; } bool deQueue(SqQueue *&q,ElemType &e) { if(q->front==q->rear) return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; } int main() { ElemType e; SqQueue *q; printf("环形队列基本运算如下：\n"); printf("（1）初始化队列q\n"); InitQueue(q); printf("（2）依次进队列元素a,b,c\n"); if(!enQueue(q,'a'))printf("\t提示：队满，不能进队\n"); if(!enQueue(q,'b'))printf("\t提示：队满，不能进队\n"); if(!enQueue(q,'c'))printf("\t提示：队满，不能进队\n"); printf("（3）队列为%s\n",(QueueEmpty(q)?"空":"非空")); if(deQueue(q,e)==0) printf("队空，不能出队\n"); else printf("（4）出队一个元素%c\n",e); printf("（5）依次进队列元素d,e,f\n"); if(!enQueue(q,'d'))printf("\t提示：队满，不能进队\n"); if(!enQueue(q,'e'))printf("\t提示：队满，不能进队\n"); if(!enQueue(q,'f'))printf("\t提示：队满，不能进队\n"); printf("（6）出队列序列："); while(!QueueEmpty(q)) { deQueue(q,e); printf("%c",e); } printf("\n"); printf("（7）释放队列\n"); DestroyQueue(q); return 0; } 链队 #include<stdio.h> #include<malloc.h> typedef char ElemType; typedef struct DataNode { ElemType data; struct DataNode *next; }DataNode; typedef struct { DataNode *front; DataNode *rear; }LinkQuNode; void InitQueue(LinkQuNode *&q) { q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; } void DestroyQueue(LinkQuNode *&q) { DataNode *p=q->front,*r; if(p!=NULL) { r=p->next; while(r!=NULL) { free(p); p=r;r=p->next; } } free(p); free(q); } bool QueueEmpty(LinkQuNode *q) { return(q->rear==NULL); } void enQueue(LinkQuNode *&q,ElemType e) { DataNode *p; p=(DataNode *)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if(q->rear==NULL) q->front=q->rear=p; else { q->rear->next=p; q->rear=p; } } bool deQueue(LinkQuNode *&q,ElemType &e) { DataNode *t; if(q->rear==NULL) return false; t=q->front; if(q->front==q->rear) q->front=q->rear=NULL; else q->front=q->front->next; e=t->data; free(t); return true; } int main() { ElemType e; LinkQuNode *q; printf("链队的基本运算如下：\n"); printf("（1）初始化链队q\n"); InitQueue(q); printf("（2）依次进链队元素a,b,c\n"); enQueue(q,'a'); enQueue(q,'b'); enQueue(q,'c'); printf("（3）链队为%s\n",(QueueEmpty(q)?"空":"非空")); if(deQueue(q,e)==0) printf("队空，不能出队\n"); else printf("（4）出队一个元素%c\n",e); printf("（5）依次进队列元素d,e,f\n"); enQueue(q,'a'); enQueue(q,'b'); enQueue(q,'c'); printf("（6）出链队序列："); while(!QueueEmpty(q)) { deQueue(q,e); printf("%c",e); } printf("\n"); printf("（7）释放链队\n"); DestroyQueue(q); return 0; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！