本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 " ~9 M) [& X: `# t0 E- }: L7 F * y% W7 f9 [* K# ? 队列的概念 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。# P' U7 p4 a* `# y7 q+ q' m* U 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式 : S7 C2 p7 D; }( C4 N 普通队列 ]# A/ v0 o2 ~" n5 ^ 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。 3 h7 y2 z6 s. L" H% Z* S& M( ?% k 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。& L! w$ ?5 x0 t 环形队列 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 N4 i/ z6 d8 D. }1 D 队列头 (Head) :允许进行删除的一端称为队首。9 |* ~7 c d0 @. _- F 队列尾 (Tail) :允许进行插入的一端称为队尾。0 R7 d, t/ _2 y( P / `/ Z3 J7 C) C" K 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。( I6 I/ j4 }7 @5 Q! y5 e& j0 W+ y' A 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。. z; O$ W% I( N% F6 d$ x % S8 p3 T$ Z4 z/ G7 }8 e 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。" ~8 Y% o: J7 p' C& K! f3 A( p) ?# A 0 H, Y- y; u; k, b7 M% S 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:/ m' L0 Y0 E c3 T7 i# c ①定义一个结构体: 1typedef struct$ v$ a* n. ~% ~+ U, z) \ 2{- G/ Q0 l( Z; H4 m6 `& L) o 3 u16 Head; 4 u16 Tail;5 U: d5 g8 G+ o 5 u16 Lenght;: {; y3 A* i+ y8 k. {2 U 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t;# o- {0 f. ^7 _7 e+ m$ } 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区1 R4 C6 \1 t5 I' b; L ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/**. r! R% d) F+ s6 e; p* J. k3 f( ^ p 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰 6* @date 2018# Q& V0 K& Z( N- ^! {% b) E 7* @version v1.0 8* @note 初始化环形缓冲区 9*/ 10void RingBuff_Init(void)6 L# Q7 S# K; M 11{ 12 //初始化相关信息* }- `1 ~" d2 [ 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0;* M- h. F5 x( J# K! @/ ^! \4 m 15 ringBuff.Lenght = 0;/ q% ~9 N3 |8 S; Q0 G! d7 I6 L 16} 初始化效果如下: ( i- W# e3 f9 x7 @6 b 8 n; u p/ N' C5 r& Y+ M( R% y" U- Y 写入环形缓冲区的代码实现: 1/**6 H+ _+ u6 C, m. e! c4 A5 C 2* @brief Write_RingBuff 3* @param u8 data$ [+ }9 M7 K0 \' O* n' z 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功2 } _ S, G! @ 5* @author 杰杰. e/ k( P. H3 R9 u$ t 6* @date 2018, j" S- L; ]% H5 [2 Y: _ 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据 9*/" \# ]- `9 C9 n1 @! X. b" C- ~ 10u8 Write_RingBuff(u8 data) 11{ 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 {) l0 I2 s- z* i. ^! O7 v 14 return FLASE; 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data;& C' o6 f( p, I6 C( A' o5 w, ]! u 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++; 20 return TRUE;% V k1 | J6 ` { 21}% o7 T9 N( F9 D) ? 读取缓冲区的数据的代码实现: 1/**! v+ a8 K0 R2 `2 s' F4 d7 a- G 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰3 r* B# j3 f, z2 T 6* @date 2018 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/ 10u8 Read_RingBuff(u8 *rData) 11{0 j" x) n F# d1 A) B( { 12 if(ringBuff.Lenght == 0)//判断非空$ j; t+ {! j% V9 E- R& v 13 {6 S' Z: ?; r# A' ^ 14 return FLASE;0 R5 {6 |2 Z- F/ n 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++;4 A( |0 b+ B5 [/ ^- u. A3 I! _+ B 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght--; 20 return TRUE; 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。6 D6 `7 a. i3 y3 _6 l 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 那么在串口接收函数中: . K6 A6 Y9 U: W2 ~: @; M' E 1void USART1_IRQHandler(void) " w) _" q. e8 z0 c1 p h$ ?8 w 2{6 ^' i1 }- D. }* x" R 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断9 d0 q" W4 R+ P: u7 s8 Q 4 {* c: h, p8 v5 n4 I 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据3 D8 t# g! L; e# w 7 } 8}* @6 x2 v* q% l) @2 }7 u" M8 @1 n, w 测试效果' @1 r3 q) c0 Y 测试数据没有发生丢包现象, q1 J4 Y3 v3 d, z3 \. n 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。. N- H6 M; {% E$ } 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据) n' Q0 }( a, p( W$ U 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/: _1 I& v/ Q5 m$ I6 c2 ~ D 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200: h- O# ~! @ ]2 f3 P 5#define FLASE 1 ! i+ t- Q4 J, w1 n 6#define TRUE 0 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data);0 x' Z8 P& o, n! T$ ~ 9u8 Read_RingBuff(u8 *rData); 10#endif 7 H Q) Z# \3 V 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾创客: 创客飞梦空间是开源公众号4 W+ ]/ d7 u8 U" i& u( R欢迎大家分享出去 也欢迎大家投稿6 ]2 X4 W8 ?* g$ D1 r |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>' l W: e4 H- K. T; _
* N& A5 ?3 l5 P0 a C9 q3 b1 k
7 i `! F! J' l" j: ]. d1 h
7 v. U% d7 u" b. a) @2 F; e
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)! d9 g3 M: F3 l. f) S- g4 \; T
{& z' o" b+ @* j3 J
fifo->in = 0;6 D1 U" P' T7 ~
fifo->out = 0;2 U/ A, [( c# o2 v) ~6 n8 W: x
fifo->mask = 0;3 f( M/ Z: Y* q1 u
fifo->data = buffer;6 u. O8 `1 P) i. W2 ^
if (size < 2) {
return -1;
}! i( S6 `; ]/ t
if ((size & (size-1)) != 0)! F4 \& m$ e7 v2 G
{ s/ W$ E& i- y; h4 d4 }& p2 Z
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/$ i: t/ G: @% ?4 T+ I0 K
}
/ ~. @* `6 R$ m* Z
fifo->mask = size - 1;. Z: c$ m% d; I' u( p. D5 V M
4 v2 p! e% R: x* Q3 l& a- e3 N/ ?
return 0;
}
" w! @2 o$ ~- p) ^
$ P8 @6 S! ]. G9 r# M
3 Z" o' _: D4 i1 |* m# I6 p- M# U1 i9 t
+ y/ }( t/ f- y- \$ r1 X" N5 R
# [ s6 L# d# [- ]1 S* o7 Y
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)& B0 x/ C0 V" R
{
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;
return 1;( k5 V# k, q, x
}
1 c; q3 {% x+ Z1 E" E/ O, P4 ]" ]
return 0;+ b( P- w* o& X0 a/ j; [
}
- l( n1 P* ~6 Q8 M; U
5 Z' Z5 q3 ~+ | M4 _4 A
6 ?3 H7 Q* }: F& o5 c) M. e* W
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )4 r s- P7 w# N8 |
{
if( fifo->in != fifo->out )% B( q- g5 a# L+ D& l
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;
return 1;( h8 V4 Q) ]3 Q$ m! A1 R
}
* a& s6 [: v5 K4 a T; t+ P! S' w
return 0;
}
2 m" v s8 {9 I3 p5 N
: n5 @ {9 N/ h$ B
ok, 了解了解
=========================================
看了源代码, 4 r4 h' N' ]0 ?1 ]: f, S
; F' q' u$ Q$ F3 W4 B! y
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.& i+ e( }6 v( L. S/ k( D" Y$ A+ Q
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。
一个暑假自学完一本数据结构课本,做完一本题库。
1 {4 d& B1 t t! `
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!