隊列存儲結構及實作

一、目的

1. 掌握隊列的概念及實作方式
2. 熟悉隊列的存儲結構及運算

二、内容

1. 編寫一個程式sqqueue.cpp，實作環形隊列（假設棧中元素類型ElemType為char）的各種基本運算，并在此基礎上設計一個程式exp3-3.cpp，完成如下功能：

   （1） 初始化隊列q。

   （2） 判斷隊列q是否非空。

   （3） 依次進隊元素a、b、c。

   （4） 出隊一個元素，輸出該元素。

   （5） 依次進隊元素d、e、f。

   （6） 輸出出隊序列。

   （7） 釋放隊列。

2. 編寫一個程式liqueue.cpp，實作鍊隊（假設棧中元素類型ElemType為char）的各種基本運算，并在此基礎上設計一個程式exp3-4.cpp，完成如下功能：

   （1）初始化鍊隊q。

   （2）判斷鍊隊q是否非空。

   （3）依次進隊元素a、b、c。

   （4）出隊一個元素，輸出該元素。

   （5）依次進隊元素d、e、f。

   （6）輸出出隊序列。

   （7）鍊隊釋放隊列。

三、源代碼

1. 環形隊列

#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;
}
           

1. 鍊隊

#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;
}
           

備注：

有問題可以評論，看到後我會盡力及時回複的，謝謝！