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

順序棧：使用數(shù)組實(shí)現(xiàn)的棧。

棧特性：

• 允許插入和刪除的一端叫棧頂（top），另一端叫棧底。
• 只能在棧頂插入和刪除元素。
• 后進(jìn)先出（Last In First Out）的線性表，后進(jìn)入的元素先出棧，剩下的元素才能出棧。

優(yōu)點(diǎn)：

• 具有記憶功能，可用于表達(dá)式求值等操作。
• 添加和刪除元素不需要移動(dòng)大量元素，只需要移動(dòng)棧頂指針。

缺點(diǎn)：

• 需分配大量存儲(chǔ)空間，無(wú)法有效利用資源。

時(shí)間復(fù)雜度

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

空棧示意圖

棧頂插入元素示意圖

棧頂刪除元素示意圖

實(shí)現(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   // 返回值為假
#define MAXSIZE 20 // 存儲(chǔ)空間初始分配大小

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

// 順序棧結(jié)構(gòu)
typedef struct {
    ElemType data[MAXSIZE]; // 用于存儲(chǔ)元素值
    int top; // 用于指示棧頂指針
}SqStack;

/**
 * 初始化棧
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status InitStack(SqStack *S) {
    S->top = -1; // 棧頂指針指向-1表示棧為空
    return OK;
}

/**
 * 清空棧中元素
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status ClearStack(SqStack *S) {
    S->top = -1; // 棧頂指針指向-1表示棧為空
    return OK;
}

/**
 * 判斷棧是否為空
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status StackEmpty(SqStack *S) {
    if (S->top == -1) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 獲取棧中元素個(gè)數(shù)
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
int StackLength(SqStack *S) {
    return S->top + 1;
}

/**
 * 獲取棧頂元素的值，存到元素e中
 * @param S 棧
 * @param e 用于存儲(chǔ)棧頂元素的值
 * @return 執(zhí)行狀態(tài)
 */
Status GetTop(SqStack *S, ElemType *e) {
    // 棧為空時(shí)，獲取棧頂元素失敗
    if (S->top == -1) {
        return ERROR;
    }

    // 將棧頂元素的值賦值給e元素
    *e = S->data[S->top];

    return OK;
}

/**
 * 添加新元素e到棧頂
 * @param S 棧
 * @param e 新元素
 * @return 執(zhí)行狀態(tài)
 */
Status Push(SqStack *S, ElemType e) {
    // 棧滿時(shí)，添加失敗
    if (S->top == MAXSIZE - 1) {
        return ERROR;
    }
    S->top++; // 棧頂指針加1
    S->data[S->top] = e; // 將新元素賦值給棧頂
    return OK;
}

/**
 * 彈出棧頂元素
 * @param S 棧
 * @param e 彈出元素
 * @return 執(zhí)行狀態(tài)
 */
Status Pop(SqStack *S, ElemType *e) {
    // 棧為空時(shí)，彈出元素失敗
    if (S->top == -1) {
        return ERROR;
    }
    *e = S->data[S->top]; // 將棧頂元素的值賦給e元素
    S->top--; // 棧頂指針減1
    return OK;
}

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

/**
 * 從棧底開始遍歷棧中元素
 * @param S 棧
 * @return 執(zhí)行狀態(tài)
 */
Status StackTraverse(SqStack S) {
    int i = 0; // 指示器，用于指示棧頂指針的位置

    printf("[ ");
    // 指示器位置小于棧頂指針
    while (i <= S.top) {
        visit(S.data[i++]); // 打印i位置元素，i向下一個(gè)元素移動(dòng)
    }
    printf("]\n");
    return OK;
}

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

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

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

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

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

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

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

    return 0;
}

運(yùn)行結(jié)果