該系列文章主要作數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）學(xué)習(xí)的筆記玫坛。里面代碼的注釋很詳細(xì)滋觉，同時(shí)提供給大家參考，歡迎指正和指教昌渤。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)赴穗，簡(jiǎn)稱為鏈棧。

棧因?yàn)橹皇菞ｍ攣?lái)做插入和刪除操作愈涩，所以比較好的方法是將棧頂放在單鏈表的頭部望抽，棧頂指針和單鏈表的指針合二為一。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼實(shí)現(xiàn)

typedef int SElemType;
// 定義鏈棧
typedef struct StackNode{
    
    SElemType data; // 存放棧的數(shù)據(jù)
    struct StackNode * next;
    
}StackNode, *LinkStackPtr;

typedef struct LinkStack{
    
    LinkStackPtr top; // top指針
    int count; // 棧元素計(jì)數(shù)器
    
}linkStack;

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作

一履婉、鏈棧的基本操作：初始化、獲取鏈棧的長(zhǎng)度斟览、判斷是否為空毁腿、獲取棧頂元素等

/**
 * 初始化
 */
Status InitStack(linkStack *S){
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    if(!S->top)
        return ERROR;
    S->top=NULL;
    S->count=0;
    return OK;
}

/**
 * 獲取元素
 */
Status visit(SElemType c){
    printf("%d ",c);
    return OK;
}

/**
 * 清空棧
 */
Status ClearStack(linkStack *S){
    LinkStackPtr p,q;
    p=S->top;
    while(p)
    {
        q=p;
        p=p->next;
        free(q);
    }
    S->count=0;
    return OK;
}

/**
 * 判斷棧是否問(wèn)空
 */
Status StackEmpty(linkStack S){
    if (S.count==0)
        return TRUE;
    else
        return FALSE;
}

/**
 * 計(jì)算棧的長(zhǎng)度
 */
int StackLength(linkStack S){
    return S.count;
}
/**
 * 獲取棧頂并返回
 */
Status GetTop(linkStack S,SElemType *e){

    if (S.top == NULL) {
        return ERROR;
    }else{
        *e = S.top->data;
    }
    return OK;
}

二、進(jìn)棧操作(Push)

對(duì)于鏈棧的進(jìn)棧(Push)操作，假設(shè)元素值為e的新節(jié)點(diǎn)是s已烤，top為棧頂指針鸠窗，插入元素e的代碼如下

/**
 * 插入元素 e 為新的棧頂元素
 */
Status Push(linkStack * S, SElemType e){
    
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;   //把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼
    S->top = p;        // 將新節(jié)點(diǎn)p賦值給棧頂指針。
    S->count++;
    
    return OK;
}

三胯究、出棧操作(Pop)

至于鏈棧的出棧操作稍计，也是簡(jiǎn)單的三句操作。

• 假設(shè)變量p用來(lái)存儲(chǔ)要?jiǎng)h除的棧頂結(jié)點(diǎn)裕循。
• 將棧頂指針下移一位
• 釋放p臣嚣。

/**
 * 出棧
 */
Status Pop(linkStack * S, SElemType *e){
    
    LinkStackPtr p;
    
    if (StackEmpty(*S)) // 棧為空
        return ERROR;
    
    *e = S->top->data;
    p = S->top;           // 棧頂結(jié)點(diǎn)賦值給p
    S->top = S->top->next; //棧頂指針下移一位
    free(p);
    S->count--;
    return OK;
}

四、遍歷鏈棧操作(Traverse)

/**
 * 遍歷
 */
Status StackTraverse(linkStack S){
    LinkStackPtr p;
    p=S.top;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

測(cè)試代碼

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        int j;
        linkStack s;
        int e;
        if (InitStack(&s)) {  //將1到10依次進(jìn)棧
            for (j = 1; j <= 10; j++) {
                Push(&s, j);
            }
        }
        printf("棧中的元素依次為：");
        StackTraverse(s);
        Pop(&s,&e);
        printf("彈出的棧頂元素 e=%d\n",e);
        printf("棸疲空否：%d(1:空 0:否)\n",StackEmpty(s));
        GetTop(s,&e);
        printf("棧頂元素 e=%d 棧的長(zhǎng)度為%d\n",e,StackLength(s));
        ClearStack(&s);
        printf("清空棧后硅则，棧空否：%d(1:空 0:否)\n",StackEmpty(s));
    }
    return 0;
}

測(cè)試結(jié)果

對(duì)比順序棧和鏈棧

• 時(shí)間復(fù)雜度：均為O(1)
• 空間性能：
  • 順序棧需要事先確定一個(gè)固定的長(zhǎng)度株婴，可能會(huì)存在內(nèi)存空間浪費(fèi)的問(wèn)題怎虫。但是它的優(yōu)勢(shì)在于存取的時(shí)候很方便。
  • 鏈棧要求每個(gè)元素都有指針域困介，也增加了內(nèi)存開銷大审，但是對(duì)于棧的長(zhǎng)度無(wú)限制。
• 總體而言：如果棧的使用過(guò)程中元素變化不可預(yù)料座哩，有時(shí)很小徒扶，有時(shí)很大，那么最好用鏈棧八回，反之酷愧，如果變化在可控范圍，使用順序棧更好缠诅。