数据结构（C实现）------- 顺序队列(循环队列之少用一个存储空间实现) .

65 阅读 0 评论 43 点赞

我是靠谱客的博主奋斗花瓣，最近开发中收集的这篇文章主要介绍数据结构（C实现）------- 顺序队列(循环队列之少用一个存储空间实现) .，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

上节已经提到有三种方法来实现循环顺序队列，其中第一种设立标识不常用，最常的就是后两种，上一节已经讨论了用计数器来实现循环顺序队列，这节就用第三种方法，也就是少用一个存储空间来实现循环顺序队列，其基本操作和用计数实现类同，下面是具体实现：

顺序队列（循环队列）类型描述：

//顺序队列的类型描述
#define MAXSIZE 5
typedef int ElemType;
typedef struct{
	ElemType *data;
	int front,rear;
}SqQueue;

基本操作：

1. 初始化顺序队列(循环队列) Init_SqQueue(SqQueue* Q)

void Init_SqQueue(SqQueue* Q){
    Q->data = (SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);

	Q->front = Q->rear = 0;	
}

2. 销毁顺序队列(循环队列)Destroy_SqQueue(SqQueue* Q)

void Destroy_SqQueue(SqQueue* Q){
	if(Q->data){
		free(Q->data);
		Q->front = Q->rear = 0;
	}
}

3. 清空顺序队列(循环队列)Clear_SqQueue(SqQueue* Q)

void Clear_SqQueue(SqQueue* Q){
	Q->front = Q->rear = 0;
}

4. 判断顺序队列(循环队列)是否为空IsEmpty_SqQueue(SqQueue* Q)

int IsEmpty_SqQueue(SqQueue* Q){
	return (Q->rear == Q->front);
}

5. 判断顺序队列(循环队列)是否已满 iSFull_SqQueue(SqQueue* Q)

int iSFull_SqQueue(SqQueue* Q){
	return ((Q->rear + 1) % MAXSIZE == Q->front);
}

6. 求得顺序队列(循环队列)的长度GetLength_SqQueue(SqQueue* Q)

int GetLength_SqQueue(SqQueue* Q){
	return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

7. 取得顺序队列(循环队列)的的队头GetHead_SqQueue(SqQueue* Q,ElemType *x)

void GetHead_SqQueue(SqQueue* Q,ElemType *x){
	if(IsEmpty_SqQueue(Q)){
		printf("顺序队列空!n");
		exit(0);
	}
	else{
		*x = Q->data[Q->front];
	}
}

8. 取得顺序队列(循环队列)的的队尾GetRear_SqQueue(SqQueue* Q,ElemType *x

void GetRear_SqQueue(SqQueue* Q,ElemType *x){
	if(IsEmpty_SqQueue(Q)){
		printf("顺序队列空!n");
		exit(0);
	}
	else{
		*x = Q->data[(Q->rear - 1 + MAXSIZE) % MAXSIZE];
	}
}

9. 入顺序队列(循环队列)En_SqQueue(SqQueue* Q,ElemType x)

void En_SqQueue(SqQueue* Q,ElemType x){
	if(iSFull_SqQueue(Q)){
		printf("顺序队列已满!n");
		exit(0);
	}
	else{
		Q->data[Q->rear] = x;
		Q->rear = (Q->rear + 1) % MAXSIZE;
	}	
}

10. 出顺序队列(循环队列)De_SqQueue(SqQueue* Q,ElemType *x)

void De_SqQueue(SqQueue* Q,ElemType *x){
	if(IsEmpty_SqQueue(Q)){
		printf("顺序队列空!n");
		exit(0);
	}
	else{
		*x = Q->data[Q->front];
		Q->front = (Q->front + 1) % MAXSIZE;
	}	
}

11. 打印顺序队列(循环队列)Print_SqQueue(SqQueue* Q)

void Print_SqQueue(SqQueue* Q){
	int i = 0;
	int j = Q->front;

	if(IsEmpty_SqQueue(Q)){
		printf("顺序队列空!n");
		exit(0);
	}
	else{
		while(i < GetLength_SqQueue(Q)){
			printf("%dt",Q->data[j]);
			j = (j + 1) % MAXSIZE;
			i++;
		}
		printf("n");
	}
}

以上，就是循环顺序队列的另一种实现方法，也就是通过少用一个存储空间，和用计数器实现循环顺序队列的主要区别在判断队列满上。