c++ - 用动态数组实现的堆栈

Question

假设我们使用一个动态分配的数组来实现一个堆栈。如果数组填满，我们是面临两难境地。从以下选项中，选择最能描述的选项我们处理填充数组的策略。

(a) We declare a new array, twice as big as the original, and copy the data into the new space for a total cost of O(n), over a sequence of n pushes.

(b) We declare another array and keep track of which of the two (or more) arrays contain the current top of the stack in a private member of the stack class. This costs us O(1) per push.

(c) For some fixed k, we create a new array of size n + 2^k and copy the data into the new space for an average cost of O(1) per push operation.

(d) We avoid implementing a stack using a dynamically allocated array, because it is inefficient to have to reallocate memory.

(e) None of these answers is a reasonable response.

我很确定正确答案是 a，但我不明白为什么它会比其他答案更好？其他的还实用吗？他们对我来说似乎还可以。例如，c 几乎与 `a 相同，不是吗？为什么加倍比增加一个常数更有利？其他选项如何 - 为什么它们不起作用？

Answer 1

假设您的堆栈有 128 个元素，而您最终不得不在其中存储 4096 个元素。与每次以 128 项常量扩展数组相比，您需要调整数组大小多少次？