C++(在基于数组的堆栈中弹出)我们是否删除该元素？

Question

这里是一些关于使用 ARRAY 实现的 STACK 的讲稿中的代码。

在规范中:

template <typename T>
class Stack {
public:
    Stack();
    bool pop (T& stackTop);
    //there is still some other code

private:
    int maxSize;
    int* arr;
    int _size;
}

实现中:

bool Stack<T>::pop(T& stackTop){
    if (isEmpty()){ 
        return false;
    }else{
        --_size;
        stackTop=arr[_size];
        return true;
    }
}

以及一些用户程序示例:

Stack<int> st;
int k;
st.push(1);st.push(2);st.push(3);//will add element 1 ,2, and 3.
st.pop(k);cout<<"pop"<<k<<endl; //will pop the last element which is 3 and print pop 3

据我了解，在 pop 实现中，我们更新(减少一)数组的大小。但我们似乎并没有删除这个元素! 那么，该元素实际上是否仍然存在，而我们只是减小了大小以使数组的顶部发生了移动？ 例如 我的最大尺寸是 100 在代码中，我推送了 1、2 和 3。现在顶部位于 3 上。其余 97 个元素仍未分配。 现在我弹出(这是最后一个元素，即 3)。 当我弹出时，我只是将顶部“移动”到2。但实际上3仍然在那里，其余的97个元素仍然未分配。 ???

请解释一下它是如何工作的。

Answer 1

弹出一个元素应该将其从堆栈中删除，但同时返回相同的元素(是否删除它或进一步处理它取决于您)。

如果您使用静态结构(例如堆栈数组)，您可以简单地使代表刚刚弹出的堆栈顶部的单元格的内容无效，返回该元素(如果您按值存储，则只需返回否则返回引用)并将索引设置为其下方的元素作为新的顶部，或者创建该数组的一个较小大小的拷贝，并复制尚未弹出的内容。您可以通过尝试在一批中依次弹出多个弹出来优化最后一种方法，然后将堆栈“刷新”到较新的较小堆栈。我个人更喜欢第一种方式，因为堆栈通常被认为是具有一定大小的东西(=具有有限容量而不是动态容量的堆栈)。

弹出时删除元素是堆栈中弹出的工作方式，如果您只是将旧值保留在那里，则可能会导致愚蠢的情况，例如覆盖元素，您已通过推送命令弹出但没有根本想覆盖。如果您以正确的方式执行此操作，您总是知道一旦弹出该值就无法再从该堆栈中检索(除了弹出它的那一刻)，因为它不再存在!

您还可以使用单个链表来实现，然后在执行弹出操作时确实可以减小堆栈的大小，而不仅仅是用虚拟值“替换”弹出的元素或创建一个新的较小堆栈并复制剩下的就在那里。