分类： C/C++
2015-09-29 14:52:28
用数组实现循环队列时会碰到如何判断队列满和空两种状态，一种方法是直接在队列结构体中添加一个 queue_size和curr_size两个元素来判断队列的满和空。
Struct queue{
TYPE buff[SIZE]; //模拟队列的数组。
Unsigned int read_pos;
Unsigned int write_pos;
Unsigned int queue_size;
Unsigned int curr_size;
}
那么判断队列的空满就很简单。 Queue_size==curr_size时队列就是满，curr_size==0就是空。
另一种的实现是不需要curr_size变量，通过牺牲一个数组的单元来判断队列的空和满，即(write_pos+1)%queue_size==read_pos 表示队列满。Write_pos==read_pos时表示队列空。
第二种方法更能体现循环队列的‘循环’特性。
不过这两种方法都有一个弊端，就是无论何时对read_pos和write_pos的增操作都需要做模运算。 即 read_pos=(read_pos+1)%queue_size。或者是不做模运算但是每次增操作都需要判断是否”溢出”，是便赋值为0。
这里还有第三中方法。不过这个方法也不是完美的。它的唯一的要求就是队列的大小需要是2的n次幂。 但是他不需要第一种方法需要一个curr_size或者第二种方法的少用一个数组单元来判断队列的空和满，同时更重要的避免的模运算(相当慢的操作)。
实现如下
Struct queue{
TYPE buff[SIZE]； //size为2的n次幂(n大于0)
Unsigned int write_pos;
Unsigned int read_pos;
Unsigned int size_mask; //为 SIZE-1
}
判断队列的空满如下实现：
判空： write_pos==read_pos;
判满： (write_pos-read_pos)>size_mask
那么入队操作如下:
int enqueue(TYPE data,Queue q){
If((q.write_pos-q.read_pos)<=q.size_mask){
q.buf[ q.write_pos & q.size_mask ]=data; //利用mask为2的n次方减一(有效
q.write_pos++; //位都是1)巧妙的利用与运算，避免
return SUCCESS; //了模运算和write_pos的回卷
}else{
return NOMEM
}
}
出队操作：
Int dequeue(TYPE *data,Queue q){
If((q.write_pos-q.read_pos)>0){
*data=q.buff[ q.read_pos & q.size_mask ];
q.read_pos++;
return SUCCESS;
}else{
return NODATD
}
}
log: 2015-12-18
该实现存在一个bug，当程序运行足够久后，或者说enqueue 调用的次数足够多时，最终会发生 wr下标回卷到0 这时候rd下标可能还未回卷。那么
wr-rd就是负值
由于 (q.write_pos-q.read_pos)<=q.size_mask 这三个变量都是无符号型的，上面的情况发生时，即wr-rd<0 被隐式转换为无符号型后数值可能很大从而是条件不成立。 但是此时可能队列并未满。从未导致，未满队列却不能入队数据
另外，如果一直调用enqueue操作。直到 wr回卷为0，此时wr = rd = 0，那么出队操作会因此判断队列时空的。到时有数据不能取，或者是继续调用enqueue导致之前的入队数据被覆盖。
