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;
}