1. 棧的概念

在開始前，請牢記這句話：棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)。

棧（stack）是限定僅在表的一端進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)，請聯(lián)系我們前文所學(xué)的，設(shè)想一個(gè)單鏈表我們只能夠?qū)ζ滏湵淼谋砦步Y(jié)點(diǎn)進(jìn)行操作，而操作也只能夠進(jìn)行插入一個(gè)新的結(jié)點(diǎn)與刪除最末尾的這個(gè)結(jié)點(diǎn)兩個(gè)操作，而這樣強(qiáng)限制性的‘鏈表’，就是我們所說的棧。

讓我們重新理順一下定義：棧是一個(gè)線性的數(shù)據(jù)結(jié)構(gòu)，規(guī)定這個(gè)數(shù)據(jù)結(jié)構(gòu)只允許在其中一端進(jìn)行操作，并禁止直接訪問除這一端以外的數(shù)據(jù)。

如圖：棧就像一個(gè)放球的單管桶，只允許球從桶的開口這一端取出，并且球先放入桶中則后從桶中拿出。

2. 棧的結(jié)點(diǎn)設(shè)計(jì)

棧分為數(shù)組棧和鏈表?xiàng)＃鋮^(qū)別是數(shù)組棧使用數(shù)組進(jìn)行功能的模擬，實(shí)現(xiàn)較為快速和便利，而鏈表?xiàng)Ｊ褂面湵淼乃悸啡ピO(shè)計(jì)，實(shí)現(xiàn)較為麻煩，但是其穩(wěn)定不易出錯(cuò)；在鏈表?xiàng)Ｖ杏址譃殪o態(tài)鏈表?xiàng)：蛣討B(tài)鏈表?xiàng)?，靜態(tài)鏈表?xiàng)＝o定棧的空間大小，不允許超過存儲超過給定數(shù)據(jù)大小的元素，而動態(tài)棧使用的是自動創(chuàng)建空間的方法進(jìn)行創(chuàng)建，只要符合機(jī)器的硬件要求以及編譯器的控制，其理論上是極大的。

說了那么多，我們以鏈表?xiàng)５膭討B(tài)鏈表?xiàng)槔?，進(jìn)行棧的設(shè)計(jì)，在后文直接以棧一名字稱呼動態(tài)鏈表?xiàng)?，這也是各類語言標(biāo)準(zhǔn)模板中棧的實(shí)現(xiàn)方式。

首先是棧的結(jié)點(diǎn)設(shè)計(jì)，我們可以設(shè)計(jì)出兩個(gè)結(jié)構(gòu)體，一個(gè)結(jié)構(gòu)體Node表示結(jié)點(diǎn)，其中包含有一個(gè)data域和next指針。

其中data表示數(shù)據(jù)，其可以是簡單的類型（如int,double等等），也可以是復(fù)雜的結(jié)構(gòu)體（struct類型）；

next指針表示，下一個(gè)的指針，其指向下一個(gè)結(jié)點(diǎn)，通過next指針將各個(gè)結(jié)點(diǎn)鏈接。

目前的設(shè)計(jì)如同單鏈表，接下來，為這個(gè)進(jìn)行限制性的設(shè)計(jì)，我們額外添加一個(gè)結(jié)構(gòu)體，其包括了一個(gè)永遠(yuǎn)指向棧頭的指針top和一個(gè)計(jì)數(shù)器count記錄元素個(gè)數(shù)，（也可以設(shè)計(jì)成一個(gè)指針top和一個(gè)指針bottom分別指向棧頭和棧尾）其主要功效就是設(shè)定允許操作元素的指針以及確定棧何時(shí)為空（count的方法是當(dāng)count為0時(shí)為空，top和bottom方法就是兩者指向同一個(gè)空間時(shí)為棧為空）

這里我采用的是top和count組合的方法。其代碼可以表示為：

//棧的結(jié)點(diǎn)設(shè)計(jì)
//單個(gè)結(jié)點(diǎn)設(shè)計(jì)，數(shù)據(jù)和下一個(gè)指針
typedef struct node     
{
    int data; 
    struct node *next;
} Node;
//利用上面的結(jié)點(diǎn)創(chuàng)建棧，分為指向頭結(jié)點(diǎn)的top指針和計(jì)數(shù)用的count
typedef struct stack    
{
    Node *top;
    int count;
} Link_Stack;

3. 棧的基本操作—入棧

如圖：

入棧(push)操作時(shí)，我們只需要找到top所指向的空間，創(chuàng)建一個(gè)新的結(jié)點(diǎn)，將新的結(jié)點(diǎn)的next指針指向我們的top指針指向的空間，再將top指針轉(zhuǎn)移，指向新的結(jié)點(diǎn)，即是入棧操作

其代碼可以表示為：

//入棧 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
    if (p == NULL)
        return NULL;
    Node *temp;
    temp=(Node*)malloc(sizeof(Node));
    //temp = new Node;
    temp->data = elem;
    temp->next = p->top;
    p->top = temp;
    p->count++;
    return p;
}