【C/C++】泛型棧

用 C 語言實作泛型棧

mystack.h

1 #ifndef __MYSTACK_H__
 2 #define __MYSTACK_H__
 3 
 4 #include <assert.h>
 5 
 6 // C style，不使用C++的class
 7 typedef struct {
 8     void *elems;
 9     int elemSize;    // 元素大小
10     int logicLen;    // 邏輯長度，棧中目前元素個數，也是下個進棧元素的下标
11     int allocLen;    // 配置設定的最大記憶體長度
12     void (*freefn)(void *);    // Free函數指針，用于釋放棧元素的記憶體
13 }stack;
14 
15 // 構造函數
16 void StackNew(stack *s, int elemSize, void (*freefn)(void *) = NULL) {
17     s->elemSize = elemSize;
18     s->logicLen = 0;
19     s->allocLen = 4;    // 初始為棧開辟4個元素的記憶體
20     s->elems = malloc(s->allocLen * elemSize);
21     assert(s->elems);    // 表達式為0則報錯
22     s->freefn = freefn;
23 }
24 
25 // 析構函數
26 void StackDispose(stack *s) {
27     if (s->freefn) {
28         for (int i = 0; i < s->logicLen; i++) {
29             s->freefn((char *)s->elems + i * s->elemSize);
30         }
31     }
32     free(s->elems);
33 }
34 
35 void StackPush(stack *s, void *elemAddr) {
36     if (s->logicLen == s->allocLen) {
37         s->allocLen <<= 1;
38         s->elems = realloc(s->elems, s->allocLen * s->elemSize);
39         assert(s->elems);    // 如果realloc失敗，s->elem還會是原來那片記憶體，并不是NULL，但realloc函數會傳回NULL
40     }
41     void *target = (char *)s->elems + s->logicLen * s->elemSize;    // 目的位址
42     memcpy(target, elemAddr, s->elemSize);
43     s->logicLen++;
44 }
45 
46 void StackPop(stack *s, void *elemAddr) {
47     assert(s->logicLen > 0);
48     s->logicLen--;
49     void *source = (char *)s->elems + s->logicLen * s->elemSize;    // 棧頂元素位址
50     memcpy(elemAddr, source, s->elemSize);
51 }
52 
53 #endif      

分析：

1、為了實作存放 int 型、double 型、char * 型、自定義類型元素的棧（泛型棧），需要定義一個指明元素大小的變量 elemSize，在棧初始化時傳入以開辟足夠大小的空間。注意 malloc() 後 assert() 的運用，在記憶體申請失敗時直接退出。

2、如果存儲的是基本資料類型，如 char、int 等或者是成員不包含指針的結構體類型，析構函數隻需要 free(elems)，而對棧中每個元素則不需要手動 free；如果存儲的元素是 char * ，或是指向結構體的指針，或是指向動态申請記憶體的指針等等，就需要在調用 StackDispose() 之前，将清理棧中元素的方式的資訊傳給構造函數，即函數指針（指向一段代碼）。作為棧結構體的第 5 個成員，它預設是空指針（對于基本資料類型），要麼是某個合法的 freefn() 指針（對于使用者指定資料結構）。

3、入棧函數 StackPush() 使用 realloc 不斷地增長棧的記憶體空間。對于基礎資料類型，elems[logicLen] 即為棧頂元素；而泛型棧中，則需要從具體的記憶體位址中找到相應的棧頂位置 target，這裡同樣使用了 void * → char * 的小技巧，并使用 memcpy() 将要入棧的元素拷貝到棧頂位址中去。

4、出棧函數 StackPop() 将出棧元素放在函數的參數清單中，由使用者提供一個位址，棧擷取棧頂位址指向的元素并将其拷貝到該位址指向的記憶體中。

main() 函數

1 void StrFree(void *vp) {
 2     free(*(char **)vp);
 3 }
 4 
 5 int main() {
 6     /* int棧 */
 7     stack intStack;
 8     StackNew(&intStack, sizeof(int));
 9     for (int i = 1; i <= 5; i++) {
10         StackPush(&intStack, &i);
11     }
12     int top;
13     for (int i = 0; i < 5; i++) {
14         StackPop(&intStack, &top);
15         cout << top << endl;
16     }
17     StackDispose(&intStack);
18     /* string棧 */
19     const char *players[] = {"Niko", "Miracle-" ,"Sky" ,"pigff" ,"Yaphets"};
20     stack strStack;
21     StackNew(&strStack, sizeof(char *), StrFree);
22     for (int i = 0; i < 5; i++) {
23         char *copy = strdup(players[i]);
24         StackPush(&strStack, &copy);
25     }
26     char *player;
27     for (int i = 0; i < 5; i++) {
28         StackPop(&strStack, &player);
29         cout << player << endl;
30         free(player);
31     }
32     StackDispose(&strStack);
33     return 0;
34 }      

分析：

1、strFree() 函數，雖然接受的參數 vp 是 void *（為了類型通用），但我們編寫該函數時邏輯上知道 vp 是 char ** 類型

2、WHY 不在 StackPop()（彈出棧頂元素）之前，釋放棧頂字元串的記憶體空間？？？

     因為 StackPop() 函數實際上并沒有将一份棧頂字元串的拷貝傳回給使用者，而是擷取棧頂字元串所在記憶體的位址，并用 memcpy() 複制到使用者提供的空間（player），即使用者擷取的是一個指向該字元串的指針，該字元串的所有權由棧交給使用者，是以彈出來的 player 應當由使用者需要自行 free()。并且字元串拷貝函數 strdup() 在内部調用了 malloc() 動态配置設定記憶體，應該與 free() 成對出現。

輸出結果：

以上。

轉載于:https://www.cnblogs.com/wayne793377164/p/8854676.html