19_2.2.2 堆栈的顺序存储实现_哔哩哔哩_bilibili

表达式求值

表达式由运算数和运算符号构成。 中缀表达式： $a+b\times c-d/e$后缀表达式（逆波兰式）： $abc\times +de/-$ 数字与数字之前用空格分隔。 要处理后缀表达式，要求后放进去的元素先计算，先放进去的元素后计算，可以用栈实现。 [[2023.12.29#栈和队列]] 例如计算$\text{6 2 / 3 -4 2 *+}$，模拟堆栈过程为：

显然时间复杂度是$O(n)$

模拟实现

#define MaxSize
typedef struct SNode* Stack;
struct SNode{
    ElementType Data[MaxSize];
    int top;
};

如果top指向-1，则当前堆栈为空

压栈

#define MaxSize
typedef struct SNode* Stack;
struct SNode{
    ElementType Data[MaxSize];
    int top;
};

void push(Stack Ptrs,ElementType item){
    if(Ptrs->top == MaxSize - 1){
        printf("full");
        return;
    }else{
        Ptrs->Data[++(Ptrs->top)] = item;
        return;
    }
}

出栈

ElementType Pop(Stack Ptrs){
    if(Ptrs->top == -1){
        printf("empty");
        return ERROR;//elementtype特殊值
    }else{
        return (Ptrs->Data[(Ptrs->top)--];
    }
}

---

实操

请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。 可以让两个栈从数组两头向中间生长，如果栈顶指针相遇则说明栈满。

#define MaxSize
struct DStack{
    ElemntType Data[MaxSize];
    int top1;
    int top2;
} S;
S.top1 = -1;
S.top2 = MaxSize;

void Push(struct DStack *Ptrs,ElemntType item,int tag){//通过tag区分左右堆栈
    if(Ptrs->top2 - Ptrs->top1 == 1){
        printf("full");
        return;
    }
    if(tag == 1)
        Ptrs->Data[++(Ptrs->top1)] = item;
    else
        Ptrs->Data[--(Ptrs->top2)] = item;
}

ElemntType Pop(struct DStack *Ptrs,int tag){
    if(tag == 1){
        if(Ptrs->top1 == -1){
            printf("empty");
            return NULL;
        }else{
            return Ptrs->Data[(Ptrs->top1)--];
        }
    }else{
        if(Ptrs->top2 == MaxSize){
            printf("empty");
            return NULL;
        }else{
            return Ptrs->Data[(Ptrs->top2)++];
        }
    }
}

链表实现

20_2.2.3 堆栈的链式存储实现_哔哩哔哩_bilibili

typedef struct SNode *Stack;
struct SNode{
    ElementType Data;
    struct SNode *Next;
};

Stack CreateStack(){//创建堆栈头结点
    Stack s;
    S = (Stack)malloc(sizeof(struct SNode));
    S -> Next = NULL;
    return s;
}

int IsEmpty(Stack S){
    return (S->Next == NULL); 
}

void Push(ElementType item, Stack S){//压栈
    struct SNode *TmpCell;//创建一个节点
    TmpCell = (struct SNode*)malloc(sizeof(struct SNode));
    TmpCell -> Element = item;
    TmpCell -> Next = S->Next;
    S->Next = TmpCell;
}

ElementType Pop(Stack S){//删除并返回堆栈S的栈顶元素
    struct SNode *FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)){
        printf("Empty");
        return NULL;
    }else{
        FirstCell = S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

表达式求值

21_2.2.4 堆栈应用_表达式求值_哔哩哔哩_bilibili

中缀表达式向逆波兰式的转化

P1175 表达式的转换 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1. 运算顺序相对不变
2. 存储等待中的符号，通过堆栈实现
3. 处理括号 转化过程中碰到操作数就直接输出，碰到操作符的话先判断与栈顶元素的优先级大小关系，优先级更小的话就让栈顶元素出栈并输出，否则其本身入栈。 括号优先入栈，不优先出栈，入栈前括号优先级最高，入栈后括号优先级最低。遇到右括号时，将栈内左右括号之间的内容全部输出。

运算数:直接输出; 左括号:压入堆栈; 右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出); 运算符:

• 若优先级大于栈顶运算符时,则把它压栈;
• 若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出（放入 dat 栈，遇到^时中止）;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈;

若各对象处理完毕,则把堆栈中存留的运算符一并输出。

计算过程展现

展示计算过程需要以下栈：dat,op,num。 dat 栈内容为上一部分计算的结果，首先将 dat 栈中内容放入新的 op 栈（即倒序），然后开始读取 op 栈内容

1. 读到数字，加入 num 栈中
2. 读到运算符，从 num 栈中取两个元素，计算后放回 num 中
3. 倒序输出 num，正序输出 op记录详情

其他用途

函数调用及递归实现 [[通过C题重新深入讨论递归]] 深度优先搜索DFS [[通过C题重新深入讨论递归#递归实现的深度优先搜索]] 回溯算法