CH3栈与队列.ppt

栈（stack）是一种很重要的特殊线性结构。 栈是限定在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底。不含元素的栈称为空栈。 栈的特点是后进先出（LIFO）。 栈的基本操作除了在栈顶实现进栈和出栈外，还有初始化栈、判空及取栈顶元素等。 大数是指超过计算机内能表示的最大整数上限的数，无法用整型数表示大数。就用字符型表示大数，读数的次序为高位到地位，但相加的次序为地位到高位，因此，用栈可以实现两个大数的相加。 对于两个大数的加法，其操作步骤归纳如下： 将两个加数的相应位从高位到底位分别加入到两个栈sA和sB中； 若两个加数栈都非空，则一次从栈中弹出栈顶数字相加，和存入变量partialSum中，结果个位数压入栈sum中，进位与下一个数相加； 若某个加数栈为空，则将非空加数栈中数字一次弹出与进位相加，和的个数压入栈sum中，直到该栈为空。若最高位有进位，则最后将进位压入栈sum中； 若两个加数栈均为空，则栈sum中保存的就是最终计算结果。栈sum保存的结果是从高位到低位。 在中缀表达式转化为后缀表达式从左往右的扫描过程中，由优先级低到高依次得到表达式中每个运算符（同优先级的运算符先读到的优先）；而最终得到的后缀表达式过程中，要由优先级高到低依次输出每个运算符，所以此问题适合用栈来解决。 在表达式转化过程中，操作数的相对顺序是不变的，只有运算符的位置在发生变化。因此，在从左至右扫描中缀表达式时，操作数按其原有次序依次输出到后缀表达式中。 由中缀表达式转化为后缀表达式的过程中，可以得出在后缀表达式中的运算符已经按照优先关系从高到低顺序排列，而且对于每个运算符而言，它需要的操作数已在之前最近位置顺序排列完毕。因此，在求解后缀表达式值时，读取到的操作数时依次进栈；一旦遇到运算符，则最靠近它的操作数就在栈顶，对栈顶两个操作数进行运算后，结果进栈；一次类推，便可以求得表达式最终的值。 具体的转化步骤如下所示： 初始化一个运算符栈； 从算术表达式输入的字符串中从左到右读取一个字符； 若当前字符是操作数，则直接送往后缀式； 若当前字符为左括号，将其压入运算符栈； 若当前字符为运算符时，则： 当运算符栈空，则直接压入栈； 当运算符优先级高于栈顶运算符，则将此运算符压入栈；否则，弹出栈顶运算符送往后缀式，并将当前运算符压入栈，重复5； 若当前字符为右括号，反复将栈顶符号弹出，送往后缀式，直到遇到左括号为止，并将左括号弹出舍去； 若读取未结束，转到2； 读取完毕，则将栈中剩余的所有运算符弹出送往后缀式。 递归(recurve) 在程序设计语言中用来定义句法，在数据结构中用来解决表或树形结构的有哪些信誉好的足球投注网站和排序等问题。 在数学及程序设计方法学中的递归定义为：若一个对象部分地包含自己，或用自己给自己定义，则称这个对象上递归的；且若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。 常用到递归方法的情况有： 定义是递归的 数据结构是递归的 问题的解法是递归的 求解过程： 创建一个顺序表L，用于存放素数环的元素；创建一个链式队列，用于存放还未加入到素数环中的自然数。 初始化L，将1加入到L中；将2~n全部加入到Q中。 将Q首元素p与L的最后一个元素相加。如果，两数之和是素数，且p不是队尾元素，则将p追加到L中；否则，p在此入队列等待。 如果p是队尾元素，还需要判断它与L中第一个元素之和是否素数，如果是，则求解结束；否则转至3，直到队列为空，或已对队列中每一个元素都遍历了一次且未能加到素数环为止。 栈与队列的相同点： 都是线性结构，数据元素之间具有“一对一”的逻辑关系。 插入操作都是限制在表尾进行。 都可在顺序存储结构和链式存储结构上实现。 在时间代价上，插入与删除操作都需要常数时间；在时间代价上，情况也相同。 多链栈和多链队列的管理模式可以相同。 栈与队列的不同点： 删除数据元素的位置不同。栈在栈顶，队列在表头。 应用场合不同。符合先进后出的特点的应用使用栈，符合先进先出的特点的应用使用队列。 顺序栈可以实现多栈空间共享，而队列则不同。 作为临时存储空间操作不同。用栈做临时存储结构，存取在栈顶进行；而队列存在队头，取在队尾进行。 栈和队列都是特殊的线性表： 栈是插入和删除操作限制在表尾（栈顶）进行； 栈的特点是先进后出； 队列是插入限定在表尾（队尾）进行，删除限定在表头（队头）进行； 队列的特点是先进先出。 栈和队列的基本操作： 包括进/出栈或队列、取栈或队列首数据元素； 这些操作的时间复杂度都是O（1）。 栈和队列都可用顺序和链式两种存储方法存储： 顺序栈和顺序队列中元素的遍历是靠指示器top、rear或front的移动；而链式栈和链式队列中元素的遍历是靠指针的链接； 顺序栈比链栈使用广泛，