有许多不同类型的堆栈

Question

我正在制作一个需要使用两个堆栈的C程序。一个需要持有chars，另一个需要持有双打。我有两个结构，节点和堆栈：

struct node { 
    double value; 
    struct node *next; 
    struct node *prev; 
}; 

struct stack { 
    struct node *last; 
    struct node *curr; 
}; 

问题是我需要每种类型之一。我能想到的唯一的事情是有两个独立的结构（即char_node，double_node，char_stack，double_stack）。如果这是C++，我会使用模板，但当然我不能在C.

我记得有一件事可以用于这个是void指针。这会起作用吗？它会不会很实际？

Answer 1

您可以使用联合。

这里有一些关于unions的信息。

Answer 2

为什么不使用联合？

struct node { 
    union { 
     double d_value; 
     char c_value; 
    } val; 
    struct node *next; 
    struct node *prev; 
}; 

Answer 3

好的，但你显示的节点结构似乎属于双链表，而不是堆栈。你真的在考虑堆叠吗？您显示的动态分配链接节点的链会在一瞬间消耗您的内存。

我建议你重新考虑这个基础设计。你应该使用更有效的内存（也许我不知道你的特殊情况，但这是一般的方法，这实际上可能导致2个不同类型的对象的堆栈以保持数据对齐（你不会喜欢1字节的字符例如在普通存储区中混合4字节长）

但这只是我的看法，根据我对此的经验，可能对您的情况有用;）。

Answer 4

1. 如果你真的想用一个链表作为堆栈你不需要next和prev，就在旁边。您也不需要尾部/头部指针（示例代码中的“最后一个”）。在堆栈中，你只关心顶级元素。

2. 如果你正在实现一个栈来保存char和double类型，为什么不声明每个类型的数组并保存一个指向数组中最后一个有效元素的指针呢？然后当你想推入数组时，你增加指针并设置值。要弹出，请做相反的操作：获取值并减少指针。使用数组意味着一次性分配所有可能需要的内存，而不是每次要将新节点推入堆栈时。

Answer 5

如果每个栈只需要保存一个数据类型，联合和void指针是矫枉过正的。制作一个DoubleStackNode和一个CharStackNode - 这就是C++模板（即StackNode<T>）无论如何都会在幕后执行的。

不要为了制作一些超一般的全面解决方案而自杀。你只需要两种类型的堆栈。

您可以使用联合，但这样做会为char堆栈增加大量的空间开销。