高效利用队列的空间
大家都知道队列是可以用数组来模拟的，可以先开辟一段定长的数组空间，然后分别使用两个变量head和tail来代指队列的头和尾，从而维护整个队列，相信到这里大家都比较熟悉。不过这种做法是有弊端的，比如说下图这种情况
假设经过不断地增删元素，Head和Tail已经来到了数组最后两个位置，这时候整个队列中只有两个元素，并且我们也不能再增加元素了，因为已经到达了容量的上限。然而，这时候前面一大片连续空间就造成了浪费。因此我们重新设想一下
这是另外一种构思，此时队列当中存有三个元素，那么该怎么实现呢？
#define MAXSIZE (1 << 16)
template <typename _Tp>
struct fifo {
uint16_t front = 1;
uint16_t end = 1;
int frontCount = -0x3f3f3f3f;
int endCount = -0x3f3f3f3f;
_Tp arr[MAXSIZE];
}对于front和end两个变量，可以用无符号整型来实现，当无符号整型溢出的时候，会自然的变成0，问题就爽快的解决了。不过这里还引入了两个变量，frontCount和endCount，这是为了判断front是在end的前面还是后面。换句话说，当end发生溢出的时候，end就来到了front前面，这时候endCount就加1，frontCount同理。
bool empty() {
if (endCount > frontCount)
return false;
return (front == end) ? true : false;
}
bool full() {
if (endCount > frontCount && end == front)
return true;
return false;
}
std::size_t size() {
if (full())
return MAXSIZE;
else if (empty())
return 0;
else if (frontCount == endCount)
return (end - front);
else
return (MAXSIZE - front + end);
}以上是判断队列容量的一些相关成员函数，实现都比较简略，较为关键的是入队和出队的操作实现。
void push(_Tp&& element) {
if (full()) {
std::cerr << "Full\n";
return;
}
if (((uint16_t) (end + 1)) == 0)
++endCount;
arr[++end] = element;
}
void push(const _Tp& element) {
if (full()) {
std::cerr << "Full\n";
return;
}
if (((uint16_t) (end + 1)) == 0)
++endCount;
arr[++end] = element;
}
std::optional<_Tp> pop() {
if (empty())
return std::nullopt;
if (((uint16_t) (front + 1)) == 0)
++frontCount;
return arr[++front];
}有个小区别，这里的front指向的位置在逻辑上是不存储元素的，其它的和开篇所讲的都差不多。那么，对于(end + 1) ，为什么要加一个强制转换呢？因为如果不加的话，end和1进行运算之后就提升为了int类型，这时候结果是int类型的，它不会因为溢出而变成0。
完整代码：
#include <iostream>
#include <cstdint>
#include <optional>
#define MAXSIZE (1 << 16)
template <typename _Tp>
struct fifo {
uint16_t front = 1;
uint16_t end = 1;
int frontCount = -0x3f3f3f3f;
int endCount = -0x3f3f3f3f;
_Tp arr[MAXSIZE];
void push(_Tp&& element) {
if (full()) {
std::cerr << "Full\n";
return;
}
if (((uint16_t) (end + 1)) == 0)
++endCount;
arr[++end] = element;
}
void push(const _Tp& element) {
if (full()) {
std::cerr << "Full\n";
return;
}
if (((uint16_t) (end + 1)) == 0)
++endCount;
arr[++end] = element;
}
std::optional<_Tp> pop() {
if (empty())
return std::nullopt;
if (((uint16_t) (front + 1)) == 0)
++frontCount;
return arr[++front];
}
bool empty() {
if (endCount > frontCount)
return false;
return (front == end) ? true : false;
}
bool full() {
if (endCount > frontCount && end == front)
return true;
return false;
}
std::size_t size() {
if (full())
return MAXSIZE;
else if (empty())
return 0;
else if (frontCount == endCount)
return (end - front);
else
return (MAXSIZE - front + end);
}
};相信看完本篇，你也多多少少有收获，喜欢的可以动动手指点赞加关注！