本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 c( i! p6 z X1 g 队列的概念 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 ^ w" Z" k7 K5 C5 V + d& ?; v. R% ]6 o/ [ 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式2 ~% [0 G8 H: x4 T 8 x7 L! S% B: |' R) K1 v' Q* }4 K# q8 i 普通队列 / i: O+ A% q) L- O 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 环形队列 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。& z; d) x! x5 l: Y( C 队列尾 (Tail) :允许进行插入的一端称为队尾。 }7 x1 M7 e3 s 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。5 @# S4 _: J! T- V7 I, J( `( Y / m" t9 W! y7 g3 c; q; z 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 ; Z7 T7 q. [; B% M 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。/ _8 ~0 u' K; U# k' g 4 a1 w' W# U0 C6 _6 ~- u% w* u: S 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现: 4 v: _$ G# C ^ ①定义一个结构体:1 k# p2 I9 G$ q0 V" ]5 h 1typedef struct' ^$ v6 o- } D8 U1 O1 ` 2{ 3 u16 Head; 9 w: ^# z; K# t7 Y: i% ]" ` 4 u16 Tail; 5 u16 Lenght;, T" q8 ~, V% D9 p7 J 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t; 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区5 S4 s$ ~% _4 p+ P 5 G6 M, Q& m, @; h' ]( t7 `/ c, G. c ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/** 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰 6* @date 2018 7* @version v1.0( s6 p1 J N; I- h' O 8* @note 初始化环形缓冲区; G4 n& n8 `( p S2 R 9*/ 10void RingBuff_Init(void) 11{ 12 //初始化相关信息 13 ringBuff.Head = 0;# }% {0 f- U* W 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0;/ ^: d: n& {, a2 S4 s 16} 初始化效果如下:1 U6 \$ T5 D0 {5 m- O/ C, L 5 k% l3 w; s( U* `5 b3 h 写入环形缓冲区的代码实现: 1/**4 E1 n; r0 _; P, Y" m 2* @brief Write_RingBuff4 K3 G5 r* F k/ `0 s" u/ w4 \ 3* @param u8 data/ T6 D& P7 b/ M4 W 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功& K; E" v1 l* P- R7 G 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据5 c8 M2 _: ]" T/ D 9*/' d' _ Z: O( I7 F6 U 10u8 Write_RingBuff(u8 data) 11{ 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 {3 j; j' c$ U- `4 {6 Q0 _$ O 14 return FLASE; 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data;5 |2 B2 J, B0 d" ? 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问2 z! ? T7 B2 h0 l 19 ringBuff.Lenght++; 20 return TRUE;* ^+ }- P9 f2 r7 C 21} 读取缓冲区的数据的代码实现: 1/**4 I; Z; t8 X, ~ 2* @brief Read_RingBuff' w/ }: b1 \ y7 G 3* @param u8 *rData,用于保存读取的数据6 l; H( w. k; ~* S& L. X v 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功8 C# b1 N p( v 5* @author 杰杰% C, X3 P `" N, y 6* @date 20185 O2 q) w8 k5 f1 q) o- p 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/6 n& v' f; K+ v0 ~0 T( M; S+ T 10u8 Read_RingBuff(u8 *rData) 11{ 12 if(ringBuff.Lenght == 0)//判断非空 13 { 14 return FLASE;/ E* Q; y$ P# W1 @# Z 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++; 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght--; 20 return TRUE;: q: Z; @, G2 z/ ?9 l1 q 21}对于读写操作需要注意的地方有两个:3 J8 B6 R2 ~' g& h3 W/ }( P 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 那么在串口接收函数中:7 g+ x8 Y! e9 \ : c! z6 j L2 t2 [9 f 1void USART1_IRQHandler(void) 2{ 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 {6 J) Q3 E$ `) h! k# O K 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据% C" }1 _ r2 F, \! P* ` 7 } 8} 测试效果5 g- a. K$ J; m' s9 U+ y$ y 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。' ~+ T+ B" o, a5 g7 Y+ m! q7 `, S 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据1 N3 w! B% U! ^3 g' V( N 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/9 I3 P2 W' ^/ n7 y) w1 C 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 ; ]( A% M3 ]* D. K% C 6#define TRUE 0 ! B' r0 P$ ~: G( g8 t 7void RingBuff_Init(void);! S9 X: ?! I0 C( C3 e 8u8 Write_RingBuff(u8 data);8 i5 n4 {+ T7 U! ?8 N' I) | 9u8 Read_RingBuff(u8 *rData); 10#endif 3 i* Z4 V2 [+ q P8 U8 A 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。: w& \/ H* d# u4 I2 L6 o/ g 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS: y; u* S& }& b% J 创客: 创客飞梦空间是开源公众号欢迎大家分享出去' z& F* E! Q% C9 C9 e4 J 也欢迎大家投稿 7 R& v/ E( ~$ {0 ~, o3 { |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>9 h+ D1 l' V h$ z3 O& z. y3 H
# y- W; t* P) z
" I1 @; c0 ^' P) q! n; e( n
9 `% ?. |# n, _* e5 w# v, ^
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{9 d8 k5 }6 o: H
fifo->in = 0;( I; U7 t" q! g4 F- n* g$ Q# [7 f
fifo->out = 0;
fifo->mask = 0;& h8 l( ~8 L* I+ u# k- C7 @* g
fifo->data = buffer;
if (size < 2) {
return -1;: x3 }" z& N- B% }8 K1 _% E6 Z
}1 S& \" E4 \ V: D+ B2 c& L5 E2 o j
if ((size & (size-1)) != 0)" _8 M+ f# h( F4 z6 M* E
{- V4 l' G6 x X' P% ?
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/
}/ l, \5 B3 S9 t
' R3 Y7 [4 I" r- v4 s5 T) L' ]
fifo->mask = size - 1;8 r# w) w+ ^$ q5 w
3 u, B( h4 A2 \" O; f8 T5 H
return 0;9 D0 A7 F+ i5 p* E5 i. a1 M, J
}) \, @9 v; X3 l2 u5 s9 a2 O$ ~
5 ^6 H/ g" _! u( Y: l: Z3 X5 q
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)+ X/ O8 ?+ `+ K; i0 c
{+ a6 l2 V3 D+ o ~9 Z
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{5 s: a5 W8 {0 `+ f
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;4 s4 m7 q- I0 O7 v
return 1;. ~1 e) g P7 E3 B# P
}
) w7 h- i. j5 L( @8 r
return 0;
}
( h6 _# K5 k) [4 b; d. B
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )5 O: ^: r) y; z0 B5 T; v/ ^4 ~
{( C+ n5 X7 U: i- |( I
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;# T8 f, a% L5 _ J/ i! d
return 1;9 U1 R7 F5 M1 v6 q! T# d v
}
& Z( J9 n0 ^4 w1 i! u% |# w' W
return 0;6 o+ l' w# h6 I
}1 q! H; B& Y* F- f& I
* B2 y9 L9 g+ I; A0 O: u
4 ]% p$ Q: _4 A" B
ok, 了解了解
=========================================( n6 A4 ]4 ~. t% R6 H: @6 b5 \, K
看了源代码,
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.& s+ D; _6 N5 _- s- p, k
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。3 _) o& m5 r5 _$ c
一个暑假自学完一本数据结构课本,做完一本题库。
" A a* F! V8 S4 \6 D+ y
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!