鏈棧的基本操作（入棧和出棧）

鏈棧，即用鏈表實現棧存儲結構。

鏈棧的實現思路同順序棧類似，順序棧是將數順序表(數組)的一端作為棧底，另一端為棧頂;鏈棧也如此，通常我們將鏈表的頭部作為棧頂，尾部作為棧底，如圖 1 所示：

圖 1 鏈棧示意圖

將鏈表頭部作為棧頂的一端，可以避免在實現數據 "入棧" 和 "出棧" 操作時做大量遍歷鏈表的耗時操作。

鏈表的頭部作為棧頂，意味著：

• 在實現數據"入棧"操作時，需要將數據從鏈表的頭部插入;

• 在實現數據"出棧"操作時，需要刪除鏈表頭部的首元節點;

因此，鏈棧實際上就是一個只能采用頭插法插入或刪除數據的鏈表。

鏈棧元素入棧

例如，將元素 1、2、3、4 依次入棧，等價于將各元素采用頭插法依次添加到鏈表中，每個數據元素的添加過程如圖 2 所示：

圖 2 鏈棧元素依次入棧過程示意圖

實現代碼為：

//鏈表中的節點結構
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
//stack為當前的鏈棧，a表示入棧元素
lineStack* push(lineStack * stack,int a){
    //創建存儲新元素的節點
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新節點與頭節點建立邏輯關系
    line->next=stack;
    //更新頭指針的指向
    stack=line;
    return stack;
}

鏈棧元素出棧

例如，圖 2e) 所示的鏈棧中，若要將元素 3 出棧，根據"先進后出"的原則，要先將元素 4 出棧，也就是從鏈表中摘除，然后元素 3 才能出棧，整個操作過程如圖 3 所示：

圖 3 鏈棧元素出棧示意圖

因此，實現棧頂元素出鏈棧的實現代碼為：

//棧頂元素出鏈棧的實現函數
lineStack * pop(lineStack * stack){
    if (stack) {
        //聲明一個新指針指向棧頂節點
        lineStack * p=stack;
        //更新頭指針
        stack=stack->next;
        printf("出棧元素：%d ",p->data);
        if (stack) {
            printf("新棧頂元素：%d\n",stack->data);
        }else{
            printf("棧已空\n");
        }
        free(p);
    }else{
        printf("棧內沒有元素");
        return stack;
    }
    return stack;
}

代碼中通過使用 if 判斷語句，避免了用戶執行"棧已空卻還要數據出棧"錯誤操作。

總結

本節，通過采用頭插法操作數據的單鏈表實現了鏈棧結構，這里給出鏈棧及基本操作的完整代碼：

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("彈棧元素：%d ",p->data);
        if (stack) {
            printf("棧頂元素：%d\n",stack->data);
        }else{
            printf("棧已空\n");
        }
        free(p);
    }else{
        printf("棧內沒有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

程序運行結果為：

彈棧元素：4 棧頂元素：3
彈棧元素：3 棧頂元素：2
彈棧元素：2 棧頂元素：1
彈棧元素：1 棧已空
棧內沒有元素