![shequ.stmicroelectronics.cn](./template/st_v1/static/img/logo2.png)
本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 队列的概念% h0 F5 @. q1 S" { 在此之前,我们来回顾一下队列的基本概念:5 a& U5 G/ Y$ P1 Q- f1 e3 T 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。6 l2 X/ e0 ], u* c8 u; M 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 / H, I! k- J, c3 m" p队列的常见两种形式 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。 . F; N1 z6 S" i5 H, `* `2 A 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。 1 p1 A& H0 r! y2 I 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。 - {! a0 }9 }. a4 A+ t& m0 |! X: y R4 n% ? 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。- B8 q1 j V' ^( z/ p 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。1 Y$ g6 T5 `8 E( r 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。0 d8 N/ m# Z8 x" | 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:* Q2 ]( h: p1 y4 H |: ~9 l# `( r" x ①定义一个结构体:2 H+ O# y) p6 x/ @. u6 b' O 1typedef struct3 o; d9 S" Y' B% A 2{5 {- H+ Q6 R( e, x/ f 3 u16 Head; + g6 q" z2 }& [. {* I7 e8 _ 4 u16 Tail; 5 u16 Lenght;( W8 H) X3 p: H. ~ }% e F6 Q 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t; 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区; ?* J) A/ A0 h" w' E1 m- _ ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。/ ^" [8 c' n% |% ~ B 1/** 2* @brief RingBuff_Init 3* @param void0 V1 {4 A9 F2 ~2 T. U, L, }3 K$ c 4* @return void3 z( ?; L" M- ]1 M( i0 R' C3 v* ` 5* @author 杰杰5 Y! A( S: l5 W0 l 6* @date 20186 L1 J8 Y( B& w9 n. W2 x2 C 7* @version v1.0 8* @note 初始化环形缓冲区5 d2 q7 _9 T' A6 R X1 V; X% S* c 9*/2 z& Q3 M4 H0 Z* o: v* [ 10void RingBuff_Init(void) 11{ 12 //初始化相关信息5 M# f: T; ^- w' J! O+ E* s 13 ringBuff.Head = 0;& Y7 P i [ w) v3 t 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0;7 S; l8 V. [9 o, R8 v 16}9 Q. }7 m5 {8 w 初始化效果如下:+ t" }8 V& O3 Z7 u) o. [/ f 写入环形缓冲区的代码实现: 1/**" L9 h4 N2 `; _5 V- h) t3 U7 T 2* @brief Write_RingBuff: m& @4 b/ X7 }) C; o) L4 s6 E 3* @param u8 data/ {+ Q/ c- i' F" U. S& k 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功7 O- |' C) \# x& C& _ 5* @author 杰杰2 G+ Z/ B4 n0 S g( L 6* @date 2018- {" d7 X5 @- W4 B Q3 |8 o 7* @version v1.0( Q9 |" v7 B: p) c9 g* g) ?2 j 8* @note 往环形缓冲区写入u8类型的数据# a+ ^9 P5 o: M, M 9*/ 10u8 Write_RingBuff(u8 data)6 i5 O" {% _% O2 \0 @ 11{ 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满& ~5 S( b" h- _ 13 {8 Z6 i z- H9 q 14 return FLASE;/ L: S- v1 F; Y" o0 n8 A& u+ P8 J 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;+ n" d! V0 E7 D7 \. a) V 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++; k. B, r' r* P 20 return TRUE;/ N+ Q! e' O: ?; e: j 21}: d8 [/ H7 {+ b/ K8 k/ ^ }4 E 读取缓冲区的数据的代码实现: 1/** 2* @brief Read_RingBuff6 ^0 I/ [+ r1 v& m 3* @param u8 *rData,用于保存读取的数据 d# b' [0 m3 l; m) U 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰$ ^$ Q# r( j! s, {6 ] 6* @date 2018 7* @version v1.0& p c0 {9 B: M( R5 Q4 V9 U- { 8* @note 从环形缓冲区读取一个u8类型的数据 9*/ 10u8 Read_RingBuff(u8 *rData) 11{$ K# l( c0 T6 ^) Z/ z, X2 h" r 12 if(ringBuff.Lenght == 0)//判断非空) p9 ]- B; H: x0 i) r; d. U! _ 13 {5 Y# a; x9 x' G4 Y8 {& |7 S 14 return FLASE;0 e ]& G; k2 L 15 }) f9 i# k U7 W, H, l& V 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++; 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问- q( Q W( a4 C 19 ringBuff.Lenght--; 20 return TRUE; 21} 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。* R7 Q u# g4 w: Q5 X' l 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 1void USART1_IRQHandler(void) 2{ 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断: p9 ?- N6 u$ J' e4 O3 N* C2 ~ 4 {- u, |/ a& r5 B Q0 l, z+ l 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位; A8 J. Q9 ?! |& n 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据& K7 f6 T) G: @ 7 }. u- [2 |4 @2 H: b# ?/ r 8} 测试数据没有发生丢包现象 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF9 N- g; T' \+ @$ c1 L* o% P 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200* H( U) k& g. W 5#define FLASE 1 6#define TRUE 0 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData); 10#endif) Z5 r% C9 n1 K+ b9 q ) Z. |4 ~7 X. P; j+ b/ F 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 B! L! U0 L7 s0 k 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS3 L# f+ \- K* X+ Y 创客: 创客飞梦空间是开源公众号欢迎大家分享出去. H7 p3 D' w3 G( _% h) Z 也欢迎大家投稿- K q& W! A- t7 R" G3 { 2 q1 S4 w1 O' V/ U2 u$ D! x1 { |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
% r+ F5 U$ c6 q9 \ g5 a5 ~, @3 H
3 z% g* A: O4 H6 B
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{
fifo->in = 0;5 [) E1 _6 j/ }* ]5 V b+ \- Q
fifo->out = 0;- O6 V6 O" H" X
fifo->mask = 0;
fifo->data = buffer;8 {' W1 a. i) m5 y' W( @3 T! B
4 a# D: W1 k# r: b* c8 Q; w
if (size < 2) {* M1 v' X8 q/ M7 m& I; K
return -1;
}$ V7 x$ C5 _ b, q! w
1 Q# d+ ]. y( h) N3 `3 v5 T
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/
}
6 A+ f8 h3 D& i1 ?. I
fifo->mask = size - 1;4 {# T) a r# D/ h- B
9 f4 A9 p' K2 w' s+ E8 J
return 0;
}/ k/ S# i- C7 V: u' q1 p; |
$ j. i; [" g/ X" m) i5 X) i
2 Y" V1 s$ }* A7 W B2 Y+ p
+ v4 D& y( @# l& j8 ~7 a- a6 W
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)/ A: l& I5 `& z, G8 s [
{* h0 I+ ?! m8 u
, E7 @6 U4 j0 E
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )5 B# ?4 Q1 g6 m, H; n; x3 ]
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;; v% B( V1 a! n* j0 G7 i
& c" n! _; i- P) @0 P9 D& M4 u
return 1;. Z0 Y" g( P( O8 E
}7 V. U! h6 T# d5 m
! A+ ^* i4 z1 ]/ {" G
return 0;
}. w+ M) a, D6 N7 c0 |" E
1 |7 R' }5 B, i/ O! E ?
+ }2 ^( Q& N- ?# S
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p ) T/ a$ t5 ]1 o8 ?& }
{' r: x4 Q3 e9 U& ~2 z$ c
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;4 U# h1 t$ A& ^- s: b0 \& x
C1 c6 t8 O4 f2 ~% ?7 `
return 1;" D6 t7 E% J/ O! h% b
}
return 0;. g; A# H `& t' G9 g
}7 x. b3 G) W8 O9 c1 n' S
/ }+ X* h$ Z+ K% X
ok, 了解了解 U! e( |0 W5 {( Z6 A1 R
=========================================
看了源代码,
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.1 J, R" k& n' a) k: D
/ W8 L* E/ t% A' u( e. f
, E7 e/ m w" [2 z: j/ e: u/ N- m
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。9 e, ^. V- Z- X+ L- ?
一个暑假自学完一本数据结构课本,做完一本题库。
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻
: W& j) z" ]! T9 j9 ?& _3 ]
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构还是用处很大的!!!