高效利用队列的空间

  大家都知道队列是可以用数组来模拟的，可以先开辟一段定长的数组空间，然后分别使用两个变量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);
	}
};

  相信看完本篇，你也多多少少有收获，喜欢的可以动动手指点赞加关注！