c - 哨兵与传递计数

Question

我在 C 中有一个结构，其中包含一个数组，我在该数组上执行堆栈操作。

如果堆栈已满，我需要防止将元素推入数组末尾，并返回错误条件。

将堆栈的大小作为结构的元素包含在内，并将该数量的元素传递给 stack_push() 函数是更好的风格，还是应该在堆栈数组的末尾有一个哨兵元素？

Answer 1

你将如何实现你的stack_push()功能？

如果它需要扫描到数组的末尾以寻找一个空槽来插入推入的元素，那么无论如何您都需要一个标记值（例如，如果数组包含指针元素，则为 NULL）。但请注意，该算法将是 O( N )。

另一方面，跟踪数组中活动元素的数量允许您的算法对于推送（以及对于弹出）为 O(1)。它还省去了在数组中分配一个额外元素的麻烦，如果它是一个结构数组，这可能很重要。

一般来说，大多数堆栈数据结构都是使用数组和计数器来实现的。

Answer 2

你会使用什么哨兵值？当然，你必须确保这个函数的调用者绝对不会使用这个值。如果您的函数在看似合理的输入的哨兵值处过早停止，则调试可能会非常混乱。

对于字符串之类的东西，很容易使用 NULL 来终止，因为字符串不应该有零字节。但是，如果您开始在某些地方使用哨兵而不在其他地方使用，那么对于尝试使用您的代码的开发人员来说，它可能会开始变得非常混乱。

我会说使用大小参数，除非有一个非常明确和明显的哨兵选择，甚至可能没有。