c++ - c++ STL中队列的数据插入和删除速度
问题描述
我对 C++ STL 中队列的插入和删除速度有疑问。
当我尝试使用我制作的 Dequeue 解决算法问题时,我面临着超时问题。
所以我认为我的 Dequeue 太慢了,我想知道我的 Dequeue 和 c++ STL 中的队列有什么区别。
这是我的队列代码。
请给我一些建议。
在这段代码中,我想value
在Node
课堂上不能有负数。
class Node
{
private:
int value;
Node* prev;
Node* next;
public:
Node();
Node(int value);
Node(int value, Node* next);
~Node();
void setValue(int value);
void setPrev(Node* prev);
void setNext(Node* next);
int getValue();
Node* getPrev();
Node* getNext();
};
Node::Node()
: value(-1), prev(nullptr), next(nullptr)
{
}
Node::Node(int value)
: value(value), prev(nullptr), next(nullptr)
{
}
Node::Node(int value, Node* next)
: value(value), prev(nullptr), next(next)
{
}
Node::~Node()
{
}
void Node::setValue(int value)
{
this->value = value;
}
void Node::setPrev(Node* prev)
{
this->prev = prev;
}
void Node::setNext(Node* next)
{
this->next = next;
}
int Node::getValue()
{
return this->value;
}
Node* Node::getPrev()
{
return this->prev;
}
Node* Node::getNext()
{
return this->next;
}
class Dequeue
{
private:
Node* front;
Node* back;
public:
Dequeue();
~Dequeue();
void pushFront(int value);
void pushBack(int value);
void popFront();
void popBack();
int getFront();
int getBack();
int getSum();
};
Dequeue::Dequeue()
{
this->back = new Node(-1, nullptr);
this->front = new Node(-1, this->back);
this->back->setPrev(front);
}
Dequeue::~Dequeue()
{
}
void Dequeue::pushFront(int value)
{
Node* node = new Node(value, this->front->getNext());
node->setPrev(this->front);
this->front->setNext(node);
node->getNext()->setPrev(node);
}
void Dequeue::pushBack(int value)
{
Node* node = new Node(value, this->back);
node->setPrev(this->back->getPrev());
this->back->setPrev(node);
node->getPrev()->setNext(node);
}
void Dequeue::popFront()
{
if (this->front->getNext() == this->back)
return;
Node* node = this->front->getNext();
this->front->setNext(node->getNext());
node->getNext()->setPrev(this->front);
node->setNext(nullptr);
node->setPrev(nullptr);
delete node;
}
void Dequeue::popBack()
{
if (this->back->getPrev() == this->front)
return;
Node* node = this->back->getPrev();
this->back->setPrev(node->getPrev());
node->getPrev()->setNext(this->back);
node->setNext(nullptr);
node->setPrev(nullptr);
delete node;
}
int Dequeue::getFront()
{
if (this->front->getNext() == this->back)
return -1;
return this->front->getNext()->getValue();
}
int Dequeue::getBack()
{
if (this->back->getPrev() == this->front)
return -1;
return this->back->getPrev()->getValue();
}
解决方案
您Dequeue
是通过链表实现的,其中节点在每个推送/弹出操作中分配/解除分配。std::queue
是通过 a 实现的std::deque
,效率更高(它只分配一次)。
如果您需要在中间插入,链表很好,但这不是您的情况。std::deque
基本上是固定大小数组的动态序列。
相关问题:
推荐阅读
- javascript - 对在 javascript 中使用 slice 感到困惑
- c# - Visual Studio - 属性窗口 - 字段描述为空
- r - MAJOR Y Axis 问题 [R studio](它是在加我的变量吗?)
- flutter - clippath 和 custompaint 颤动之间的区别
- distributed-computing - 有没有一种分布式系统结合了两种架构风格:分层架构和基于对象的架构?
- netlogo - 导出世界仅导出 Netlogo 6.2 中的前 22 个海龟拥有的变量
- object - 如何在方法参数中引用兄弟对象键?
- android - 如何使按钮停留在 RecyclerView 的末尾?
- jquery - jQuery 逻辑运算符 || (或)语法错误
- reactjs - 尝试访问来自 API 的数据时出现 TypeError:_ 未定义