动态堆栈内存重新分配

Question

我对 C++ 相当陌生，对指针也很陌生。我目前正在处理一个堆栈，并试图在堆栈大小达到顶部时重新分配堆栈的内存，但是，我遇到了问题。我已经对 Google 和堆栈溢出进行了大量研究，并发现一些有用的信息，但由于我对堆栈和 C++ 很陌生，所以我仍然遇到问题。我希望一些聪明的人至少能为我指明正确的方向。

现在...这是我的代码。

#include <iostream>
#define STACKMAX 20
using namespace std;

template <class T> class StackTemplated {
private:
    int top;
    T   values[STACKMAX];
public:
    StackTemplated();
    void    push(T i);
    T       pop(void);
    bool    empty(void);
 }; 


template <class T> StackTemplated<T>::StackTemplated() {
    top = -1;
}

template <class T>void StackTemplated<T>::push(T i) {
if (top == STACKMAX - 1) {

    // reallocate top of stack. (this is the area I'm having issues)
    char * string1;
    string1 = (char *)calloc(STACKMAX, sizeof(char));

        if (top == STACKMAX - 1) {
            cout << "The stack didn't re-allocate.";
            exit(1);
        }

} else {
    top++;
    values[top] = i;
}
}   

 template <class T> T StackTemplated<T>::pop(void) {
if (top < 0) {
    printf("%", "Stack underflow!");
    exit(1);
} else {
    return values[top--];
}
}   

template <class T> bool StackTemplated<T>::empty() {
return (top == -1);
}

Answer 1

以下是我注意到的一些事情的列表：

• STACKMAX 是一个常量。如果您要扩展堆栈，您将如何跟踪它当前的大小？
• values 成员是一个固定大小的数组。如果不更改其声明和分配方式，您将无法动态更改其大小。
• calloc() 使用您指定的字节数分配新的内存块。您需要以某种方式将现有堆栈复制到新的内存块中，并释放前一个堆栈。
• 您在对 calloc() 的调用中仅分配 STACKMAX 字节。您可能希望按 sizeof T 缩放，以防 T 不是 char。

一旦你解决了这些要点，就会有很多细节需要你解决。祝你好运。

Answer 2

问题是您不想重新分配堆栈顶部。相反，您想要分配一个新的值数组，该数组足够大以容纳新值。另外，由于您需要重新分配数组，因此 values 应该是一个指针。

但是我们忘记这一切怎么样？如果我们使用 C++ 工作，让我们使用 C++ 提供的功能来让我们的生活更轻松。完成后，如果您确实觉得有必要，请尝试打开一切。

我所指的一件事是您对calloc 的使用。使用calloc是一个坏主意，特别是在使用模板时。问题是，由于 calloc 没有类型信息，因此它不会执行像调用构造函数这样基本的操作。构造函数在 OOP 中非常非常重要，因为它们保证对象在创建时的不变性。相反，请使用 new[] 关键字，例如

values = new T[STACKMAX];

这会分配 STACKMAX 长度的 T 数组。当然，正如 Greg 指出的那样，您应该重新考虑 STACKMAX 的使用，并改用变量。另外，values 不应该是静态数组，而应该是 T* 类型。

我提到的另一件事是，您实际上正在尝试实现一个根据需要动态增长的数组。在 C++ 中，我们将这样的结构称为向量。如果您使用向量，您的整个代码就会简化为

#include<iostream>
#include<vector>

using namespace std;

template<class T> class StackTemplated {
private:
    std::vector<T> vec;

public:
    StackTemplated() { } // the constructor is trivial; in fact, you can leave it out if you want
    void    push(T i);
    T       pop(void);
    bool    empty(void);
};

template<class T>
void StackTemplated<T>::push(T i) {
    vec.push_back(i);
}

template<class T>
T StackTemplate<T>::pop(void) {
    T top = vec.back();
    vec.pop_back();
    return top;
}

template<class T>
bool StackTemplate<T>::isEmpty(void) {
    return vec.size() == 0;
}

仅此而已。如果您可以使用现有的数据结构来实现新的数据结构，那么事情就会少很多。

一旦您真正熟悉向量的工作原理（并且网络上有大量解释/文档），然后尝试自己实现该功能。最重要的是，如果您确切地知道数据结构的行为方式，那么实现数据结构就会容易得多。

Answer 3

我会声明你的值，

T* vaules;

然后使用 new 来创建它而不是 calloc。您需要跟踪堆栈的顶部及其大小。正如格雷格所说，当你增加堆栈时，请确保复制数据并清理旧数据。