电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 嵌入式常用数据结构------队列操作简介 [打印本页]

作者: edu118gct 时间: 2014-10-8 17:44 标题: 嵌入式常用数据结构------队列操作简介

队列是嵌入式软件中常用的一种数据结构。什么是队列呢？在生活中，我们都知道
，买东西时要排队，比如最近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

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)