有許多不同類型的堆棧

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堆棧增加大量的空間開銷。