我对 C 下的内存结构的理解是程序的内存与堆栈和堆分开，每个从 block 的两端增长，可以想象分配所有 ram，但显然抽象为某种 OS 内存片段管理器。< br/> 堆栈设计用于处理局部变量(自动存储)和堆用于内存分配(动态存储)。
(编者注:在某些 C 实现中，自动存储不使用“调用堆栈”，但这个问题假设在普通 CPU 上使用普通的现代 C 实现，如果本地人不能只是生活，他们会使用调用堆栈在寄存器中。)
假设我想为一些数据解析算法实现一个堆栈数据结构。它的生命周期和范围仅限于一个函数。
我可以想到 3 种方法来做这样的事情，但在我看来，考虑到这种情况，它们都不是最干净的方法。
我的第一个想法是在堆中构造一个堆栈，例如 C++ std::vector:
Some algorithm(Some data)
{
Label *stack = new_stack(stack_size_estimate(data));
Iterator i = some_iterator(data);
while(i)
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
push_stack(stack,label);
}
else if(label_type_b(label))
{
some_process(&data,label,pop_stack(stack));
}
i = some_iterator_next(i);
}
some_stack_cleanup(&data,stack);
delete_stack(stack);
return data;
}
这个方法没问题，但是很浪费，因为堆栈大小是一个猜测，并且在任何时候 push_stack 可能会调用一些内部 malloc 或 realloc 并导致不规则的减速。这些都不是这个算法的问题，但这个结构似乎更适合必须跨多个上下文维护堆栈的应用程序。这里不是这种情况。栈是这个函数私有(private)的，在退出前被删除，就像自动存储类一样。
我的下一个想法是递归。因为递归使用内置堆栈，这似乎更接近我想要的。
Some algorithm(Some data)
{
Iterator i = some_iterator(data);
return some_extra(algorithm_helper(extra_from_some(data),&i);
}
Extra algorithm_helper(Extra thing, Iterator* i)
{
if(!*i)
{return thing;}
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
*i = some_iterator_next(*i);
return algorithm_helper
( extra_process( algorithm_helper(thing,i), label), i );
}
else if(label_type_b(label))
{
*i = some_iterator_next(*i);
return extra_attach(thing,label);
}
}
}
这种方法使我免于编写和维护堆栈。对我来说，代码似乎更难理解，但对我来说并不重要。
我的主要问题是这会占用更多空间。
使用堆栈帧保存此 Extra 构造的副本(它基本上包含 Some data 加上要保存在堆栈中的实际位)和完全相同的迭代器的不必要副本每帧中的指针:因为它“更安全”然后引用一些静态全局(我不知道如何不这样做)。如果编译器做了一些聪明的尾递归之类的事情，这不会是一个问题，但我不知道我是否喜欢交叉手指并希望我的编译器很棒。
我能想到的第三种方式涉及某种可以在堆栈上增长的动态数组，这是使用某种我不知道的 C 语言编写的最后一件事。< br/>
或者一个外部 asm block 。
考虑到这一点，这就是我正在寻找的东西，但我看不到自己编写 asm 版本，除非它非常简单，而且我认为编写或维护并不容易，尽管它在我的脑海中看起来更简单.显然它不能跨 ISA 移植。
我不知道我是否忽略了某些功能，或者我是否需要寻找另一种语言，或者我是否应该重新考虑我的生活选择。一切都可能是真的……我希望这只是第一个。
我不反对使用某些库。有没有，如果有，它是如何工作的？我在搜索中没有找到任何东西。
我最近了解了可变长度数组，但我真的不明白为什么不能将它们用作增加堆栈引用的一种方式，但我也无法想象它们会以这种方式工作。
最佳答案
;博士:使用 std::vector 或等价物。
(已编辑)
关于您的开场白:分段的时代结束了。如今，进程有多个堆栈(每个线程一个)，但都共享一个堆。
关于选项 1:与其编写和维护堆栈并猜测其大小，您应该直接使用 std::vector 或围绕它的 C 包装器，或者它的 C 克隆 - 在任何情况下，使用“vector ”数据结构。
Vector的算法一般是quite efficient .不完美，但通常适用于许多实际用例。
关于选项 2:您是对的，至少只要讨论仅限于 C。在 C 中，递归既浪费又不可扩展。在其他一些语言中，特别是在函数式语言中，递归是表达这些算法的方式，尾调用优化是语言定义的一部分。
关于选项 3:最接近您正在寻找的 C 东西是 alloca() .它允许你增加堆栈帧，如果堆栈没有足够的内存，操作系统会分配它。然而，围绕它构建堆栈对象将非常困难，因为没有 realloca()，正如@Peter Cordes 所指出的。
另一个缺点是堆栈仍然有限。在 Linux 上，堆栈通常限制为 8 MB。这是与递归相同的可扩展性限制。
关于可变长度数组:VLA 基本上是语法糖，一种方便的表示法。除了语法之外，它们还具有与数组完全相同的功能(实际上，甚至更少，即 sizeof() 不起作用)，更不用说 std::vector.
关于c - 使用callstack在C中实现栈数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59559587/