MyQueue版本1

#include <iostream>
using namespace std;

template<typename T>
class MyQueue {

private:

	struct QueueItem {
		QueueItem(T _data = T(), QueueItem  * _next = nullptr)
			:data(_data),
			next(_next) {
			next = nullptr;
		}
		T  data;
		QueueItem  * next;
	};
	QueueItem * _front;//指向队头
	QueueItem * _rear; //指向队尾

public:

	//队尾入队操作
	void push(T & _value) {
		QueueItem *tep = new QueueItem(_value, nullptr);
		_rear->next = tep;
		_rear = tep;
	}
	//队头出队操作
	void pop() {
		if (empty()) { return; }
		QueueItem *tep = _front->next;
		_front->next = tep->next;
		//如果队中只有一个元素,被删除了,由于这个出队的元素要delete,所以,_rear 就丢失信息了,这个时候要记得把_rear=nullprt
		if (_front->next == nullptr) { _rear = front; }
		delete tep;
	}

	//队是否为空
	bool empty() {
		return _front = _rear;
	}

	~MyQueue() {
		QueueItem *current = _front;
		while (current != nullptr) {
			_front = _front->next;
			delete current;
			current = _front;
		}
	}

	MyQueue<T>() {
		QueueItem *tep = new QueueItem;
		_front = tep;
		_rear = tep;
	}


	T front()  {
	   return  _front->next; ->data;
	}
};

int main() {

	MyQueue<int> mq;
	for (int i = 0; i < 10000000; i++) {
		mq.push(i);
		mq.pop();
	}

	bool isEmpty = mq.empty();

	cout << isEmpty << endl;

	system("pause");
	return 0;
}

上面代码有个效率问题,循环 10000000 次,一直在创建 对象,和销毁对象. 如何优化?

MyQueue版本2

#include <iostream>
using namespace std;


template<typename T>
class MyQueue {

private:

	struct QueueItem {
		
		QueueItem(T _data = T(), QueueItem  * _next = nullptr)
			:data(_data),
			next(_next) {
			next = nullptr;
		}

		//分配内存
		void * operator new(size_t size) {
			
			if (poolItemList == nullptr) {
				
				//预先申请内存空间			
				poolItemList = (QueueItem *) new char[sizeof(QueueItem) * POOL_ITEM_SIZE];
				QueueItem * tp = poolItemList;
				//把上面申请的内存空间 按照 一个 一个 QueueItem 串到队列中
				while (tp < poolItemList + POOL_ITEM_SIZE -1) {
					tp->next = tp + 1;
					++tp;
				}
				tp->next = nullptr;
				cout << "1:申请缓存池空间" << poolItemList << endl;
				
			}
			
			QueueItem *  returnPoint = poolItemList;
			poolItemList = poolItemList->next;	
		//	cout << "申请QueueItem节点空间" << returnPoint << endl;
			return returnPoint;
			
		}

		//将使用过的内存还会去
		void operator delete(void * ptr) {
			
			//归还的内存放回到链表头部
			if (ptr != nullptr) {
				QueueItem * qptr = (QueueItem *)ptr;		
				QueueItem *	tp_poolItemList = poolItemList;
				qptr->next   = poolItemList;
				poolItemList = qptr;
			//	cout << "归还空间" << ptr << endl;
			}

		}

		T  data;
		QueueItem  * next;
		static  const   int  POOL_ITEM_SIZE = 10000;
		static  QueueItem    * poolItemList ;

	};
	
	
	QueueItem * _front;//指向队头
	QueueItem * _rear; //指向队尾
	
	
public:

	//构造函数
	MyQueue<T>() {
		QueueItem *tep = new QueueItem();
		_front = tep;
		_rear  = tep;
	}

	~MyQueue() {
		QueueItem *current = _front;
		while (current != nullptr) {
			_front = _front->next;
			delete current;
			current = _front;
		}
	}


	//队尾入队操作
	void push(T & _value) {
		QueueItem *tep = new QueueItem(_value, nullptr);
		_rear->next = tep;//原来队尾元素的下一节点设置为当前申请节点
		_rear = tep;
	}

	//队头出队操作
	void pop() {
		if (empty()) { return; }
		QueueItem *first = _front->next;
		_front->next = first->next;
		//如果队中只有一个元素,被删除了,由于这个出队的元素要delete,所以,_rear 就丢失信息了,这个时候要记得把_rear=nullprt
		if (_front->next == nullptr) { _rear = _front; }
		delete first;
	}

	//队是否为空
	bool empty() {
		return _front == _rear;
	}

	T front()  {
	   return  _front->next->data;
	}


};

template<typename T>
typename MyQueue<T>::QueueItem *  MyQueue<T>::QueueItem::poolItemList =nullptr;


int main() {

	MyQueue<int> mq;
	for (int i = 0; i < 100000; i++) {
		mq.push(i);
		mq.pop();
	}

	bool isEmpty = mq.empty();

	cout << isEmpty << endl;

	system("pause");

	return 0;

}