第二章 栈与队列

「栈」构造

顺序实现

typedef struct
{
    ElemType data[MaxSize];
    int top;
} Stack;

链式实现

typedef struct
{
    ElemType data[MaxSize];
    int top;
} Stack;

「栈」计算

• 当有n个不同的元素入栈，出栈序列的个数为卡特兰数：${\displaystyle \frac{1}{𝑛+1}{C}_{2𝑛}^n}$
• 给定二叉树的前序序列作为入栈队列，则所有的出栈为所有可能的中序遍历

第二节 队列

「队列」构造

typedef struct
{
    ElemType data[MaxSize];
    int front, rear; //队头和队尾指针
} SqQueue;

「队列」中缀转后缀

• 操作数：直接加入表达式
• 界限符
  • “(”：直接入栈
  • “)”：依次弹出运算符，直到“(”为止
• 运算符
  • 依次弹出栈中优先级大于等于当前运算符的所有运算符
  • 碰到“(”或栈空停止