棧：限定只能在表尾進行插入和刪除的線性表。

鏈棧：使用鏈表表示的棧。

鏈棧特性：

• 只能棧頂插入和刪除元素。
• 無需預先分配大量存儲空間。
• 后進先出（Last In First Out）的線性表，后進入的元素先出棧，剩下的元素才能出棧。

優(yōu)點：

• 具有記憶功能，可用于表達式求值等操作。
• 無需預先分配大量存儲空間。

缺點：

• 需要為表中的邏輯關(guān)系增加額外的存儲空間。

時間復雜度

• 讀取時的時間復雜度為O(1)。
• 插入、刪除時的時間復雜度為O(1)。

鏈棧節(jié)點示意圖

鏈棧插入元素示意圖

鏈棧刪除元素示意圖

實現(xiàn)代碼如下：

// 鏈棧
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define OK 1      // 執(zhí)行成功
#define ERROR 0   // 執(zhí)行失敗
#define TRUE 1    // 返回值為真
#define FALSE 0   // 返回值為假

typedef int Status; // 函數(shù)返回結(jié)果類型
typedef int ElemType; // 元素類型

// 鏈棧節(jié)點
typedef struct StackNode {
    ElemType data; // 元素值
    struct StackNode *next; // 指向下一個節(jié)點的指針
}StackNode, *LinkStackPtr;

// 鏈棧結(jié)構(gòu)
typedef struct {
    LinkStackPtr top; // 棧頂指針
    int count; // 棧中元素個數(shù)
} LinkStack;

/**
 * 初始化棧
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status InitStack(LinkStack *S) {
    S->top = (LinkStackPtr) malloc(sizeof(StackNode)); // 為棧頂指針分配空間
    // 分配空間失敗，初始化錯誤
    if (!S->top) {
        return ERROR;
    }

    S->top = NULL; // 棧頂指針置空
    S->count = 0; // 棧中元素為0
    return OK;
}

/**
 * 清空棧中元素
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status ClearStack(LinkStack *S) {
    LinkStackPtr p, q; // p用于指向下一個元素，q指向被刪除元素

    p = S->top; // p指向棧頂
    // 當棧中還有元素時
    while (p) {
        q = p; // q指向當前元素
        p = p->next; // p指向下一個元素
        free(q); // 刪除q元素
    }
    S->count = 0; // 設(shè)置棧中元素個數(shù)為0
    return OK;
}

/**
 * 判斷棧是否為空
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status StackEmpty(LinkStack *S) {
    // 棧中元素個數(shù)為0
    if (S->count == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 獲取棧中元素個數(shù)
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status StackLength(LinkStack *S) {
    return S->count; // 返回棧中元素個數(shù)
}

/**
 * 獲取棧頂元素的值，存到元素e中
 * @param S 棧
 * @param e 用于存儲棧頂元素的值
 * @return 執(zhí)行狀態(tài)
 */
Status GetTop(LinkStack *S, ElemType *e) {
    // ?？赵貫榭眨@取失敗
    if (S->count == 0) {
        return ERROR;
    }

    *e = S->top->data; // 將棧頂元素的值存到元素e中
    return OK;
}

/**
 * 添加新元素e到棧頂
 * @param S 棧
 * @param e 新元素
 * @return 執(zhí)行狀態(tài)
 */
Status Push(LinkStack *S, ElemType e) {
    // 創(chuàng)建新節(jié)點
    LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));

    // 節(jié)點創(chuàng)建失敗
    if (!s) {
        return ERROR;
    }

    s->data = e; // 將新元素值賦值給新節(jié)點
    s->next = S->top; // 設(shè)置新節(jié)點的下一個元素指向棧頂元素
    S->top = s; // 設(shè)置棧頂指針指向新節(jié)點
    S->count++; // 棧中元素個數(shù)加1
    return OK;
}

/**
 * 彈出棧頂元素
 * @param S 棧
 * @param e 彈出元素
 * @return 執(zhí)行狀態(tài)
 */
Status Pop(LinkStack *S, ElemType *e) {
    LinkStackPtr p; // 指向被刪除元素的指針

    // 棧中元素為空，刪除失敗
    if (S->count == 0) {
        return ERROR;
    }

    *e = S->top->data; // 將棧頂元素的值賦值給元素e
    p = S->top; // p指向被刪除節(jié)點
    S->top = S->top->next; // 設(shè)置新的棧頂元素為被刪除節(jié)點的下一個元素
    free(p); // 刪除棧頂節(jié)點
    S->count--; // 棧中元素個數(shù)減1

    return OK;
}

/**
 * 打印單個元素的值
 * @param e 元素
 * @return 執(zhí)行狀態(tài)
 */
Status visit(ElemType e) {
    printf("%d ", e);
    return OK;
}

/**
 * 從棧頂開始遍歷棧中元素
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status StackTravel(LinkStack *S) {
    LinkStackPtr p; // 用于遍歷棧中元素的指針

    p = S->top; // p指向棧頂
    printf("[ ");
    // 當棧中還有元素
    while (p) {
        visit(p->data); // 打印該元素的值
        p = p->next; // p指向下一個節(jié)點
    }
    printf("]\n");
    return OK;
}

int main() {
    int j; // 用于遍歷
    LinkStack s; // 棧
    ElemType e; // 元素

    // 如果初始化成功
    if (InitStack(&s) == OK) {
        // 向棧中插入10個元素
        for (j = 1; j <= 10; j++) {
            Push(&s, j); // 向棧頂插入元素j
        }
    }

    printf("棧中的元素為：");
    StackTravel(&s); // 遍歷棧中元素

    Pop(&s, &e); // 彈出棧頂元素
    printf("彈出的棧頂元素為：e = %d\n", e);
    printf("彈出一個元素之后，棧是否為空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");

    GetTop(&s, &e); // 獲取棧頂元素的值
    printf("棧頂元素的值為：e = %d\n", e);

    printf("棧的長度為：%d\n", StackLength(&s)); // 獲取棧的長度

    ClearStack(&s); // 清空棧中元素
    printf("清空棧后，棧是否為空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");

    return 0;
}

運行結(jié)果