高效利用队列的空间

  大家都知道队列是可以用数组来模拟的，可以先开辟一段定长的数组空间，然后分别使用两个变量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 << "Fulln"; 			return; 		}  		if (((uint16_t) (end + 1)) == 0) 			++endCount;  		arr[++end] = element; 	}  	void push(const _Tp& element) { 		if (full()) { 			std::cerr << "Fulln"; 			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 << "Fulln"; 			return; 		}  		if (((uint16_t) (end + 1)) == 0) 			++endCount;  		arr[++end] = element; 	}  	void push(const _Tp& element) { 		if (full()) { 			std::cerr << "Fulln"; 			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); 	} };

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