C语言中的意大利面堆栈

Question

有没有人知道在哪里能找到用C语言编写的意大利面栈的示例代码？

- Ralph

---

+1 是最奇怪的数据结构之一，几乎只在编译器符号表栈中有用。 - Jack

@Jack说：“除了‘几乎’这个词之外，意大利面堆栈在实现延续方面也非常有用。” - outis

@outis，你能详细说明一下意大利面栈的用途吗？因为我不知道这种数据结构是用来做什么的。 - Ayush

@Jerky: 除了在询问问题或答案方面需要澄清外，不应该使用评论提出其他问题。首先，SO是一个问答网站，而不是论坛，评论既不打算（也不适合）用于讨论。如果您有超出最初要求的问题，请首先查看适当的SE网站，是否已经提出了您的问题，如果没有，请发表新问题。由于您正在询问数据结构概念（而不是涉及代码的实现细节），请尝试[programmers.SE]（http://programmers.stackexchange.com/）。 - outis

Answer 1

应该是类似于这样的东西：

struct stack_item;

struct stack_item
{
    stack_item *parent;
    void *ptr_data;
};

stack_item *stack_pointer = null;

void push(stack_item *item)
{
    if (stack_pointer == null)
        item->parent = null;
    else
        item->parent = cur; 

stack_pointer = item;
}

/* like push but doesn't update cur stack item to the one pushed, just add a child */
void push_parallel(stack_item *item)
{
    if (stack_pointer == null)
    {
        stack_pointer = item;
        item->parent = null;
    }
    else
        item->parent = stack_pointer;
}

stack_item *pop()
{
    if (stack_pointer == null)
    {
        printf("error: stack is empty.\r\n");
        return null;
    }

    stack_item *current = stack_pointer;
    stack_pointer = current->parent;

    return current;
}

请注意，当您想要保留从堆栈弹出的事物的引用时，意大利面条堆栈非常有用，它具有许多平行的链接列表，这些列表最终指向共同的根。因此，您必须保留弹出的项目的引用，因为您需要以从叶子到根的自下而上的方式遍历它们，并且当然使用不同的叶节点将产生不同的链接列表，其中包含与从其他叶子开始的其他列表相同的元素。

- Jack

---

push_parallel函数不应该返回指向堆栈顶部的指针吗？ - Ralph

cur只是由于以不同的方式调用了stack_pointer而引起的错误，我已经修复了它。对于push_parallel函数，这取决于事实，即意大利面堆栈实际上没有一个栈顶，而是根据您开始访问它的位置有很多个，通常您必须自己关心堆栈外的引用。 - Jack