c - C 函数栈顶实现

Question

出于学习目的，我正在用 C 语言实现一个通用堆栈。这是它的pop函数:

void* StackPop(Stack *s) {
    assert(s != NULL);
    assert(s->logicalLen > 0); // there must be at least on element
    void *object = (char*) s->elems + (s->logicalLen--) * s->elemSize; // decrement logical length
                                                                       // on the fly
    return object;
}

在这种情况下(StackPop)我很清楚，我必须将顶部对象的所有权转移给调用者。因此返回一个通用指针就可以了，因为调用者应该决定如何处理该对象。 另一方面，我想编写一个 StackTop() 函数来返回顶部元素。这对我来说非常不确定:我知道这两个函数应该非常相似，区别在于我不应该减少堆栈的大小或返回指针，因为我不希望客户端修改它。那么如何仅传递顶部元素的副本呢？接受通用指针作为参数是我唯一的选择并在该地址中进行深层复制吗？

void StackPop(void *target) {
    // make a deep copy into target address with memcopy or whatever?
}

有更好的方法吗？

Answer 1

I know that both functions should be very similar ...

谁说的？

您正在设计堆栈，因此您可以自由定义使用堆栈的所有规则。例如，您可以跳过对 NULL 指针的所有检查，只需在文档中写入使用 NULL 指针调用函数 xxx 会导致未定义的行为。最后，这取决于您希望堆栈达到什么程度 - 高性能、使用安全、易于使用等。

这同样适用于 StackPop 和 StackTop 函数。您可以自由设定规则。

对我来说，你的StackPop似乎在逻辑上是错误的。返回一个指向已通过递减逻辑Len逻辑上释放的内存区域的指针不是我所期望的。但是您可以在文档中写下 StackPop 返回的指针在下一个 StackPush 时变得无效。 (在 C++ 中，某些容器对迭代器/指针有此类限制)。

对于 StackTop 也是如此 - 您只需返回一个指向顶部元素的指针，并声明它仅在下一个 StackPop 之前有效。

这是你的设计，你的规则。

我宁愿这样做:

int push(stack* s, void* o)
{
    // memcpy contents of o to next free location
    // increment number of elements held
}

int top(stack* s, void* o)
{
    // memcpy top element to o
}

int pop(stack* s)
{
    // decrement number of elements held
}

在所有三种情况下，int 用于返回错误值。

为了提高性能，您可以提供一个函数，例如ptop 返回指向顶部元素的指针(仅在下一次弹出之前有效)。

关于深复制:

您无法在通用堆栈中进行深度复制。如果用户在堆栈中放入了一些内部有指针的东西，则用户必须自己处理它。