栈（顺序栈）

栈：限定只能在表尾进行插入和删除的线性表。

顺序栈：使用数组实现的栈。

栈特性：

• 允许插入和删除的一端叫栈顶（top），另一端叫栈底。
• 只能在栈顶插入和删除元素。
• 后进先出（Last In First Out）的线性表，后进入的元素先出栈，剩下的元素才能出栈。

优点：

• 具有记忆功能，可用于表达式求值等操作。
• 添加和删除元素不需要移动大量元素，只需要移动栈顶指针。

缺点：

• 需分配大量存储空间，无法有效利用资源。

时间复杂度

• 读取时的时间复杂度为O(1)。
• 插入、删除时的时间复杂度为O(1)。

空栈示意图 栈顶插入元素示意图 栈顶删除元素示意图

实现代码如下：

// 顺序栈
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define OK 1      // 执行成功
#define ERROR 0   // 执行失败
#define TRUE 1    // 返回值为真
#define FALSE 0   // 返回值为假
#define MAXSIZE 20 // 存储空间初始分配大小

typedef int Status; // 函数返回结果类型
typedef int ElemType; // 元素类型

// 顺序栈结构
typedef struct {
    ElemType data[MAXSIZE]; // 用于存储元素值
    int top; // 用于指示栈顶指针
}SqStack;

/**
 * 初始化栈
 * @param S 栈
 * @return 执行状态
 */
Status InitStack(SqStack *S) {
    S->top = -1; // 栈顶指针指向-1表示栈为空
    return OK;
}

/**
 * 清空栈中元素
 * @param S 栈
 * @return 执行状态
 */
Status ClearStack(SqStack *S) {
    S->top = -1; // 栈顶指针指向-1表示栈为空
    return OK;
}

/**
 * 判断栈是否为空
 * @param S 栈
 * @return 执行状态
 */
Status StackEmpty(SqStack *S) {
    if (S->top == -1) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 获取栈中元素个数
 * @param S 栈
 * @return 执行状态
 */
int StackLength(SqStack *S) {
    return S->top + 1;
}

/**
 * 获取栈顶元素的值，存到元素e中
 * @param S 栈
 * @param e 用于存储栈顶元素的值
 * @return 执行状态
 */
Status GetTop(SqStack *S, ElemType *e) {
    // 栈为空时，获取栈顶元素失败
    if (S->top == -1) {
        return ERROR;
    }

    // 将栈顶元素的值赋值给e元素
    *e = S->data[S->top];

    return OK;
}

/**
 * 添加新元素e到栈顶
 * @param S 栈
 * @param e 新元素
 * @return 执行状态
 */
Status Push(SqStack *S, ElemType e) {
    // 栈满时，添加失败
    if (S->top == MAXSIZE - 1) {
        return ERROR;
    }
    S->top++; // 栈顶指针加1
    S->data[S->top] = e; // 将新元素赋值给栈顶
    return OK;
}

/**
 * 弹出栈顶元素
 * @param S 栈
 * @param e 弹出元素
 * @return 执行状态
 */
Status Pop(SqStack *S, ElemType *e) {
    // 栈为空时，弹出元素失败
    if (S->top == -1) {
        return ERROR;
    }
    *e = S->data[S->top]; // 将栈顶元素的值赋给e元素
    S->top--; // 栈顶指针减1
    return OK;
}

/**
 * 打印单个元素的值
 * @param e 元素
 * @return 执行状态
 */
Status visit(ElemType e) {
    printf("%d ", e);
    return OK;
}

/**
 * 从栈底开始遍历栈中元素
 * @param S 栈
 * @return 执行状态
 */
Status StackTraverse(SqStack S) {
    int i = 0; // 指示器，用于指示栈顶指针的位置

    printf("[ ");
    // 指示器位置小于栈顶指针
    while (i <= S.top) {
        visit(S.data[i++]); // 打印i位置元素，i向下一个元素移动
    }
    printf("]\n");
    return OK;
}

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

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

    printf("栈中的元素为：");
    StackTraverse(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;
}

运行结果