哨兵与传递计数

Question

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

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

将堆栈的大小作为结构的元素包含进来，并将该数量的元素传递给stack_push（）函数还是应该在堆栈数组的末尾有一个sentinel元素？

Answer 1

你会使用什么定点值？当然，你必须确定这个函数的调用者绝对不会使用这个值。如果你的函数过早地停留在一个似乎是合理输入的标记值，那么调试可能会非常混乱。

对于像字符串这样的事情，很容易使用NULL来终止，因为字符串不应该有零字节。但是，如果您开始在某些地方而不是其他地方使用标记，那么对于尝试使用您的代码的开发人员而言，它会开始变得非常混乱。

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

Answer 2

你打算如何实现你的stack_push()函数？

如果它需要扫描到数组的末尾，寻找空插槽来插入推入的元素，那么无论如何您都需要一个定位值（例如，如果数组包含指针元素，则为NULL）。但请注意，该算法将为O（N）。另一方面，跟踪数组中的活动元素的数量可以使您的算法在推送（也适用于弹出）时为O（1）。它还为您节省了在数组中分配一个额外元素的麻烦，如果它是一个结构数组，那么这可能很重要。

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