[嵌入式]C语言数据结构Queue----循环队列

前言

无论是单片机还是MCU设备，数据处理应用中经常要使用FIFO队列，而Queue循环队列就是最经典、最基础的数据结构应用。
通过大学学习的数据结构导论，结合自己的项目实践，用C语言描述和实现了循环队列的功能。

一、基本概念

1、队列的定义

• 队列简称队，也是一种运算受限的线性表，其规则允许在线性表的一端插入数据，另一端删除数据，插入数据的一端叫做队尾(rear)，删除的一端叫做队首(front)。
• 新插入队尾数据的动作叫入队，从队首删除数据的动作叫做出队。出队后，它的后继元素数据将成为新的队首，如果后继数据为空，队列将为空队列。由于队列的插入删除动作在不同一端进行，每个元素一次进入和离开，因此队列也称作先进先出表。

2、循环队列的特点

• 循环队列的利用了数学上的求模运算，将重复的长度存储空循环利用，逻辑上就形成了一个循环表。当maxSize-1的位置使用后，入队的下一个元素将进入第一个0号空间位置。
• 同样因为是循环使用位置空间，解决了顺序列表中的假溢出问题。

3、队列状态过程

• 初始状态
  初始队列状态时，队列的数据头指向和数尾的指向-1 也就是未开始状态，即：(Q)->front = (Q)->rear = -1 。
  

• 入队4个元素
  数据元素ABCD按照次序，依次进入队列填满位置，这个时候，未出过数据front数据头就仍指向-1位置，因为入队4个数据，rear数据尾就指向3位置（-1+4=3）。

• 出队2个元素
  出队两个数据，即将A和B数据出队，位置0和位置1将为空数据，front将指向位置1（-1+2=1）位置0位置1数据为空。因为没有数据出队，rear队尾仍然指向位置3（数据D）。

• 再出队2个人元素
  因为再次出队列2个元素，CD将不在队列中，整个队列中将为空，front再次后移2个位置指向位置3，因为没有数据入队，rear也还是指向位置3。

二、代码实现

1、代码说明

• MAXSIZE决定了队列的空间长度。也就是前面说到的位置的总数量。
• ELemType是队列中的一个元素，可以使自定义的任何结构体，这里我定义了一个1024大小的字符数组，以及一个短整型COM值，COM值方便我在项目中存数据编号。
• 入队时，我们要先判断数据队列是否溢出，可以看到溢出条件为两个：一种是只出不进，堆满溢出，另一种是有进有出，直到尾巴加一后就是队首，为溢出。
• 出队则是要先判断队列中是否为空。
• 在某一时刻，我们可以查询读取队列中的所有位置或者某个位置的元素或值。

2、 代码描述

 
//#################################################
//############# C数据结构 -- 循环队列 ##############
//#################################################
//队列位置总数量
#define  MAXSIZE 20
//队列单个元素结构体
typedef  struct 
{
	uint8_t data[1024];
	uint8_t com;
}ELemType; 

//队列结构体
typedef  struct 
{	
	ELemType queue[MAXSIZE];
	int8_t front,rear;	
}queuetype;


//################## 队列初始化 ##################//
void  init_queue(queuetype *Q)
{
		Q->front = Q->rear = -1;
}
//################## 入队列 ##################//
void  enter_queue(queuetype *Q, ELemType x)
{
		//只入队不出队时，到最大数量时溢出
		if ( Q->front == -1  && (Q->rear+1) == MAXSIZE )
		{
		    printf("溢出！EER1\n");
		}
		//取余刚好等于队列头时为溢出
		else if ((Q->rear+1) % MAXSIZE ==  Q->front)
		{
			printf("溢出！EER2\n");
		}
		//正常入队
		else  
		{
			Q->rear = (Q->rear+1) % MAXSIZE;//位指针累加后移
			Q->queue[Q->rear] = x;//新元素复制赋值给队列尾单元
		} 		
}

//################## 出队列 ##################//
void  delete_queue(queuetype *Q)
{
		//front头等于尾时，队列为空
		if ( Q->front ==  Q->rear )
		{
			return;
		}
		Q->front = (Q->front+1)%MAXSIZE;
	    printf("出队！\n");	
}

//################## 取队首元素 ##################//
ELemType  gethead( queuetype *Q)
{  			
	 	return  (Q->queue[(Q->front+1)%MAXSIZE]);
}

//################## 判断队列中是否为空 ##################//
int  empty(queuetype *Q)
{		 
		if ( Q->front ==  Q->rear ) 
		{			
			return 1;//队列为空
		}
		else  
		{			
			return 0;//队列不为空
		}
}	
		
//################## 显示队列中所有COM数据 ##################//
void  display_all(queuetype *Q)
{
		int i = Q->front+1;
		if(!empty(Q))
		{
			while(i % MAXSIZE != Q->rear)
			{
				printf("%d ",Q->queue[ i++ % MAXSIZE ].com );
			}
			if (Q->rear != -1 )
			{
				printf("%d ",Q->queue[ i % MAXSIZE ].com );//显示队尾
			}
		}		
}

//##################  查询队列元素COM ##################//
int check_all_for_com(queuetype *Q, int8_t comNumber)
{
		int i = Q->front+1;
		
		if(!empty(Q))
		{			
			while(i % MAXSIZE != Q->rear)
			{
				if (comNumber== Q->queue[ i++ % MAXSIZE ].com)
				{
					return 1;								
				}
			}
		}		 
		return 0;
}