c - 如何创建和处理堆栈？

Question

因为 C++ 及以后的任何东西都有很好的结构来处理像行为( vector 、列表、数组列表等)这样的“堆栈”，所以我想用 C 来保留这个问题。

因此，我正在学习编译器、堆栈、inscript 和 postscript、解析器、词法分析器，以及涉及将编译器组合在一起的所有其他内容，因为我将在本学期稍后的类(class)中被要求这样做。我想确保我对堆栈的理解是扎实的。

我相信我对如何将它们组合在一起有大致的了解。基本上你有一个遵循后进先出模型的数组。当您添加一个元素时，它会被“插入”到数组的末尾，并在移除时“弹出”。没问题。我担心的是一些实现细节。 如何跟踪元素数量？堆栈应该初始化到多大？我应该使用结构将这些细节放在一起吗？变量是全局变量吗？

我的教授已经给了我们一些与我们的作业相关的源代码，我只是在寻找一些补充细节以供我自己理解(通常我必须自己整理一些东西才能理解别人的代码)。在我的大部分编程经验中，堆栈是一些我无法控制的神奇地方，但如果我的递归函数太深就会爆炸(所以有人吗？)。

提前致谢。

编辑:

好的，我想我需要澄清的一件事是我不是在制作“真正的”堆栈，而是需要采用一个中缀 epxression 并将其转换为后缀。我正在查看堆栈数据结构，因此任何与架构相关的内容都可能不适用于此。给我的印象是堆栈是处理此问题的方法，同样使用 BNF 表示法中描述的规则缩减。

Answer 1

你说的是哪种堆栈？

大多数 CPU 架构都有一个堆栈的概念，基本上就是 CPU 跟踪函数调用的方式。 C 通常被编译为为此目的使用相同的堆栈，并且还经常将其用于参数传递。

这样的“架构”堆栈不需要太多，通常在 CPU 中有一个寄存器指向堆栈的顶部。操作系统的工作是确保每次进程启动时，该进程都有一个有效的堆栈指针。这是通过分配内存并将寄存器初始化到正确的地址来完成的。具有虚拟内存等的现代“大型”操作系统通常支持按需动态扩展堆栈。

在这种情况下，堆栈中的元素数量未明确跟踪，您可以通过检查当前堆栈指针并与进程进行比较来计算使用的字节数量'(假设已知)“stack start”，但这并没有告诉你这些字节的内部结构。这对于此类低级构造来说是正常的。

---

如果像 nos 在评论中暗示的那样，你真的在​​谈论堆栈数据结构，那么在 C 中就没有这种东西的标准实现。可以想象许多可能的 API:s，例如:

typedef struct _Stack Stack;

Stack * stack_new(size_t element_size, size_t initial_depth, int allow_growth);
int     stack_push(Stack *stack, const void *element);
int     stack_pop(Stack *stack, void *element);
void    stack_peek(const Stack *stack, void *element);
size_t  stack_depth(const Stack *stack);
void    stack_clear(Stack *stack);

上面的 API 保留了初始深度以及一旦您尝试超出用户限制时堆栈是否应该增长。在我看来，这对于通用 API 来说是明智的。