我是靠谱客的博主 呆萌手套,最近开发中收集的这篇文章主要介绍数据结构之.队列,循环队列,链式队列(一),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

队列你真的懂了吗?队列用来干嘛?什么场景用队列有优势?

一、循环队列

颜色说明如下:
在这里插入图片描述
假设有一个空队列,长度为len = 10 fornt对头,rear队尾初始化时,指向0位置。
注意,这里指向可不是指针的意思,就是front = =rear == 0。
在这里插入图片描述
向队列写入1个数据,rear队尾向后移动一个位置,此时,front == 0,rear = rear + 1,也就是 rear == 1。在这里插入图片描述
继续向队列写入9个数据,rear队尾向后移动一个位置,此时,front = 0,rear = 9。如果是传统队列,此时是不能再写入数据了,rear 不能等于10。
在这里插入图片描述
队列里有9个数据,此时为非空,读走5个数据,此时,front == 5,rear == 9, rear - front == 4。如果是顺序队列,再写数据,此时是从5位置写入数据,前面5个就浪费了。
在这里插入图片描述
队列里有4个数据,此时为非空,再写入1个数据,此时,front == 5,rear =rear + 1, rear == 0。如果是传统顺序队列,
rear - front 是 < 0,不可操作的,不允许再写入,但是本文研究设计的循环队列,是可以写入的,如下。
在这里插入图片描述
再继续看下面。继续写入3个数据,红色为队列满之后写入的数据,此时,front== 5不变,rear == 3,没啥问题啊,为啥前人,会发明顺序队列,是因为不可判断队列数据个数吗,rear - front < 0,是不可以判断的,但是,可不可以增加一种判读机制呢,引入一个count,记录数据个数,每次增加一个数,就加1,读走一个数,就减1。上面步骤最开始是写1个数,count == 1,再写入8个数,就是是9个数,再读走5个数,就还剩4个数,再写入一个数,就是5个,最后,下面步骤,写入3个数,就是8个数,下图,红色和绿色都是代表有数据,刚好是8个数。
在这里插入图片描述
再继续分析如下,读走一个数,front队头向后移动一个位置,还剩7个数。
在这里插入图片描述
再继续读走3个数到最后一个位置,此时,还剩4个数,继续读,会怎么样?
在这里插入图片描述
继续读,如下,队头又回到队尾前面了,此时count == 2。front == 0,rear == 3。
在这里插入图片描述
读走最后两个,此时,front == rear == 3,空队列。
在这里插入图片描述
再来分析,和我们最开始的队列,front == rear == 0,有啥区别?也是空对列,好像是 front == rear,,只是位置在0和3,但是都是队头队尾相等,没有数据的空队列。,此时可以根据front == rear来判断空队列下结论吗?
在这里插入图片描述
继续看,如果把队列都写满,此时,front == rear,为满队列,和上面的空队列一样的情况,所以,不能只靠这个条件进行判读,我们可以加入一个判断条件,count
如果count == 0,且front == rear,则为空队列,如果count != 0,front == rear,为满队列。
在这里插入图片描述
到这里结束了?但是有个毛病,满之后,再继续写,会怎么样?如下图,再写入3个数据,原来是10个,加3个,本来是10+ 3 == 13,现在是把10个满队列的数,前面3个覆盖掉,那不是丢失数据了,就算不考虑丢失的问题,此时要去读取数据时,front == 0,读第0个数,现在读出来的是第11个位置数据,也就是第11个位置的数,而不是被覆盖之前的第0个位置数据,这显然不符合先进先出的思想,因为最现在被覆盖后,最新的数据应该是从第3个数据开始的后面一段数据。
在这里插入图片描述
所以,我们要做一个改进,当队列已满时,不再允许写入数据,只有再次为空时,才允许写入数据。
如果我们希望,可以覆盖,真正实现循环,就需要做如下改进,把队头移动到队尾,front == rear,不关心数据丢失的问题,只希望数据是最新的数据。
在这里插入图片描述
如下,验证设计的正确性,读取2个数据,此时front = front + 2,front == 5。完全正确,为了验证安全性,可以写代码
增加长度,和轮询次数,本文没有验证过,只是理论研究。
在这里插入图片描述
**总结;
1、传统的循环队列其实没有实现真正的循环队列,只是队头队尾可以循环移动,此时可以只根据

front == rear 来判断空。
front== ( rear + 1)% len 来判断满队列。

但是本文真正实现了数据循环覆盖,循环队列。列外判断机制加入了count,与别人有所区别。
1、满队列时,如果希望不覆盖前面的数据,防止数据丢失,可以加判断,满队列将不被允许写入,直到不满。
2、满队列时,如果希望,实现循环写入,将可以通过移动队头到队尾,将数据覆盖。
以上设计,各有各的用处场景,不能说哪个好,场景不同,就要选用不同的方式。**

demo代码:

#include"queue_cmd.h"

PT_QUEUE_CMD QUEUE_CMD_Open(SX_S32 depth)
{
	PT_QUEUE_CMD handle = (PT_QUEUE_CMD)xine_xmalloc(sizeof(T_QUEUE_CMD));
	if( handle == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return NULL;
	}
	
	if (pthread_mutex_init( &handle->mutex, NULL ) != 0)
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		QUEUE_CMD_Close( handle );
		return NULL;
	}
	
	if( pthread_cond_init(&handle->cond, NULL) != 0 )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		QUEUE_CMD_Close( handle );
		return NULL;
	}
	
	handle->ptCmd = (PT_NET_Pkt)xine_xmalloc(sizeof(T_NET_Pkt) * depth);
	if( handle->ptCmd == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		QUEUE_CMD_Close( handle );
		return NULL;
	}
	
	handle->s32QueueDepth = depth;
	handle->s32IndexR = 0;
	handle->s32IndexW = 0;
	handle->s32Count = 0;
	handle->bAbortRequest = SX_FALSE;
	
	return handle;
}

void QUEUE_CMD_Close( PT_QUEUE_CMD handle )
{
	if( handle )
	{
		if( handle->ptCmd )
		{
			xine_freep(  (void *)&(handle->ptCmd) );
		}
		
		pthread_mutex_destroy( &handle->mutex );
		pthread_cond_destroy(&handle->cond);
		
		xine_freep(  (void *)&handle);
	}
	return;
}

SX_S32 QUEUE_CMD_Send( PT_QUEUE_CMD handle, PT_NET_Pkt cmd)
{
	if( handle == NULL || cmd == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return -1;
	}

	pthread_mutex_lock( &(handle->mutex) );
	
	if(  (handle->s32IndexW + 1) % handle->s32QueueDepth == handle->s32IndexR) //&& (count> 0) )
	{
		pthread_mutex_unlock( &(handle->mutex) );
		//TRACE(DL_WARNING, "queue fulln");		//tx bus_send_cmd fifo is always full in working phase
		return 0;
	}
	
	PT_NET_Pkt ptCmd = handle->ptCmd + handle->s32IndexW;
	
#if	1
	*ptCmd = *cmd;
#else
	memcpy( ptCmd->szSync, cmd->szSync, sizeof(ptCmd->szSync) );
	ptCmd->s8ChNo		= cmd->s8ChNo;
	ptCmd->s8CmdIndex	= cmd->s8CmdIndex;
	ptCmd->s16CmdPeriod	= cmd->s16CmdPeriod;
	ptCmd->s8LibIndex	= cmd->s8LibIndex;
	ptCmd->u8CmdLength	= cmd->u8CmdLength;
	ptCmd->s8CmdFormat	= cmd->s8CmdFormat;
	memcpy( ptCmd->szReserved1, cmd->szReserved1, sizeof(cmd->szReserved1) );
	memcpy( ptCmd->szCmd, cmd->szCmd, MIN(ptCmd->u8CmdLength, sizeof(ptCmd->szCmd)) );
	
	ptCmd->s32StatusLength = cmd->s32StatusLength;
	memcpy( ptCmd->szStatus, cmd->szStatus, MIN(ptCmd->s32StatusLength, sizeof(ptCmd->szStatus)) );
	ptCmd->s32LastTime	= cmd->s32LastTime;
	ptCmd->s32Sn		= cmd->s32Sn;
	ptCmd->ptBk			= cmd->ptBk;
	ptCmd->ptCh			= cmd->ptCh;
	ptCmd->ptCmd_Myself = cmd->ptCmd_Myself;
	ptCmd->next			= cmd->next;
#endif
	
	handle->s32IndexW = (handle->s32IndexW+1) % handle->s32QueueDepth;
	handle->s32Count++;
	
	pthread_cond_signal( &handle->cond );
	pthread_mutex_unlock( &handle->mutex );
	return 1;
}

SX_S32 QUEUE_CMD_Receive(PT_QUEUE_CMD handle, PT_NET_Pkt cmd, SX_BOOL block)
{
	if( handle == NULL || cmd == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return -1;
	}
	
	SX_S32  	ret;
	pthread_mutex_lock( &(handle->mutex) );

	for (;;)
	{
		if (handle->bAbortRequest)
		{
			ret = -1;							 // 异常
			break;
		}

		if(( handle->s32IndexW == handle->s32IndexR) //&& ( _s32Count == 0 ))	//empty		
		{
			if ( !block)						// 阻塞标记,1(阻塞模式),0(非阻塞模式)
			{
				ret = 0; 						// 非阻塞模式,没东西直接返回0
				break;
			}
			else
			{
				pthread_cond_wait(&handle->cond, &handle->mutex);
			}
		}
		else
		{
			PT_NET_Pkt ptCmd = handle->ptCmd + handle->s32IndexR; //指针 == 队头,加索引,
#if 1
			*cmd = *ptCmd;
#else
			memcpy( cmd->szSync, ptCmd->szSync, sizeof(cmd->szSync) );
			cmd->s8ChNo			= ptCmd->s8ChNo;
			cmd->s8CmdIndex		= ptCmd->s8CmdIndex;
			cmd->s16CmdPeriod	= ptCmd->s16CmdPeriod;
			cmd->s8LibIndex		= ptCmd->s8LibIndex;
			cmd->u8CmdLength	= ptCmd->u8CmdLength;
			cmd->s8CmdFormat	= ptCmd->s8CmdFormat;
			memcpy( cmd->szReserved1, ptCmd->szReserved1, sizeof(ptCmd->szReserved1) );
			memcpy( cmd->szCmd, ptCmd->szCmd, MIN(cmd->u8CmdLength, sizeof(cmd->szCmd)) );
			
			cmd->s32StatusLength = ptCmd->s32StatusLength;
			memcpy( cmd->szStatus, ptCmd->szStatus, MIN(cmd->s32StatusLength, sizeof(cmd->szStatus)) );
			cmd->s32LastTime	= ptCmd->s32LastTime;
			cmd->s32Sn		= ptCmd->s32Sn;
			cmd->ptBk			= ptCmd->ptBk;
			cmd->ptCh			= ptCmd->ptCh;
			cmd->ptCmd_Myself 	= ptCmd->ptCmd_Myself;
			cmd->next		= ptCmd->next;
#endif			
			handle->s32IndexR = (handle->s32IndexR + 1) % handle->s32QueueDepth;
			if( handle->s32Count > 0 )
			{
				handle->s32Count--;
			}
			ret = 1;
			break;
		}
	}
	
	pthread_mutex_unlock( &(handle->mutex)  );
	return ret;
}

void QUEUE_CMD_Abort(PT_QUEUE_CMD handle) 
{
	if( handle == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return;
	}
	
	pthread_mutex_lock( &(handle->mutex) );
	
	handle->bAbortRequest = SX_TRUE;
	
	pthread_cond_signal(&handle->cond);
	pthread_mutex_unlock( &handle->mutex);
	
	return;
}


void QUEUE_CMD_Flush(PT_QUEUE_CMD handle)
{
	if( handle == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return;
	}
	
	pthread_mutex_lock( &(handle->mutex) );

	handle->s32IndexR	= 0;
	handle->s32IndexW	= 0;
	handle->s32Count	= 0;
	
	handle->bAbortRequest = 0;
	
	pthread_mutex_unlock( &(handle->mutex)  );
	return;
}

//queue_cmd.h

#ifndef QUEUE_CMD_H_
#define QUEUE_CMD_H_

#include "global.h"

#pragma pack(1)
typedef struct UART_Pkt
{
	SX_U16	u16SyncHead;		//EB90/AABB
	SX_U8	u8Cmd;
	SX_U8	data[120];			//
} T_UART_Pkt, *PT_UART_Pkt;
#pragma pack()

#pragma pack(1)
typedef struct NET_Pkt
{
	//net head 
	SX_U8		u8Ch;
	SX_U8		u8Reserved1;
	SX_U8		u8Reserved2;
	SX_U8		u8Reserved3;
	SX_U32 		u32TimeStamp;
	
	//uart pkt
	T_UART_Pkt	tUartPkt;
} T_NET_Pkt, *PT_NET_Pkt;
#pragma pack()

typedef struct QUEUE_CMD{
	PT_NET_Pkt 	ptCmd;
	
	SX_S32		s32QueueDepth;
	SX_S32  		s32IndexR;
	SX_S32  		s32IndexW;
	SX_S32  		s32Count;

	SX_BOOL		bAbortRequest;
	pthread_mutex_t	mutex;
	pthread_cond_t 	cond;
}T_QUEUE_CMD, *PT_QUEUE_CMD;

extern	PT_QUEUE_CMD 	QUEUE_CMD_Open( SX_S32 depth );
extern	void 				QUEUE_CMD_Close( PT_QUEUE_CMD handle );
extern	SX_S32 			QUEUE_CMD_Receive(PT_QUEUE_CMD handle, PT_NET_Pkt cmd, SX_BOOL block);
extern	SX_S32 			QUEUE_CMD_Send( PT_QUEUE_CMD handle, PT_NET_Pkt cmd);
extern	void 			QUEUE_CMD_Abort( PT_QUEUE_CMD handle );
extern	void 			QUEUE_CMD_Flush( PT_QUEUE_CMD handle );
#endif /* QUEUE_CMD_H_ */

QUEUE_Frame_Open(100);
//下面是读写对列的操作,当网络端有数据发过来时,写对列,并读队列,例外数据类型可不是int一个字节
//太low了,我是结构体套结构体的类型,把这个结构体理解成一个数据类型,使用指针指定的方式赋值,

SX_S32  Frame_Receiver_Rcv(PT_Receiver handle, void *buf, SX_S32 timeoutMs )
{
	if( handle == NULL )
	{
		TRACE(DL_ERROR, "DL_ERRORn");
		return 0;
	}
	SX_U8 *pDst = NULL;
	SX_S32 ret, sret, retval;
	SX_S64 max_fd;
	fd_set readfds;
	struct timeval tv;
	int i  = 0;
	FD_ZERO(&readfds);	
	FD_SET( handle->sockfd, &readfds );

	max_fd = handle->sockfd;	
	tv.tv_sec  = timeoutMs/1000;	
	tv.tv_usec = (timeoutMs%1000)*1000;	
	
	retval = select( max_fd + 1, &readfds, NULL, NULL, &tv );
	if ( retval > 0 )
	{
		if( buf ){
			sret = recvfrom( handle->sockfd, (SX_S8 *)buf, UDP_MAX_LEN, 0, (struct sockaddr *)&(handle->cliaddr), &(handle->cliaddr_len) );
		}
		else{
			sret = recvfrom( handle->sockfd, handle->pszRecvBuf, UDP_MAX_LEN, 0, (struct sockaddr *)&(handle->cliaddr), &(handle->cliaddr_len) );
			handle->s32RecvLen = sret;
		}
		
		if ( sret > 0 )
		{
			ret = sret;
			pDst = (SX_U8 *)&handle->FrameSendQueue.data;
			memcpy( (SX_S8 *)pDst, (SX_S8 *)buf,sret);

			//printf("+       recvfrom   %ld  +rn",sret);
			if(handle->ptFrameQueue == NULL || &(handle->FrameSendQueue) == NULL)
				return -1;
			QUEUE_CMD_Send(handle->ptFrameQueue,&(handle->FrameSendQueue));
            
			//tset
			QUEUE_CMD_Receive(handle->ptFrameQueue,&(handle->FrameRcvQueue),1);
			for(i = 0; i< sret;i++)
			printf("%x",handle->FrameRcvQueue.data[i]);
			printf("rn");
		}
		else
		{
			ret = 0;  // no data;
		}
	}
	else if ( retval == 0 )
	{
		// timeout		
		ret = 0;
	}
	else
	{
		// error		
		ret = -1;
	}
	
	return	ret;
}

上面的例程,数据是不允许被覆盖的,因为本例程的数据不能被丢失,所以是按传统的写法,只移动队尾队头,实现传统循环对列。
例外判读非空,非满,也是按传统没有加入count机制,在研究了别人的写法,发现确实是多此一举。

如果要按本文上面研究,实现数据循环可覆盖的,也就是写满后,允许写入数据,可以自己改下,在判断满队列时,增加,队头 == 队尾的操作。

说明:
r + 1和w+ 1,是因为最后一个位置是len -1 ,如10个,队尾只能最大到9,
如果满队列再写入, 此时队尾位置是(9 + 1)%10 == 0,也就是0位置。

队列,在多线程通信时,是很有用的,涉及互斥,竞争,加入条件变量来约束,例外,本文例程,不是写入单个数据,而是通过指针,队头的指针,加索引,也就是队尾的索引值,每次读写取最后一个队尾的地址,指向一段存有数据的内存,实现数据的写入,读取,传统的写法是,是将所有数据复制写入,这种写法太low了,当有大数据了,很影响读写速率。

最后

以上就是呆萌手套为你收集整理的数据结构之.队列,循环队列,链式队列(一)的全部内容,希望文章能够帮你解决数据结构之.队列,循环队列,链式队列(一)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(50)

评论列表共有 0 条评论

立即
投稿
返回
顶部