好的,首先我写了方法,事先搜索了stackoverflow,注意到我的 想法与大多数人的做法相符,但是,堆栈实际上并没有反转,而是在其中放入了奇怪的值:
我是这样做的:我创建了一个辅助堆栈和一个条件大小为 != 0 的 while 循环,然后我调用 aux.push(pop()) 因为 pop 方法也返回已删除的元素,所以堆栈应该反转,并且在 O(n) 时间复杂度。但是,这种情况发生了:
要反转的堆栈:A C D F -> 结果:Đ Đ `
我运行了一个内存泄漏测试器,它告诉我我曾 4 次尝试释放已经释放的空间,所以我认为这可能是原因。
更多详情:
堆栈实现为动态数组
相关功能代码如下:
template<typename T>
bool NizStek<T>::push(const T& element){
if(_size == _capacity) increaseCapacity();
if(_size == 0){
_brojE++;
_top++;
_array[_top] = new T(element);
}
else{
_size++;
++_top;
_array[_top] = new T(element);
}
}
弹出功能:
template<typename T>
T NizStek<T>::pop(){
if(_size == 0) throw "Stack is empty";
T oldTop = *_array[_top];
delete _array[_top];
_top--;
_size--;
return oldTop;
}
反向函数:
template<typename T>
void NizStek<T>::reverse() {
NizStek<T> aux;
while(size() != 0){
aux.push(pop());
}
*this = aux;
}
COPY CONSTRUCTOR(OPERATOR = 同第一行是delete[] _array;)
template<typename T>
NizStek<T>::NizStek(const NizStek& rhs){
_size = rhs._size;
_capacity = rhs._capacity;
_niz = new T*[_capacity];
for(int i=0; i<_size ;i++) _array[i] = rhs._array[i];
_top = rhs._top;
}
提前致谢!
最佳答案
因为你没有展示它,我猜你是让编译器创建你的复制构造函数,它会做一个浅拷贝。所以这个:
template<typename T>
void NizStek<T>::reverse()
{
NizStek<T> aux;
while(size() != 0)
{
aux.push(pop());
}
*this = aux; // Potential problem here!
}
将设置this
等于aux
的指针值。据推测,您的析构函数会释放内存,因此当 aux
超出范围时,this
中指向的项目 (this->_array
)不再分配......所以当你试图取消引用它们时你会得到垃圾。
您可以通过编写自己的复制构造函数并实际执行数据的深层复制(或使用移动语义)来解决此问题。
编辑
使用更新后的复制构造函数,您似乎遇到了另一个问题:
_niz = new T*[_capacity];
for(int i=0; i<_size ;i++)
_array[i] = rhs._array[i]; // this is still a shallow copy!
_top = rhs._top;
分配将创建一个指针数组,而不是一个对象数组。所以你会有一个未分配的指针数组(this
和 aux
将指向相同的项目,所以当 aux
清除它们时它的析构函数,你仍然指向垃圾)。我想你想要的是
_niz = new T[_capacity]; // note the lack of *
for(int i=0; i<_size ;i++)
_array[i] = rhs._array[i];
_top = rhs._top;
或者
_niz = new T*[_capacity];
for(int i=0; i<_size ;i++)
{
_array[i] = new T(*rhs._array[i]); // actually do a deep copy
}
_top = rhs._top;
附带说明一下,如果您关心效率,您可能希望使用固定大小的数组或使用链表。每次推送需要新容量的项目时,重新分配和复制内存缓冲区对于堆栈结构来说效率非常低。
关于c++ - 反转堆栈时出错,你能指出来吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19848320/