![shequ.stmicroelectronics.cn](./template/st_v1/static/img/logo2.png)
本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 ! }6 f" U6 ^+ C5 Z8 N 队列的概念9 ]5 N- C$ i, K$ [: t 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。2 w. W6 H% }9 q2 k( e- z 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。9 _4 r7 \! U7 k2 c+ S 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 ' k* O" @5 N4 B5 I5 n5 m 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。) A( V' T' M: b) ^ I j + {, D1 u+ j& {- p& _! X 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。/ @( p3 |5 Q3 o3 W6 t+ y 2 K: v7 {( s) B9 \6 ]9 a0 }% _# _ 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。. j: M! B8 O* h! ^3 ]; j7 | 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。& ]9 ~8 o R B 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:8 D u# G4 N; Z* R8 f% Q# b. F 8 Q+ _' Y0 f M( O! X ①定义一个结构体:" d1 C3 Y' F; c$ p/ E6 W 1typedef struct 2{ 3 u16 Head; 4 u16 Tail; 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN];; w1 a* g$ M- I: Y 7}RingBuff_t; 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区2 |# q. V1 r8 {. \: k1 L% v0 [ ; l1 [8 x( V8 k3 P& z ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。- e0 N: ?; ~! d 1/** 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰2 }1 j) I* T1 W 6* @date 2018& {( ], p$ K. R l0 u+ o 7* @version v1.0* O. y# \ s2 e/ I. q 8* @note 初始化环形缓冲区& c% v+ q& [, G: M7 y 9*/7 w6 e. I+ [# m3 Z0 W* k 10void RingBuff_Init(void) 11{ 12 //初始化相关信息 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0; 16}, f: Z( w# ^ s$ \" Y9 a+ `" [ 初始化效果如下:2 I6 l0 M2 D* \7 v2 Y 写入环形缓冲区的代码实现: 1/** 2* @brief Write_RingBuff 3* @param u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰 6* @date 2018! Y5 X4 r8 I Y( H( i 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据' K3 d4 A* q$ W3 ]# u0 D( A$ ^# G 9*/ 10u8 Write_RingBuff(u8 data) L5 N3 {$ c0 [4 M2 \) l 11{% B: x" ^$ m0 P& U2 R, D 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 { 14 return FLASE;. f% V7 U2 Q2 Z, c/ R 15 }! e5 x7 z- x! ]+ ? 16 ringBuff.Ring_Buff[ringBuff.Tail]=data;: E& `4 `+ w8 {. j; k" J) W& _; L- [ 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问/ }9 @ m8 W$ V9 l- D1 `4 w3 I/ _ 19 ringBuff.Lenght++; 20 return TRUE;; A9 M/ F- }+ g7 s5 k- V 21} 读取缓冲区的数据的代码实现: 1/** 2* @brief Read_RingBuff w5 n! o& C: e- P% e" T4 T 3* @param u8 *rData,用于保存读取的数据 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功: U( W3 B; {& `- w) W S8 g5 X8 F 5* @author 杰杰 6* @date 20181 K- U; s$ M+ g6 r2 s 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/% s0 o" c# t$ q) S; T 10u8 Read_RingBuff(u8 *rData) 11{/ z0 ?' `# j8 S( A9 c6 N 12 if(ringBuff.Lenght == 0)//判断非空 13 {+ D; P9 [" w8 O4 v" K1 d 14 return FLASE;3 ^' G9 x! t v2 O% A 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出/ P4 x& K% z G" m7 n 17// ringBuff.Head++;$ e/ p0 i w, o3 i" d 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght--;% M+ {7 H; m9 u" e+ @) o! C/ ^ 20 return TRUE; 21} 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。" {1 J& V' A+ L0 s6 N' e8 Q( r 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。, X/ d1 W$ X$ W0 ] 1void USART1_IRQHandler(void) % R% z; @* O' f4 n/ q1 q3 H 2{; {/ r3 S! W b. u+ B W0 B W 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断6 S2 i0 I- F& f# p4 `* h 4 {% H" u6 `7 G% C' x3 f: ? 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位& ]0 p- Z# q& u+ b1 f4 y 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据 7 } 8} 测试数据没有发生丢包现象2 p+ U4 `4 @& Q7 |" G 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据- c9 b3 _8 a6 T* I3 A2 i7 L 2#if USER_RINGBUFF4 p1 E: a4 y, D0 o0 d3 e 3/**如果使用环形缓冲形式接收串口数据***/( d { y# s# L 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200: }/ ?8 ]0 W* J+ n$ y1 j 5#define FLASE 1 L! ^) L, J0 ? 6#define TRUE 0 ) |+ s3 p" A5 V$ O$ k 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData); 10#endif 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS- N: [7 d8 @- ?4 S! _9 C$ z- _ 创客: 创客飞梦空间是开源公众号6 }; M2 d: z( ~) v3 a) o9 P欢迎大家分享出去 也欢迎大家投稿* p. ]9 j% u0 v- P7 j2 G# O' n " G( T c' Y$ d. l C7 L |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>* T" e+ g: u# ^" O% p
) B+ p7 o- {+ f2 F u, ], A
. ]) m1 Z3 F0 ~+ d( ?! C6 c5 A% X
) N) Q. b0 g5 g
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size). i% B$ [- T7 S
{
fifo->in = 0;, M A H1 t! K" O( X
fifo->out = 0;3 L& Y5 |7 U, S2 u
fifo->mask = 0;
fifo->data = buffer;
0 L! Q1 s, b+ G0 ]+ q
if (size < 2) {
return -1;
}
if ((size & (size-1)) != 0)
{ `2 R& W, b0 W) V8 `) D- W" q
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/( U- B1 E: b$ \' Y% o
}
, G S E3 _3 i; V, Q$ {$ N
fifo->mask = size - 1;
return 0;, P2 c' O! [( N1 ~$ u* O& p# w6 R' K: {
}7 i: j( o4 s1 t" |1 {
6 I( J. o4 a0 v: S
' v7 ^$ s+ P: X( b
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)
{+ ?8 l6 s- H' N, q+ n3 e+ O
. p$ I8 ]* ~( x
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;- E' E5 B' F; y
return 1;
}1 P/ x( A9 ^# s) d' U$ U! P0 p
return 0;
}
" x) T7 l, m3 l9 ]5 D
5 n$ y8 c% y! @) X8 i% }& K/ P
' Z0 i* _7 v% E1 Z: p
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )
{
if( fifo->in != fifo->out )
{8 A$ k+ j- Y& a, }
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;4 ]$ z f& M1 Q& T# J
% r* I- x3 u9 U9 J& k% J
return 1;
}
' v9 S7 y6 D, _, Z W: L: G
return 0;7 O! \4 c0 V) x0 U; C3 v
}$ b. e; b/ A. s) n6 @
ok, 了解了解! e1 G$ p& D9 [: _
=========================================- z. ?3 C4 a# z& S& b' \2 g
看了源代码, * R8 b+ R) o7 R% h
. P+ q# L' n7 m' P- D7 Q
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看." y4 i. P2 f8 C, r1 P# C
! x' g. T4 O* P6 J
' g7 ]( ?, \2 x
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。
一个暑假自学完一本数据结构课本,做完一本题库。
2 v9 G; P& i3 f/ }, Q+ j$ @1 \5 }+ ?
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻
. u( J# x2 T7 c
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构还是用处很大的!!!