系統程式員成長計劃-組合的威力（三）

棧

棧是一種後進先出(LIFO, last in firstout)的資料結構，與隊列的先進先出(FIFO)相比，這種規則似乎不太公平，計算機可不管這個。事實上，棧是最重要的資料結構之一：沒有棧，基于下推

自動機的編譯器不能工作，我們隻能寫彙程式設計式。沒有棧，無法實作遞歸/多級函數調用，程式根本就無法工作。

棧主要的接口函數有：

o 建立棧 stack_create

o 取棧頂元素 stack_top

o 放入元素到棧頂stack_push

o 删棧棧頂元素stack_pop

o 取棧中元素個數 stack_length

o 周遊棧中的元素stack_foreach

o 銷毀棧 stack_destroy

棧同樣是連結清單和數組的一種特殊形式而已，下面我們重用連結清單來實作棧：

o 棧的資料結構

struct _Stack      

{      

DList* dlist;      

};      

這裡和隊列的資料結構一樣，由一個連結清單組成。

o 建立棧

Stack* stack_create(DataDestroyFunc data_destroy, void* ctx)      

{      

Stack* thiz = (Stack*)malloc(sizeof(Stack));      

if(thiz != NULL)      

{      

if((thiz->dlist = dlist_create(data_destroy, ctx)) == NULL)      

{      

free(thiz);      

thiz = NULL;      

}      

}      

return thiz;      

}      

建立棧時，除了配置設定自己的空間外，就是簡單的建立一個雙向連結清單。

o 取棧頂元素

Ret      stack_top(Stack* thiz, void** data)      

{      

return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);      

return dlist_get_by_index(thiz->dlist, 0, data);      

}      

我們認為連結清單的第一個元素是棧頂，取棧頂的元素就是取連結清單的第一個元素。

o 放入元素到棧頂

Ret      stack_push(Stack* thiz, void* data)      

{      

return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);      

return dlist_prepend(thiz->dlist, data);      

}      

放入元素到棧頂就是插入一個元素到連結清單頭。

o 删棧棧頂元素

Ret      stack_pop(Stack* thiz)      

{      

return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);      

return dlist_delete(thiz->dlist, 0);      

}      

删棧棧頂元素就是删除連結清單的第一個元素。

o 取棧中元素個數

size_t   stack_length(Stack* thiz)      

{      

return_val_if_fail(thiz != NULL, 0);      

return dlist_length(thiz->dlist);      

}      

棧中的個數等同于連結清單的個數。

o 周遊棧中的元素

Ret      stack_foreach(Stack* thiz, DataVisitFunc visit, void* ctx)      

{      

return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);      

return dlist_foreach(thiz->dlist, visit, ctx);      

}      

周遊棧中的元素等同于周遊連結清單中的元素。

o 銷毀棧

void stack_destroy(Stack* thiz)      

{      

if(thiz != NULL)      

{      

dlist_destroy(thiz->dlist);      

thiz->dlist = NULL;      

free(thiz);      

}      

return;      

}      

銷毀雙向連結清單然後釋放自身的空間。

棧是一個非常重要的資料，但奇怪的是我們很少有機會去寫它。事實上，我從來沒有在工作中寫過一個棧。這是怎麼回事呢？原因是我們的計算機本身是基于棧的，很多事情計算機已經在我們不知道的情況下幫我們處理了，比如函數調用（特殊是遞歸調用），計算機幫我們處理了。用遞歸下降進行的文法分析利用了函數

調用的遞歸性，也不需要顯式的構造棧。