1

好的，首先我已经编写了方法，事先搜索了stackoverflow，并注意到我的想法与大多数人的做法相匹配，但是，堆栈实际上并没有被反转，而是在其中放入了奇怪的值：

我这样做是这样的：我创建了一个辅助堆栈和一个条件 size ！= 0 的 while 循环，然后我调用 aux.push(pop()) 因为 pop 方法也返回已删除的元素，所以堆栈应该反转，并且在 O(n) 时间复杂度。但是，会发生这种情况：

要反转的堆栈：ACDF -> 结果：Đ Đ `

我运行了一个内存泄漏测试器，它告诉我我有 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;
}

提前致谢！

4

1 回答 1

2

由于您没有显示它，我猜您正在让编译器创建您的复制构造函数，它将执行浅拷贝。所以这：

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;

附带说明一下，如果您关心效率，您可能希望使用固定大小的数组或使用链表。每次推送需要新容量的项目时重新分配和复制内存缓冲区对于堆栈结构来说效率非常低。

于 2013-11-07T22:59:11.840 回答