如何使堆栈动态增长？

Question

这是我的 Stack 的一个小程序 class:

 #include <iostream>

using namespace std;

#include <iomanip>

template <typename T>
class Stack
{
private:
    T *stackPtr; 
    int size; 
    T top; 
public:
    Stack(int = 10);
    ~Stack(); 
    bool push(const T  );
    bool pop(); 
    void printStack();
};

int main()
{
    Stack <int> myStack(5);


    cout << "Push 5 elements to stack: ";
    int ct = 0;
    while (ct++ != 5)
    {
        int temp;
        cin >> temp;
        myStack.push(temp);
    }

    myStack.printStack(); 

    cout << "\nErasing two elements:\n";

    myStack.pop(); 
    myStack.pop(); 
    myStack.printStack(); 

    return 0;
}


template <typename T>
Stack<T>::Stack(int s)
{
    size = s > 0 ? s: 10;   
    stackPtr = new T[size]; 
    top = -1; 
}


template <typename T>
Stack<T>::~Stack()
{
    delete [] stackPtr; 
}


template <typename T>
bool Stack<T>::push(const T value)
{
    if (top == size - 1)
        return false; 

    top++;
    stackPtr[top] = value; 

    return true; 
}


template <typename T>
bool Stack<T>::pop()
{
    if (top == - 1)
        return false; 

    stackPtr[top] = 0; 
    top--;

    return true; 
}


template <typename T>
void Stack<T>::printStack()
{
    for (int ix = size -1; ix >= 0; ix--)
        cout << "|" << setw(4) << stackPtr[ix] << endl;
}

所以，为了使用这样的堆栈，我应该在使用前在构造函数中声明它的大小，就像 Stack<int> newstack(10)，如果我需要 10 个元素。那么，如果我不知道堆栈的最终大小怎么办？如何让它动态增长，仅仅通过向它推送元素？我一直在寻找解决方案，但我的所有想法仍然是计算元素数量，然后声明一个堆栈以适应元素数量。

Answer 1

我想建议使用 std::stack() 不会是您期望的答案 ;-)

您只需在达到限制时分配更多 space：

template <typename T>
bool Stack<T>::push(const T value)
{
    if (top == size - 1) {
        //return false; 
        size_t s = size + 10;       // for example increase by 10
        T *ps = new (nothrow) T[s]; // allocate new region
        if (ps==nullptr) 
            return false;           // out of memory
        for (size_t i=0; i<size; i++) 
            ps[i] = stackPtr[i];  
        delete[] stackPtr;  
        stackPtr = ps; 
        size = s;                  // stack is now bigger,  
    }                              // so continue as if there was no problem

    top++;
    stackPtr[top] = value; 

    return true; 
}

问题是，增加多少筹码。您可以像这里一样使用常量方法，但最好考虑一个成员变量并在您的构造函数中对其进行初始化。

编辑： 我使用新的 nothrow 来避免在内存不足的情况下抛出异常，因为你的签名预见了return代码就运行成功了。

Answer 2

您始终可以使用链表来完成此操作。如果你想插入到堆栈中，那么你只需在链表的头部放置一个节点。要弹出，只需将其删除即可。现在你可能会想如何实现像 Stack S=new Stack(5); 这样的语句。

你只需保留一个计数器来保持这个值。您可以对该变量实施任何检查（如堆栈溢出等）。您只需像 C++ STL 支持的那样使其动态化，就可以很容易地使用它。

Answer 3

首先，您知道 C++ 内置了 std::stack，不是吗？对于其余的答案，我假设您有一些理由不使用它（也许这是一个学习练习）。

实现您想要的效果的一种非常天真的方法是：

每次添加元素时，分配一个 size + 1 的新数组 new[].
将旧数组的所有元素和新元素复制到新数组中。
delete[]旧数组。
使stackPtr指向新数组。

撇开此解决方案的所有性能和异常安全缺陷不谈，如果您的元素类型 T 没有默认构造函数，它怎么可能工作？它甚至不会编译。事实上，您的 class 失败了，因为它适用于以下 T:

struct CannotUseInThisStack
{
    CannotUseInThisStack(int) {} // no default constructor
};

Stack<CannotUseInThisStack> s; // error

真正的解决办法是：不要使用new[]和delete[]。根据 std::vector（或根据 std::deque 实现您的堆栈，这正是 std::stack 默认情况下所做的！）。 std::vector 以更好的方式支持开箱即用的动态增长，无需在每次添加元素时连续重新分配，也不需要能够默认构造 T。

当然，这理所当然地引出了一个问题，那就是 std::vector 如何做到这一切。

答案是 std::vector，或者说它的标准分配器 std::allocator, is not implemented itself in terms of new[] and delete[] but in terms of placement new. Memory allocation and element construction are separated. See std::allocator:allocate。这解决了缺少默认构造函数的问题。首先分配原始内存，然后使用复制构造函数在该原始内存位置构造新元素（在 C++11 中，您还可以使用完美转发来就地构造 T，但这有点题外话）。

使用 placement new 还可以让 std::vector 的容量呈指数级增长。每次添加元素时，容器都不需要重新分配内存；它提前为更多元素分配原始内存（类似于 Christophe 在他的回答中所做的）。仅当超过当前容量时才会重新分配。

有了 new[] 和 delete[]，这样复杂的机制是不可能的。

通常，如果您想了解严肃的容器设计，请查看您的编译器如何实现所有 C++ 标准容器。

如何使堆栈动态增长？

How to make a stack grow dynamically?

c++

class

memory

heap-memory

stack-memory