栈

栈的基本概念

定义

栈：只允许在一端进行插入和删除操作的线性表。

特点

栈是一种线性表
只允许在一端进行插入删除操作
后进先出（LIFO）

栈顶： 进行插入删除的一端

栈底： 固定的，不可以进行插入删除的一端

空栈： 不含任何元素的空表

栈的基本操作

initStack(&S) // 初始化新栈
stackEmpty(&S) // 判断一个栈是否为空栈
push(&S, x) // 进栈，若栈未满，将x加入使之成为新栈顶
pop(&S, &x) // 出栈，若栈非空，弹出栈顶元素并用x返回
getTop(S, &x) // 读栈顶元素，若栈非空，用x返回栈顶元素
clearStack(&S) // 销毁栈，并释放S占用的内存

栈的顺序存储结构

实现

#define MAX_SIZE 100
typedef struct {
    ELEM_TYPE data[MAX_SIZE];
    int top;
} sqStack;

链式存储结构

实现

typedef struct linkStack {
    ELEM_TYPE data;
    struct linkStack *next;
} *linkStack;

队列

队列基本概念

队列的定义

也是一种操作受限的线性表，只允许在一端插入，另一端删除。

队列的特点

是一种线性表
一端插入一端删除，插入称为入队或进队，删除称为离队或出队。
先进先出（FIFO）

队头： 允许删除的一端，也称队首

队尾： 允许插入的一端

空队列： 不含任何元素的队列

基本操作

initQueue(&Q) // 初始化队列
queuEmpty(Q) // 判断一个队列是否为空
enQueue(&Q, x) // 入队，若队列未满则插入，使之成为新队尾
deQueue(&Q, &x) // 出队，若队列不为空，删除头元素，并用x返回
getHead(Q， &x) // 得队列的头元素，若队列不为空将头元素赋值给x

队列的顺序存储结构

#define MAX_SIZE 100
typedef struct {
    ELEM_TYPE data[MAX_SIZE];
    int front, rear;
} sqQueue;

队列的链式存储结构

typedef struct linkNode {
    ELEM_TYPE data;
    struct linkNode *next;
} linkNode;

typedef struct {
    linkNode *front, *rear;
} linkQueue;

双端队列

双端队列是指两端都能进行插入删除操作的队列。

其元素的逻辑结构依然是线性的，两端分写称为前端和后端。

输出受限的双端队列

允许在一端进行插入删除，另一端只允许插入的双端队列

输入受限的双端队列

允许在一端进行插入删除，另一端只允许删除的双端队列

队列与栈的运用

典型场景

栈：

函数调用，使用栈存储局部变量等
表达式计算，使用栈来计算表达式的值或几种表达式的转换
迷宫求解
进制转换

队列：

缓冲区
cpu调度

中缀表达式转后缀表达式

规则如下

从左向右读一个中缀表达式，维护一个运算符栈

如果遇到操作数，将其直接输出
如果遇到操作符或”(“，将其入栈
如果遇到”)”将栈内的操作符弹出并输出直到”(“为止，括号只弹出不输出
如果在栈顶元素不是”(“的情况下遇到其他操作符[“+”, “-“, “*”, “/“]等，从栈中弹出元素直到遇到优先级更低的运算符，或者弹出直到遇到左括号，然后将遇到的操作符入栈。注意：只有遇到右括号”)”时才弹出左括号”(“
如果读到了末尾，将栈中所有元素弹出

JS代码实现：

代码的实现只考虑了基本运算符，即加减乘除

function infix2suffix(exp) {
    // 优先级为1、2、3的操作符
    const o1 = ['+', '-']
    const o2 = ['*', '/']
    const o3 = ['(', ')']
    // 所有操作符的集合
    const operators = [...o1, ...o2, ...o3]
    // 操作符栈
    const stack = []
    // 将输入表达式拆成数组并去除空格
    const arr = exp.split('').filter(e => e !== ' ')
    let result = ''
    // 遍历输入表达式
    arr.forEach(e => {
        // top 是栈顶元素
        let top = stack[stack.length - 1];
        // 字符是操作数，直接输出
        if (!operators.includes(e)) {
            result += e
            return
        }
        // 栈为空或栈顶为左括号，操作符直接入栈
        if (!top || e === o3[0]) {
            stack.push(e)
            return
        }

        // p1, p2 分别为栈顶元素和读到的操作符的优先级
        let p1 = getPriority(top)
        const p2 = getPriority(e)

        // 如果读到了右括号，则将操作符输出并弹出，一直到弹出左括号，左括号只弹出
        if (p2 === 3) {
            for (let o = stack.pop(); o !== o3[0]; o = stack.pop()) {
                result += o;
            }
            return
        }

        // 如果读到的操作符优先级不比栈顶的优先级高，则出栈
        // 左括号只有在读到右括号时才出栈
        while (p2 <= p1 && p1 !== 3) {
            result += stack.pop()
            top = stack[stack.length - 1]
            p1 = getPriority(top)
        }
        // 将读到的操作符入栈
        stack.push(e)
        return
    })

    // 将栈中剩余的操作符出栈
    while (stack.length > 0) {
        result += stack.pop()
    }

    return result

    // 辅助函数，取操作符的优先级
    function getPriority(o) {
        if (o1.includes(o)) {
            return 1
        }
        if (o2.includes(o)) {
            return 2
        }
        if (o3.includes(o)) {
            return 3
        }
    }
}
console.log(infix2suffix('A + B * (C - D) - (E / F)'))

EOF

栈和队列

栈