C++简单循环缓冲队列
我使用数组实现了一个队列，并将其视为循环缓冲区。_tail指向要读取的下一个元素，_head指向要写入的下一个元素：
template<int SIZE>
class Q {
bool push(const int item){
if(false == isFull()){
_q[_head] = item;
_head = ++_head % SIZE;
return true;
}
return false;
}
bool pop(int& toReturn){
if(false == isEmpty()){
toReturn = _q[_tail];
_tail = ++_tail % SIZE;
return true;
}
return false;
}
private:
std::array<int, SIZE> _q;
std::atomic<int> _head;
std::atomic<int> _tail;
};但是，我的isFull()和isEmpty()逻辑中有一个错误，通过以下问题确定：
当队列最初为空时，_tail和_head都将指向_q[0]。
当我编写了_q[0]、_q[1]、_q[2]和q[3]之后，_tail和_head将再次指向相同的内容，所以很明显我不能使用_tail == _head来确定full/empty。
实现isEmpty()和isFull()逻辑的最简单方法是什么？我不确定是否应该在读取队列项之后编写一个“空白”枚举？
回答 6
Stack Overflow用户
发布于 2017-05-05 21:19:53
如果您愿意将队列的有效大小减少一个元素，则逻辑相对简单：
- 当
head和tail相同时，队列为空。 - 当
tail递增1时，使用回绕将生成head，队列已满。
这使得插入第N个元素成为不可能，因为第N个元素充当“前哨”。因此，对于N元素队列，您需要分配一个N+1元素数组，并在处理回绕的所有表达式中使用(SIZE+1)。
std::array<int,SIZE+1> _q;实施说明：
这两行
_head = ++_head % SIZE;
_tail = ++_tail % SIZE; 具有未定义的行为，因为编译器可以灵活地在赋值结束之前或之后应用递增_head和_tail的副作用。如果编译器选择在赋值之后应用副作用，则不会发生环绕效应。
由于根本不需要复合赋值，因此修复方法很简单：
_head = (_head+1) % SIZE;
_tail = (_tail+1) % SIZE; Stack Overflow用户
发布于 2017-05-05 21:16:10
在对队列中的项数进行计数的类中声明数据成员(计数器)。在(推送)中递增，在(弹出)中递减。当它为(0)时，队列为空
Stack Overflow用户
发布于 2017-05-05 21:39:59
像这样改变实现怎么样？
将头部的定义从"_head points to the next element to write into:“更改为
"_head points to latest element added“
那么isFull()就可以
bool isFull()
{
if((_head + 1) % SIZE == _tail)
return true;
return false;
}而isEmpty可能是
bool isEmpty()
{
if(_head == _tail)
return true;
return false;
}pop()是一样的，但要更改push()，并且不要忘记将_head和_tail初始化为-1
bool push(const int item){
if(false == isFull()){
if(_head == -1) //If adding the first element,
_tail = 0; // tail will point to it as it was inititiallty 0
_head = ++_head % SIZE;
_q[_head] = item;
return true;
}
return false;
}https://stackoverflow.com/questions/43805858
复制相似问题
腾讯云开发者
