第3章 栈和队列
3.1 复习笔记
一、栈
1栈的定义与基本操作
（1）栈的定义
栈是被限定仅在表尾进行插入或删除操作的线性表。栈中数据元素同属一种数据类型，数据元素之间呈线性关系。假设栈中有n个数据元素（a1，a2，…，an），则对每一个元素ai（i＝1，2，…，n－1）都存在关系<ai，ai＋1>，并且a1无前驱，an无后继。
其中，表尾端称为栈顶（top），表头端称为栈底（bottom），如图3-1所示。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出的线性表（简称LIFO结构）。
图3-1 栈的示意图
（2）栈的基本操作
①INISTACK(S)：初始化函数。
②EMPTY(S)：判栈空函数。
③PUSH(S,x)：入栈函数。
④POP(S)：出栈函数。
⑤GETTOP(S)：取栈顶元素函数。
⑥CLEAR(S)：栈置空操作。
⑦CURRENT-SIZE(S)：求当前栈中元素个数函数。
2栈的表示和实现
（1）顺序栈
顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。
栈满：top＝arrmax时表栈满，此时不能进行入栈操作。
栈空：top＝0时表栈空，此时不能进行出栈和取栈顶元素等操作。
【注意】共享栈是指两个栈共享一个数组空间，也是顺序栈的一种。它将两个栈的栈底设置在数组的两端（设top1＝－1，top2＝maxSize为栈空），入栈则分别向数组的中间位置靠近，若两栈“相遇”（top2－top1＝1），则栈满。
（2）链栈
采用链式存储结构存储的栈叫链栈。一个链栈由其栈顶指针唯一确定，且链栈一般不存在栈满的情况。链栈如图3-2所示。
图3-2 链栈示意图
二、栈的应用举例
1括号匹配
括号匹配算法如下：
①初始化一个空栈，从表达式中顺序读入括号。
②当读到左括号时进行入栈操作，且该左括号具有当前等待匹配的括号中最高的优先级。
③当读到右括号时进行出栈操作，从栈顶取出具有最高优先级的括号，看是否与右括号相匹配。
当栈空且读完表达式中所有括号，算法结束。
【注意】当表达式中出现了其他形式的括号时，匹配步骤不变。
2表达式求值
算符优先法（一种根据算术四则运算关系的规定来实现表达式求值的算法）算法如下：
①定义两个栈，一个用于寄存运算符（OPTR栈），一个用于寄存操作数或者计算结果（OPND栈）。
②置操作数栈（OPND）为空，表达式起始符“#”为运算符栈（OPTR）的栈底元素。
③依次读入表达式中的字符，若该字符为操作数，则进入OPND栈；若是运算符，则和OPTR栈顶运算符比较优先级，若该字符优先级低于OPTR栈顶元素优先级，则需将OPTR栈顶运算符代入相关运算后再进行入栈操作，反之直接入栈，直到求得结果（即OPTR栈顶元素和当前读入字符均为“#”）。
【注意】如表3-1所示定义了算符之间的优先关系。
表3-1 算符间的优先关系
三、栈与递归的实现
1递归的定义
一个直接调用自身或通过一系列过程调用语句间接地调用自身的过程，称做递归过程。
（1）分类
①直接递归
例如：
PROCENDURE A;
BEGIN
…
A;
…
END;
过程A中的语句直接调用了过程A本身，这叫做直接递归调用。
②间接递归
例如：
PROCENDURE B; PROCENDURE C;
BEGIN BEGIN
… …
C; B;
… …
END; END;
过程B中调用了过程C，而过程C又调用了过程B。这两个过程都通过另一个过程间接调用了它们自身，这就叫做间接递归调用。
（2）优缺点
①优点：
能将原始问题转换成属性相同但规模较小的子问题，程序更加易读，结构更加清晰。
②缺点：
递归程序时空复杂度一般比非递归程序高，运行效率也更低。
2栈在递归中的应用
栈一般被应用在递归程序转换成非递归程序中，将原本由系统管理的递归过程改为程序员管理。在非递归程序中，栈有两个作用：
（1）将本层递归调用时的实际参数和返回地址传递给下一层递归；
（2）保存本层参数和局部变量，从下一层返回本层时继续恢复使用。
四、队列
1队列的定义与基本操作
（1）队列的定义
队列中数据元素同属一种数据类型，数据元素之间呈线性关系。假设队列中有n个数据元素（a1，a2，…，an），则对每一个元素ai（i＝1，2，…，n－1）都存在关系（ai，ai＋1），并且a1无前驱，an无后继。
队列是一种先进先出（FIFO）的线性表。它只允许在表的一端插入元素，而在另一端删除元素。允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。
【注意】特殊的队列——双端队列
双端队列是限定插入和删除操作在表的两端进行的线性表，如图3-3所示。双端队列能够在端1和端2分别进行操作。其中，双端队列能够根据实际情况对其进行限定，比如限定只允许端1进行插入，端1和端2均能进行删除的双端队列。
图3-3 双端队列
（2）队列的基本操作
①INIQUEUE(Q)：初始化函数。
②EMPTY(Q)：判空函数。
③ENQUEUE(Q,x)：入队列函数。
④DLQUEUE(Q)：出队列函数。
⑤GETHEAD(Q)：取队头元素函数。
⑥CLEAR(Q)：队列置空函数。
⑦CURRENT_SIZE(Q)：求队列当前所含元素个数的函数。
2队列的表示与实现
（1）队列的顺序存储结构
①队列的顺序存储
队列的顺序存储是指分配一块连续的存储空间存储队列中的元素，并设立front指针指向队头位置，设立rear指针指向队尾位置（一般front指向队头元素，rear指向队尾元素的下一位置）。
②循环队列
把存储队列元素的表从逻辑上看作一个环，即为循环队列。它能够避免一般顺序存储的队列出现的“假溢出”（队列在进行多次入队和出队操作后导致存储空间剩余而无法继续入队）现象。
【注意】循环队列相关操作
设队列为Q，循环队列中入队出队需借助取余运算，具体如下：
初始状态：Q.front=Q.rear=0;
队首指针进1：Q.front=(Q.front+1)%MAXSIZE;
队尾指针进1：Q.rear=(Q.rear+1)%MAXSIZE;
队列长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE;
队满条件：(Q.rear+1)%MAXSIZE==Q.front;
队空条件：Q.front==Q.rear;
（2）队列的链式存储结构
用链表表示的队列简称为链队列，如图3-4所示。一个链队列有两个分别指示队头和队尾的指针（分别称为头指针和尾指针）。
图3-4 链队列示意图
【注意】为了操作方便，通常给链队列添加一个头结点，并令头指针指向头结点。链队列判空条件为头指针和尾指针均指向头结点。
五、离散事件模拟