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

鏈棧，即用鏈表實現(xiàn)棧存儲結構。

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

圖 1 鏈棧示意圖

將鏈表頭部作為棧頂?shù)囊欢耍梢员苊庠趯崿F(xiàn)數(shù)據(jù) "入棧" 和 "出棧" 操作時做大量遍歷鏈表的耗時操作。

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

• 在實現(xiàn)數(shù)據(jù)"入棧"操作時，需要將數(shù)據(jù)從鏈表的頭部插入;

• 在實現(xiàn)數(shù)據(jù)"出棧"操作時，需要刪除鏈表頭部的首元節(jié)點;

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

鏈棧元素入棧

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

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

實現(xiàn)代碼為：

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

鏈棧元素出棧

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

圖 3 鏈棧元素出棧示意圖

因此，實現(xiàn)棧頂元素出鏈棧的實現(xiàn)代碼為：

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

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

總結

本節(jié)，通過采用頭插法操作數(shù)據(jù)的單鏈表實現(xiàn)了鏈棧結構，這里給出鏈棧及基本操作的完整代碼：

#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("棧內(nèi)沒有元素");
        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 棧已空
棧內(nèi)沒有元素