嵌入式常用数据结构------队列操作简介
发布时间:2014-10-8 16:03
发布者:edu118gct
队列是嵌入式软件中常用的一种数据结构。什么是队列呢?在生活中,我们都知道 ,买东西时要排队,比如最近iphone6开售了,买的人比较多,黄牛倒手机也要排队 买。先来的人排在队伍的前面,优先购买,购完后离开,后到的人只有排在队伍的 后面,且只有等前面的人都买好了才能轮到他。这种队伍的变化状态称为数据结构 。 今天我们就来聊一聊队列的使用及主要运算。队列只能在一端(队尾)进入数据加 入,在另一端(队首)进行删除的数据结构。比如对于队列(d1,d2,d3,…,dn),d1 是队首,如果要从队列中删除数据,只能从d1开始,如果要向队列中添加新的数据 ,只能在队尾加入。 队列可以通过一维数组实现,也可以通过链表来实现,我们以使用数组来说明。比 如我们可以定义一个数组a[100]表示最大长度为100的队列。当向新建的队列中加入 数据时,从a[0]开始,然后记录加入的位置,当再次向队列中加入数据时,存放在 a[1]中,依次类推。假如一直向队列中加入数据,当向a[99]加入了数据之后,队列 满了。不能在之后继续加入新的数据。假如现在需要从队列中取数据,要从a[0]开 始,下次取a[1],依次类推。 这样使用的数组,如果不进行一些其他的运算,数组最终会被用完。一般我们在使 用时,当队尾达到数组结尾时,将队尾重新指向数组的开始,这样的队列称为循环 队列。 在使用队列时,主要会涉及到以下运算。 1、置空队列:将队列置成空的队列。 2、判断队列是否空:如果队列是空队列,返回真,否则返回假。 3、取头结点:读取队列中头结点的值,队列中的结点保持不变。 4、入队:将数据插入到队列的队尾。 5、出队:删除队列头结点,一般与从队列中取队首数据同时操作。 队列空和满的情况分析 对于循环队列来说,假如取数据和添加数据同时进行,会存在队列空或者队列满的 情况,假如用front来表示队首在数组中的下标,用rear表示队尾在数组中的下标。 会存在front和rear相等的情况,在这种情况下,只用front和rear的值将无法区分 当前队列是满还是空。 通常我们可以设置一个标志位来表示队满还是队空,当入队时设置flag等于1,出队 时设置flag为0,出队时设置为0,所以当front和rear相等时,flag等于0则队空, 否则队满。深圳-郑州-广州-长沙嵌入式技术实训学习,小班授课,详情郭老师 QQ754634522 或者使用一个计数器来记录队列中结点的数量。当计数count等于0时队空。 同样我们也可以少用一个节点,将front指向的空间表示为无数据。当front等于 rear时,队空,入队时,当尾指针加1,等于头指针,则说明队列已满。 下面我们使用第三种方法表示队满或队空,来详细分析一下队列的运算 1、置空队 在队列初始化时,我们需要将队列置为空的队列,当然也可以通过置空队列也删除 队列中的数据(不是真正意义上的删除,只是数据无效,可以覆盖操作)。 将数组下标0位置设置为不使用,因此头尾指针值都是0 void set_null(sequeue *q) { q->front = 0; q->rear =0; } 2、判断队空 使用前面的最后一种方法,队空的判断条件就是头指针等于尾指针 int empty(sequeue *q) { if(q->rear == q->front) return 1;//空队列返回真 else return 0;//非空返回假 } 3、取头结点 取出头结点,并不删除头结点,队列信息保持不变,如果是空队,就提示相关信息 。 get_front(sequeue *q) { if(empty(q) { printf(“null\n”);return NULL; } else return q->data[(q->front+1)%maxsize];//返回头结点 } 4、入队 入队时,将新结点插入到队尾,队尾指针加1,但要考虑从数组最大下标到0的情况 ,还有队满不能入队的情况 int in_queue(sequeue *q,data x) { if((q->rear+1)%maxsize==q->front) return NULL; else { q->rear = (q->rear+1)%maxsize; q->data[q->rear] = x; } } 5、出队 出队进行与入队相反的操作,要删除队列中的头结点。 data del_queue(sequeue *q) { if(empty(q) return NULL;//返回空指针 else { q->front = (q->front+1)%maxsize; return q->data[q->front]; } } 在实际应用中,队列使用的比较多的地方是操作系统内核,当系统任务比较多时, 需要等待的情况一般都会使用到队列,在裸机开发中,我们也可以使用队列,比如 使用队列来处理触摸屏坐标,当点击速度过快,或者触摸屏划动操作时,需要一直 记录划过的坐标,这时,如果主循环处理不完,就需要构造队列。想学习嵌入式伙伴可以加群交流132621831 |
网友评论