LV010-顺序队列简介

一、顺序队列

1. 存储结构

顺序队列是一种顺序存储结构，它借助顺序表实现，由于我们需要在顺序表的一端实现入队，在另一端实现出队，所以需要两个 "指针"（为什么加引号呢？严格来说这两个并非是指针变量，而只是代表了顺序队列中指向队头元素和队尾元素所在数组位置下标的变量，一般是整型数据），来指向队头和队尾。

按照预想的情况应该是上图的这种结构， front 指向队头元素， rear 指向队尾元素的下一个位置（原因？只有指向下一个位置才能插入嘛，不然这个数据不就被覆盖了嘛，哈哈），接下来我们想象一下从数据入队到全部出队，会发生什么现象。假设有一个队列最大可以有 5 个元素，那么我们让 5 个数据入队然后再出队，然后来看一下最终的状态。

我们会发现入队的时候尾指针不断向后移动，出队的时候头指针也是不断向后移动，当 头尾指针重合时，队列中没有元素，为空队。那么问题产生了，这个时候这个队列是空的，但是队头和队尾已经移动到最后边去了，前边即便空间已经空出来了，由于队列的规则限制，这意味着前边的内存空间是无法使用了，重新申请一个内存空间嘛？显然不太可能喽。那有什么办法吗？可以这样想，我们让队头和队尾指针再重头开始不就行了吗？方案是可行的，那怎么实现呢？

现在要解决的问题就是如何让 front 和 rear 一直自加还能保证只在这 6 个元素的队列中循环，也就是说，不管这两个指针加了多少次，是最后的取值只能在 0-5 之间，这个时候可以想到，不是有个取余数的操作嘛，对 6 取余的话，最后得到的余数一定是小于 6 的，这样，这个问题就解决啦。那我们看看还会不会有问题。

绝了，循环倒是实现了，但是，队满的时候，头尾指针重合了，这不完了。这样的话，我不知道它是空是满，万一这个状态是满的，我又继续入队了，那数据不就没得了？这又怎么办呢？没办法，只好牺牲掉数组的一个数据啦，这样当 rear 到最后一个位置的时候就不能再入队了，因为再入一个数据就已经满队了，再经过规则限定，我们来看看最后的效果吧。

【总结】

（1） front 指向队头元素的位置; rear 指向队尾元素的下一个位置。

（2）在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。

（3）为区别空队和满队，满队元素个数比数组元素个数少一个。

2. 结构体实现

/* 宏定义 */
#define N 6   /* 定义队列的容量 */

/* 自定义数据类型 */
typedef int data_t; /* 定义栈中数据元素的数据类型 */

typedef struct 
{
	data_t data[N];  /* 用数组作为队列的储存空间 */
	int front;       /* 指示队头位置的指针 */
	int rear;        /* 指示队尾位置的指针 */
}seqqueue;           /* 顺序队列类型定义 */

【说明】顺序队列应为为 sequence queue ，所以后续使用 seqqueue 作为顺序队列结构体以及函数命名的关键字。

3. 顺序队列基本操作

相关源代码可以在这里下载：

数据结构	队列 (密码: 6sez)

3.1 创建

/**
 * @Function: seqqueue_create
 * @Description: 顺序队列创建
 * @param   : none
 * @return  : 返回一个地址
 *            NULL, 创建失败;
 *            other, 创建成功
 */
seqqueue * seqqueue_create() 
{
	/* 创建一个顺序队列结构体指针变量 */
    seqqueue *sq;
	/* 1. 申请内存空间 */
	sq = (seqqueue *)malloc(sizeof(seqqueue));
	/* 2. 判断是否申请成功 */
	if(sq == NULL)
	{
		printf("sequence queue malloc failed!\n");
		return NULL;
	}
	/* 3. 初始化申请的内存空间 */
	memset(sq->data, 0, sizeof(sq->data));
	sq->front = 0;
	sq->rear = 0;
	
	return sq;
}

3.2 释放

/**
 * @Function: seqqueue_free
 * @Description: 顺序队列释放
 * @param sq: 顺序队列地址
 * @return  : 返回一个 NULL
 *            NULL, 释放完毕
 */
seqqueue * seqqueue_free(seqqueue *sq) 
{
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return NULL;
	}
	/* 2. 释放结构体指针变量指向的空间 */
	free(sq);
	sq = NULL;
	printf("sequence queue free completed!\n");
	return NULL;
}

3.3 显示

/**
 * @Function: seqqueue_show
 * @Description: 顺序队列显示
 * @param sq: 顺序队列地址
 * @return  : 返回一个数值
 *            0, 显示完毕;
 *            -1, 顺序队列不存在或者队列为空
 */
int seqqueue_show(seqqueue *sq) 
{
	int i = 0;
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return -1;
	}
	/* 2. 判断顺序队列是否为空 */
	if(sq->front == sq->rear)
	{
		printf("sequence queue is empty!\n");
		return -1;
	}
	/* 3. 访问顺序队列中所有数据 */
	if(sq->front < sq->rear)
	{
		printf("sequence queue:");
		for(i = sq->front; i < sq->rear; i++)
		{
			printf("%d ", sq->data[i]);
		}
		puts("");
	}
	else
	{
		printf("sequence queue:");
		for(i = 0; i < N; i++)
		{
			if(i == sq->rear)
				printf("null ");
			else
				printf("%d ", sq->data[i]);
		}
		puts("");
	}
	
	return 0;
}

3.4 入队

/**
 * @Function: seqqueue_enqueue
 * @Description: 入队
 * @param sq: 顺序队列地址
 * @param value: 入队数据
 * @return  : 返回一个数值
 *            0, 入队成功;
 *            -1, 入队失败
 */
int seqqueue_enqueue(seqqueue *sq, data_t value) 
{
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return -1;
	}
	/* 2. 判断顺序队列是否已满 */
	if((sq->rear + 1) % N == sq->front)
	{
		printf("sequence queue is full!\n");
		return -1;
	}
	/* 3. 元素入队 */
	sq->data[sq->rear] = value;
	sq->rear = (sq->rear + 1) % N;
	
	return 0;
}

3.5 出队

【注意】这里出队的时候不要做队列是否存在以及是否为空的判断，这两个判断若是有返回值的话程序会认为返回值就是出队的元素，所以队列的存在性以及是否为空，要在使用出队函数前进行判断。

**
 * @Function: seqqueue_dequeue
 * @Description: 出队
 * @param sq: 顺序队列地址
 * @return  : 返回一个数据
 *            ret,出队数据
 */
data_t seqqueue_dequeue(seqqueue *sq) 
{
	/* 定义一个暂存队列元素的变量 */
	data_t ret;
	/* 1. 判断顺序队列是否存在 */
	/* 需要在函数外进行，这是因为该函数需要返回队列数据，队列数据也可能为这里的返回值 */
	/* 2. 判断顺序队列是否为空 */
	/* 需要在函数外进行，这是因为该函数需要返回队列数据，队列数据也可能为这里的返回值 */
	/* 3. 元素出队*/
	ret = sq->data[sq->front];
	/* 4. 更新队头指针 */
	sq->front = (sq->front + 1) % N;
	
	return ret;
}

3.6 空满

3.6.1 是否为空

/**
 * @Function: seqqueue_empty
 * @Description: 顺序队列是否为空
 * @param sq: 顺序队列地址
 * @return  : 返回一个数值
 *            0, 顺序队列非空;
 *            1, 顺序队列为空;
 *            -1, 顺序队列不存在
 */
int seqqueue_empty(seqqueue *sq) 
{
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return -1;
	}
	/* 2. 判断队头队尾指针是否重合 */
	if(sq->front == sq->rear)
		return 1;
	else
		return 0;
	/* 或者可以写成下边的形式 */
	// return (sq-> front == sq-> rear ? 1 : 0);
}

3.6.2 是否为满

/**
 * @Function: seqqueue_full
 * @Description: 顺序队列是否已满
 * @param sq: 顺序队列地址
 * @return  : 返回一个数值
 *            0, 顺序队列未满;
 *            1, 顺序队列已满;
 *            -1, 顺序队列不存在
 */
int seqqueue_full(seqqueue *sq) 
{
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return -1;
	}
	/* 2. 判断是否已满 */
	if((sq->rear + 1) % N == sq->front)
		return 1;
	else
		return 0;
}

3.7 清空

/**
 * @Function: seqqueue_clear
 * @Description: 顺序队列清空
 * @param sq: 顺序队列地址
 * @return  : 返回一个数值
 *            0, 顺序队列已清空;
 *            -1, 顺序队列不存在
 */
int seqqueue_clear(seqqueue *sq) 
{
	/* 1. 判断顺序队列是否存在 */
	if(sq == NULL)
	{
		printf("sequence queue is not existed!\n");
		return -1;
	}
	/* 2. 清空顺序队列 */
	sq->rear = sq->front = 0;

	return 0;
}