第一章第一章 栈栈 栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。 一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。1、进栈（、进栈（PUSH）算法）算法若若TOP时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作不满则作）；）；TOP+（栈指针加，指向进栈地址）；（栈指针加，指向进栈地址）；STOP=X，结束（，结束（X为新进栈的元素）；为新进栈的元素）；2、退栈（、退栈（POP）算法）算法若若TOP0，则给出下溢信息，作出错处理，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，退栈前先检查是否已为空栈， 空则下溢；空则下溢；不空则作不空则作)；X=STOP，（退栈后的元素赋给，（退栈后的元素赋给X）；）；TOP-，结束（栈指针减，指向栈顶）。，结束（栈指针减，指向栈顶）。进栈、出栈的进栈、出栈的c+实现过程程序：实现过程程序：#define n 100void push(int s,int *top,int *x) /入栈入栈 if (*top=n) printf(overflow); else (*top)+; s*top=*x; void pop(int s,int *y,int *top) /出栈出栈 if (*top=0) printf(underflow); else *y=s*top; (*top)-; 对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。 堆栈的数组模拟 十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：N=(N / d)dN % d （其中 / 为整除运算，%为求余运算）。 例如：(1348)10(2504)8运算过程如下：NN / 8N % 89413NN / 8N % 81348168416821021252021、填空：(9413)10=( )8=( )16=( )22、数制转化程序#include#includeusing namespace std;#define size 100int asize+1,n,d,i=0,j;main() coutn; coutd; do a+i=n%d; n=n/d; while(n!=0); for (j=i;j=1;j-)coutaj; return 0;3、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。 如果进站的车厢序列为123，则可能的出站车厢序列是什么？ 如果进站的车厢序列为123456，问能否得到135426和435612的出站序列。【例【例1】括号的匹配（表达式的合法性检查）】括号的匹配（表达式的合法性检查）【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。【算法分析】 假设输入的字符串存储在c中（char c256 ）。 我们可以定义一个栈：char smaxn+1; int top; 用它来存放表达式中从左往右的左圆括号（maxn=20）。 算法的思路为：顺序（从左往右）扫描表达式的每个字符ci，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。 #include#includeusing namespace std;#define maxn 20char c256;bool judge(char c256) int top=0,i=0; while (ci!=) if (ci=() top+; if (ci=) if (top0) top-; else return 0; i+; if (top!=0) return 0; /检测栈是否为空。不空则说明有未匹配的括号检测栈是否为空。不空则说明有未匹配的括号 else return 1;main() scanf(%s,c); if (judge(c)printf(YES); else printf(NO); return 0;【例【例2】编程求一个后缀表达式的值】编程求一个后缀表达式的值【问题描述】 从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以作为结束标志。【算法分析】 后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。 比如，169*(4+3)转换成后缀表达式为： 16943+*，在字符数组A中的形式为：栈中的变化情况：运行结果：-47#include#include#include#includeusing namespace std;int stack101;char s256;int comp(char s256) int i=0,top=0,x,y; while (i=strlen(s)-2) switch (si) case +:stack-top+=stacktop+1; break; case -:stack-top-=stacktop+1; break; case *:stack-top*=stacktop+1; break; case /:stack-top/=stacktop+1; break; default:x=0; while (si!= ) x=x*10+si+-0; stack+top=x; break; i+; /while return stacktop;main() printf(input a string(_over):); gets(s); printf(result=%d,comp(s); return 0;【例【例3】车厢调度】车厢调度【问题描述【问题描述】 有一个火车站，铁路如图所示，有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n=1000），分别按照顺序编号为1，2，3，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。 负责车厢调度的工作人员需要知道能否使它以a1,a2,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。【输入【输入】 输入文件的第一行为一个整数n，其中n=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。【输出【输出】 如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。【输入样例【输入样例】 5 5 4 3 2 1【输出样例【输出样例】 YES分析：分析： 该题就是前面思考题的一部分。车站C相当于一个栈。我们用模拟法来做，假设我们已经处理了前i-1节从B方向驶出的车厢，我们现在要让ai驶出。若ai不在车站C中，我们就让若干车厢从A方向驶入车站C，直到ai驶入，再将它从B方向驶出；若ai在车站C中，如果它是车站C中停在最前面的，则将它从B方向驶出，否则原问题无解。 如样例中，出栈序列是3 5 4 2 1，模拟过程如下： 一开始栈为空 由于3不在栈中，就需要把1,2,3依次进栈，再出栈，这样符合出栈序列第一个数是3，当前栈为1,2 第2个出栈的是5,5不在栈中，则就把4,5压栈，再出栈就可以得到5，此时栈为1,2，4 第3个出栈的是4，正好是栈顶元素，直接出栈，栈变为1,2 第4个出栈的是2，正好是栈顶元素，直接出栈，栈变为2 第5个出栈的是1，正好是栈顶元素，直接出栈，栈变为在模拟过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况，所以该方案可行。【参考程序【参考程序】#include #include #include using namespace std;const int N = 1010;int stackN,aN; int top,n;int main() cin n; for (int i = 1;i ai; top = 0; for (int i = 1,cur = 1;i = n;+ i) /cur为当前要从为当前要从A方向驶入的车厢号方向驶入的车厢号 while (cur = ai) stack+ top = cur +; if (stacktop = ai) - top; else cout NO endl; return 0; cout YES endl; return 0;1、表达式括号匹配、表达式括号匹配(stack.cpp)【问题描述【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。【输入文件】 输入文件stack.in包括一行数据，即表达式，【输出文件】 输出文件stack.out包括一行，即“YES” 或“NO”。【样例输入1】2*(x+y)/(1-x)【样例输出1】 YES【样例输入2】 (25+x)*(a*(a+b+b)【样例输出2】 NO【上机练习】2、括弧匹配检验、括弧匹配检验(check.cpp)【问题描述【问题描述】 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。输入一个字符串：（），输出：OK【输入格式【输入格式】 输入仅一行字符（字符个数小于255）【输出格式【输出格式】 匹配就输出 “OK” ，不匹配就输出“Wrong”。 【输入样例【输入样例】check.in（）【输出样例【输出样例】check.outWrong3、字符串匹配问题字符串匹配问题【问题描述】 字符串中只含有括号 (),判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是,(),，例如。输入: () 输出:YES，而输入()， ()都应该输出NO。【输入格式】strs.in 文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。【输出格式】strs.out 在输出文件中有N行，每行都是YES或NO。【输入样例】5()()()()()()()()()()()()【输出标例】YESYESYESYESNO4、计算(calc.cpp)【问题描述】小明在你的帮助下，破密了Ferrari设的密码