高效利用队列的空间

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

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

热门相关:韩娱之影帝   龙骑战机   绍宋   余生皆是喜欢你   龙骑战机