好的,首先我已经编写了方法,事先搜索了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;
}
提前致谢!