Chapter 03 Stack & Queue 第三章 栈和队列 Prof. Qing Wang

本章学习的线索 主要线索 重点 难点 栈和队列的顺序存储表示 栈和队列的应用 栈和递归的关系 栈和队列的应用 栈和递归 栈和队列 ADT 栈和队列顺序表示及实现 栈和队列链式表示及实现 Prof. Q. Wang

Content Stack and its ADT Representation & Implementation of Stack Application of Stack Recursion and Stack Queue and its ADT Representation & Implementation of Queue Application of Queue Conclusion Prof. Q. Wang

Chapter 03 Stack & Queue 栈和队列也是线性表，只不过是操作受限的线性表。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。广泛应用于各种软件系统中。 Prof. Q. Wang

3.1 Stack and its ADT Definition A stack is a kind of special linear list. A stack is a data structure in which all insertions and removals of entries are made at one end, called the top of the stack. LIFO structure: The last entry which was inserted is the first one that will be removed. (LIFO: Last In First Out) Prof. Q. Wang

Top & Bottom Top Bottom Insertion The specific end of linear list at which element is inserted and removed. Bottom Another end of the stack. Fixed Insertion (Push) Removal (Pop) Prof. Q. Wang

Examples of Push and Pop Prof. Q. Wang

Prof. Q. Wang

3.1.2 Basic operations of Stack 1. Initialization； 2. Is a empty stack； 3. Push an element into the stack (Element insertion)； 4. Pop an element from the stack (Element removal)； 5. Get the value of the top element。 Prof. Q. Wang

Stack ADT ai, i=0,1,2,…. < ai , ai+1 > Create IsEmpty Push Pop getTop ai, i=0,1,2,…. < ai , ai+1 > Prof. Q. Wang

3.2 Implementation of Stack 1) Sequential form typedef int ElemType; /* 定义栈元素的数据类型， 这里定义为整型 */ #define MAXNUM 100 /* 栈中能达到的最大容量， 这里设为100 */ typedef struct SeqStack /* 顺序栈类型定义 */ { ElemType s[MAXNUM]; int top; /* 栈顶指针 */ }SeqStack, *PSeqStack; top s -1 Prof. Q. Wang [MAXNUM-1]

Sequential Stack top -1 Discussions s Create IsEmpty Push Pop GetTop [MAXNUM-1] Create IsEmpty Push Pop GetTop Discussions Prof. Q. Wang

Algorithm 3.1 Initialization 对比分析 PSeqStack createEmptyStack_seq( void ) { PSeqStack pastack; pastack = (PSeqStack)malloc(sizeof(SeqStack)); if (pastack==NULL) printf("Out space!! \n"); else pastack->top=-1; return pastack; } Prof. Q. Wang

Algorithm 3.2 Judge a stack is empty or not int isEmptyStack_seq ( PSeqStack pastack ) { return ( pastack->top == -1 ); } Prof. Q. Wang

Algorithm 3.3 Push an element into the stack void push_seq ( PSeqStack pastack, DataType x ) /* 在栈中压入一元素x */ { if ( pastack->top >= MAXNUM - 1 ) printf( "overflow! \n" ); else pastack->top = pastack->top + 1; pastack->s[pastack->top] = x; } Prof. Q. Wang

Algorithm 3.4 Pop the top element from the stack ElemType pop_seq( PSeqStack pastack ) /* 删除栈顶元素 */ { ElemType temp; if ( isEmptyStack_seq( pastack ) ) printf( "Underflow!\n" ); else temp = pastack.s[pastack->top]; pastack->top = pastack->top - 1; } return temp; Prof. Q. Wang

Algorithm 3.5 Get the value of the top element ElemType top_seq( PSeqStack pastack ) /* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ { if (isEmptyStack_seq(pastack)) Error(“Empty Stack!”); else return pastack->s[pastack->top]; } Prof. Q. Wang

Quiz How to arrange the carriages? ……………… 1 2 3 n-1 n 1 2 3 … n 1 3 2 Solution ……………… Demo Prof. Q. Wang

2) Linked list form typedef int DataType ; /* 定义栈中元素类型为整型， 也可定义为其他类型 */ struct Node /* 单链表结点结构 */ { DataType info; struct Node *link; }; struct LinkStack /* 链接栈类型定义 */ struct Node *top; /* 指向栈顶结点 */ }LinkStack, *PLinkStack; Prof. Q. Wang

Example Prof. Q. Wang

Linked stack Create IsEmpty Push Pop GetTop Applications Prof. Q. Wang

Algorithm 3.6 Initialization 对比分析 Algorithm 3.6 Initialization PLinkStack createEmptyStack_link( ) { PLinkStack plstack; plstack = (struct LinkStack *)malloc( sizeof(struct LinkStack)); if (plstack != NULL) plstack->top = NULL; else printf("Out of space! \n"); return plstack; } Prof. Q. Wang

Algorithm 3.7 Judge a linked stack is empty or not int isEmptyStack_link( PLinkStack plstack ) { return (plstack->top == NULL); } Prof. Q. Wang

Algorithm 3.8 Push an element into the linked stack void push_link( PLinkStack plstack, DataType x ) /* 在栈中压入一元素x */ { struct Node * p; p = (struct Node *)malloc( sizeof( struct Node ) ); if ( p == NULL ) printf("Out of space!\n"); else p->info = x; p->link = plstack->top; plstack->top = p; } Prof. Q. Wang

Algorithm 3.9 Pop the top element from the linked stack DataType pop_link( PLinkStack plstack ) /* 在栈中删除栈顶元素 */ { struct Node * p; DataType elem; if ( isEmptyStack_link( plstack ) ) printf( "Empty stack pop.\n" ); else p = plstack->top; elem = p->info; plstack->top = plstack->top->link; free(p); } return elem; Prof. Q. Wang

Algorithm 3.10 Get the value of the top element DataType top_link( PLinkStack plstack ) /* 对非空栈求栈顶元素 */ { if (isEmptyStack_link(plstack)) Error(“Empty Stack!”); else return plstack->top->info; } Prof. Q. Wang

3.3 Applications of Stack Bracket matching (括号匹配) Infix expression calculator (中缀表达式计算器) Reverse Poland calculator (逆波兰计算器) Conversion of the arithmetic expression (表达式转换) Impl. Impl. Impl. Impl. Prof. Q. Wang

Application 1: Bracket Matching Requirement Develop a program to check that brackets are correctly matched in an input text file. The brackets are limited in {, }, (, ), [, and ]. Methods Read a single line of characters and ignore all input other than bracket characters. Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends. Prof. Q. Wang

[ ( [ ] [ ( ) ] ) ] 例如，考虑下列括弧序列： 可见，括弧匹配也遵循“后进先出”的规律。 如何表示下列“不匹配” 的情况？ 到来的右括弧不是所“期待”的， 即来了一个“不速之客”，直到结束，也没有等到“期待”的匹配; Prof. Q. Wang

算法核心步骤 算法的设计思想： 凡出现左括弧，则进栈； 凡出现右括弧，首先检查栈是否空？ 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配 表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余。 Prof. Q. Wang

Bracket Matching Program int main() { LinkStack openings; char symbol; bool is_matched = true;   while (is_matched && (symbol = cin.get()) != '\n') { if (symbol == '{' || symbol == '(' || symbol == '[') openings.push(symbol); if (symbol == '}' || symbol == ')' || symbol == ']') { if (openings.empty()) { cout << "Unmatched closing bracket " << symbol << " detected." << endl; is_matched = false; } Prof. Q. Wang

match=openings.top(); openings.pop(); else { char match; match=openings.top(); openings.pop(); is_matched = (symbol == '}' && match == '{') || (symbol == ')' && match == '(') || (symbol == ']' && match == '['); if (!is_matched) cout << "Bad match " << match << symbol << endl; } if (!openings.empty()) cout << "Unmatched opening bracket(s) detected." << endl; Demo Prof. Q. Wang

Application 2: Infix expression calculator 限于二元运算符的表达式定义: 表达式 ::= (操作数) + (算符) + (操作数) 操作数 ::=常量 | 变量 | 常数 算符 ::= 运算符(分为算术运算符、关系运算符和逻辑运算符) | 界限符(左右括号和表达式结束符等) Exp = S1 + OP + S2 前缀表示法OP + S1 + S2 中缀表示法 S1 + OP + S2 后缀表示法 S1 + S2 + OP Prof. Q. Wang

表达式表示方法 例如: Exp = a * b + (c  d / e) * f 前缀式: + * a b *  c / d e f - c a / d e + * f Prof. Q. Wang

中缀表达式求值的算法 采用“算符优先法”，在表达式中，优先级的顺序是: 括号的优先级最高，对括号内的各种运算符有:先乘除、再加减，同级运算从左至右。 先括号内，后括号外，多层括号，由内向外。 在算符集中，在每一个运算步，相邻的算符c1 和c2之间的关系是如下三种情况（c1出现在c2之前）： c1<c2, c1的优先级低于c2 c1=c2, c1的优先级等于c2 c1>c2, c1的优先级大于c2 Prof. Q. Wang

算符间优先级 + - * / ( ) # + - * / ( ) # > > < < < > > c2 + - * / ( ) # + - * / ( ) # > > < < < > > > > > > < > > < < < < < = > > > > > > < < < < < = c1 Prof. Q. Wang

说明： 1. 计算表达式3-(6/2)4，‘#’是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个 ‘#’构成整个表达式的一对括号。表中的‘ (’=‘)’表示当左右括号相遇时，括号内的运算已经完成。同理，‘#’=‘#’表示整个表达式求值完毕。 2. ‘)’与‘(’、‘#’与‘)’以及‘(’ 与‘#’之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们暂假定所输入的表达式不会出现语法错误。 Prof. Q. Wang

算法核心步骤 为实现算符优先算法，在这里用了两个工作栈。一个存放算符OPTR，另一个存放数据OPND。算法思想是： 首先置数据栈为空栈，表达式起始符“＃”为算符栈的栈底元素 自左向右扫描表达式，读到操作数进OPND栈，读到运算符，则和OPTR栈顶元素比较（栈顶元素为c1，读到的算符为c2) 若c1<c2，则c2进栈继续扫描后面表达式； 若c1＝c2，则（“＝”），即括号内运算结束，将c1出栈，并且c2放弃，继续扫描后面表达式； 若c1>c2，则将c1出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND。 重复直到表达式求值完毕。 Prof. Q. Wang

+ ( 2 1 3 + 18 4 6 - # 23 19 5 表达式求值示意图：5+6(1+2)-4 读入表达式过程： 5 + 6 ( 1 × ( 1 + 2 ) - 4 # = 19 top base OPTR栈 OPND栈 top base 1+2=3 6×3=18 top 5+18=23 top top top 23-4=19 + top top top top top ( 2 top top top top top top top top 1 3 × top top top top top top top top top + 18 4 6 - top top top top # 23 19 5 Prof. Q. Wang

算法: 求中缀表达式值 OperandType EvaluateExpression() { InitStack(OPTR); Push(OPTR, ‘#’); InitStack(OPND); c=getchar(); while (c!= ‘#’ || GetTop(OPTR)!= ‘#’) { if(!In (c, OP)){Push((OPND, c); c=getchar();} else switch (Precede(GetTop(OPTR), c)) { case ‘<’ : //栈顶元素优先权低 Push(OPTR, c)； c=getchar()；break； case ‘=’ : //脱括号并接收下一字符 Pop(OPTR, x)； c=getchar()；break； case ‘>’ : //退栈并将运算结果入栈 Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; } return GetTop(OPND); Prof. Q. Wang

Application 3: Reverse Polish calculator Expression Infix: a+b*(c-d)-e/f Postfix (Reverse Polish Notation): abcd-*+ef/- Prefix (Polish Notation): -+a*b-cd/ef Operands: a, b, c, d, e, f Operators: +, -, *, /, Delimiter: (, ) Demo Prof. Q. Wang

Expression Evaluation How to calculate the value of the expression? a+b*(c-d)-e/f abcd-*+ef/- -+a*b-cd/ef Infix expression Prefix expression Postfix expression Prof. Q. Wang Skip

后缀表达式求值 例如： a b  c d e /  f  + c-d/e 先找运算符，再找操作数 ab d/e (c-d/e)f Prof. Q. Wang

a+b*(c-d)-e/f abcd-*+ef/- 利用后缀表达式求值时，从左向右顺序地扫描表达式，并使用一个栈暂存扫描到的操作数或计算结果，例如， a+b*(c-d)-e/f abcd-*+ef/- 中缀表达式计算表达式的值 后缀表达式计算表达式的值 在后缀表达式的计算顺序中已经隐含了加括号的优先次序，因而括号在后缀表达式中不出现。 Prof. Q. Wang

算法: 求后缀表达式值 Elemtype EvaluateExpression_postfix( ) { initStack(OPND); c=getchar( )； while(c != ‘#’ ) if (!In(c, OP)) { Push((OPND, c)；c=getchar( )；} else //退栈并将运算结果入栈 Pop(OPND, b) ; Pop(OPND, a)； Push(OPND, Operate(a, theta, b))；c=getchar( ); } return GetTop(OPND)； Skip Prof. Q. Wang

Reverse Polish calculator // The program has executed simple arithmetic commands entered by the // user. // Uses: The class Stack and the functions introduction, instructions, // do_command, and get_command. typedef double Stack_entry; int main() { Stack stored_numbers; introduction(); instructions(); while (do_command(get_command(), stored_numbers)); } Prof. Q. Wang

Obtaining command The auxiliary function get_command obtains a command from the user, checking that it is valid and converting it to lower case by using the string function tolower() that is declared in the standard header file cctype. Prof. Q. Wang

cout << "Select command and press <Enter>:"; char get_command() { char command; bool waiting = true; cout << "Select command and press <Enter>:";   while (waiting) { cin >> command; command = tolower(command); if (command == '?' || command == '=' || command == '+' || command == '-' || command == '*' || command == '/' || command == 'q' ) waiting = false; else { cout << "Please enter a valid command:" << endl << "[?]push to stack [=]print top" << endl << "[+] [-] [*] [/] are arithmetic operations" << endl << "[Q]uit." << endl; } return command; Prof. Q. Wang

bool do_command(char command, Stack &numbers) // Pre: The first parameter specifies a valid calculator command. // Post: The command specified by the first parameter has been applied // to the Stack of numbers given by the second parameter. // A result of true is returned unless command == 'q'. // Uses: The class Stack. { double p, q; switch (command) { case '?': cout << "Enter a real number: " << flush; cin >> p; if (numbers.push(p) == overflow) cout << "Warning: Stack full, lost number" << endl; break; Prof. Q. Wang

if (numbers.top(q) == underflow) case ‘+': if (numbers.top(q) == underflow) cout << "Stack empty" << endl; else { numbers.pop(); if (numbers.top(p) == underflow) { cout << "Stack has just one entry" << endl; numbers.push(q); } if (numbers.push( p+q ) == overflow) cout << "Warning: Stack full, lost result" << endl; break;  Prof. Q. Wang

if (numbers.top(q) == underflow) case '-': if (numbers.top(q) == underflow) cout << "Stack empty" << endl; else { numbers.pop(); if (numbers.top(p) == underflow) { cout << "Stack has just one entry" << endl; numbers.push(q); } if (numbers.push( p-q ) == overflow) cout << "Warning: Stack full, lost result" << endl; break;  Prof. Q. Wang

if (numbers.top(q) == underflow) case ‘*': if (numbers.top(q) == underflow) cout << "Stack empty" << endl; else { numbers.pop(); if (numbers.top(p) == underflow) { cout << "Stack has just one entry" << endl; numbers.push(q); } if (numbers.push( p*q ) == overflow) cout << "Warning: Stack full, lost result" << endl; break;  Prof. Q. Wang

if (numbers.top(q) == underflow) case ‘/': if (numbers.top(q) == underflow) cout << "Stack empty" << endl; else { numbers.pop(); if (numbers.top(p) == underflow) { cout << "Stack has just one entry" << endl; numbers.push(q); } if (numbers.push( p/q ) == overflow) cout << "Warning: Stack full, lost result" << endl; break;  Prof. Q. Wang

cout << "Calculation finished.\n"; return false; } return true; case 'q': cout << "Calculation finished.\n"; return false; } return true; Prof. Q. Wang

Application 4: Infix Expression to Postfix Infix: a+b*(c-d)-e/f Postfix (Reverse Polish Notation): abcd-*+ef/- Components Operands: a, b, c, d, e, f Operators: +, -, *, /, Delimiter: (, ), # Prof. Q. Wang

#a+b*(c-d)-e/f# abcd-*+ef/- A specific stack OPTR is used to store temporary operators, such as +, *, and ( in above expression. isp (in stack priority): the priority of operator at the top of OPTR stack. icp (incoming priority): the new incoming operator priority. If isp < icp, push the incoming operator into OPTR If isp > icp, output and pop the top of OPTR If isp = icp, scan next item and pop the top of OPTR Prof. Q. Wang

Priority of operators + - * / ( ) # > < = -- isp -- icp Prof. Q. Wang

a  ( b  ( c + d / e ) - f ) # a b c d e / +  f -  # / / + + (   Prof. Q. Wang

Infix expression: a+b*(c-d)-e/f Step Items Type Activity Optr Stack Output # 1 a operand 2 + operator isp(#) < icp(+) #+ 3 b ab 4 * isp(+) < icp(*) #+* 5 ( isp(*) < icp(() #+*( 6 c abc 7 - isp(() < icp(-) #+*(- 8 d abcd 9 ) isp(-) > icp()) abcd- == Prof. Q. Wang

#a+b*(c-d)-e/f # abcd-*+ef/- 10 - operator isp(*) > icp(-) #+ abcd-* isp(+) > icp(-) # abcd-*+ isp(#) < icp(-) #- 11 e operand abcd-*+e 12 / isp(-) < icp(/) #-/ 13 f abcd-*+ef 14 isp(/) > icp(#) abcd-*+ef/ isp(-) > icp(#) abcd-*+ef/- ==, end #a+b*(c-d)-e/f # abcd-*+ef/- Prof. Q. Wang

Program void postfix (expression e) { Stack <char> OPTR; char ch, y; OPTR.clear(); OPTR.push(‘#’); while (cin.get(ch)){ if (isdigit(ch)) cout <<ch; else { y=OPTR.top(); switch(y, ch) { case <: OPTR.push(ch); break; case >: cout << y; OPTR.pop(); break; case =: OPTR.pop(); } Prof. Q. Wang

3.4 Recursion and Stack 1. 递归的概念及递归调用过程 用自身的简单情况来定义自己的方式，称为递归定义。 一个直接调用自己或者通过一系列的调用语句间接地调 用自己的函数，称为递归函数。 Factorial 阶乘 int fact (int n) { if (n == 0) return 1; else return (n*fact(n-1)); } Prof. Q. Wang

Fibonacci array(斐波纳契)数列 int fib(int n) { if (n == 0 || n==1) return n; else return fib(n-1)+fib(n-2); } Prof. Q. Wang

2. Recursive data structure (1) //Declaration typedef struct Node { DataType data; struct Node *link; }Node, *PNode; 2. Recursive data structure (1) Linked list //Traverse linked list and print out the last node void Find_Last ( PNode p ) { if ( p -> link == NULL ) printf(p -> data); else Find_Last ( p -> link ); } Prof. Q. Wang

2. Recursive data structure (2) //Declaration typedef struct BinTreeNode { DataType data; struct BinTreeNode *lchild; struct BinTreeNode *rchild; }BinTreeNode, *PBinTreeNode, BinTree, *PBinTree; Binary tree - + / * a b c d e f bt //InOrder Traverse binary tree and print out all nodes void InOrderTraverse (PBinTree BT) { if (T) { InOrderTraverse (BT->lchild); printf(BT->data); InOrderTraverse (BT->rchild); } Prof. Q. Wang

3. Baggage Loading (背包问题) 一个背包可以放入的物品重量T，现有n件物品，重量分别为w1,w2,…,wn，问能否从这些物品中选若干件放入背包中，使得放入的重量之和正好是T。 (1) 分析问题，得到数学模型 1 t = 0 0 t < 0 0 t > 0, n < 1 knap(t, n-1) 或 knap(t-wn, n-1) 当t>0, n>=1 Knap(t,n) = (2) 设计算法：递归算法 Demo (3) 程序设计： Prof. Q. Wang

else if (t<0 || t>0 && n<1) return 0; 背包问题的递归算法 int knap (int t, int n) { if ( t==0) return 1; else if (t<0 || t>0 && n<1) return 0; else if (knap(t-w[n-1], n-1) == 1) printf (“result:n=%d,w[%d]=%d\n”, n, n-1, w[n-1]); } else return (knap(t, n-1)); Prof. Q. Wang

Procedure of function calling Before calling (调用前)： (1) Pass the parameters and return address to the sub-function (将所有的实参、返回地址传递给被调用函数保存) (2) Allocate memory for local variables (为被调用函数的局部变量分配存储区) (3) Jump to the entrance of the sub-function (将控制转移到被调用函数入口) After calling (调用后)： (1) Save the results (保存被调用函数的计算结果) (2) Release the allocated memory in sub-function (释放被调用函数的数据区) (3) Return to upper level function via return address (依照被调用函数保存的返回地址将控制转移到调用函数) Prof. Q. Wang

规则: 多个函数嵌套调用时，按照“后调用先返回”的原则进行。Last calling, first return 规则: 多个函数嵌套调用时，按照“后调用先返回”的原则进行。Last calling, first return. Just like last in, first out. int main() { int m,n; ... first(m,n); 1: … } int first(int s, int t) { int i; … second(i); 2: … ... } int second(int d) { int x,y; 3: … ... } …… . m n 1 i 2 X y …… . m n 1 i Prof. Q. Wang

Example of function calling int main() { int m,n; ... int i; … int x,y; 3: … } 2: … 1: … second first main Prof. Q. Wang

Example void main() { … call A(…); call D(…); return; } function A(…) call B(…); call C(…); return; } function B(…) { … return; } function C(…) { … call D(case1); return; } function D(…) { … call D(…); return; } Prof. Q. Wang

Tree of subprogram calls Prof. Q. Wang

Hanoi tower Description X Y Z 3 2 1 Description 假设有3个分别命名为X，Y，Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,…,n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并且仍按同样顺序叠放，圆盘移动时必须遵循下列规则： 每次只能移动一个圆盘； 圆盘可以插在X,Y,Z的任一塔座上； 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 Prof. Q. Wang

Divide & Conquer Step1 Step2 Step3 Demo X Y Z X Y Z X Y Z X Y Z 3 2 1 Prof. Q. Wang

Recursive solution of Hanoi tower Line void Hanoi (int n, char x, char y, char z) 1 { 2 if (n = = 1) 3 move(x, 1, z); 4 else { 5 Hanoi (n-1, x, z, y); 6 move (x, n, z); 7 Hanoi (n-1, y, x, z); 8 } 9 } void move (char x, int n, char y) { printf(“Move disk %d from %c to %c”, n, x, y); } Hanoi (3, a, b, c) Prof. Q. Wang

State of recursive stack Level Execute lines State of recursive stack （Address, 盘号, x, y, z） 塔与圆盘的状态 0,3,a,b,c 汉诺塔问题的递归调用过程 1 1，2，4，5 a b c 6,2,a,c,b 0,3,a,b,c 3 2 1 2 1，2，4，5 6,1,a,b,c 6,2,a,c,b 0,3,a,b,c a b c 3 1，2，3，9 3 2 1 6,2,a,c,b 0,3,a,b,c a b c 2 6，7 Prof. Q. Wang 3 2 1

State of recursive stack Level Execute lines State of recursive stack （Address, 盘号, x, y, z） 塔与圆盘的状态 8,1,c,a,b 6,2,a,c,b 0,3,a,b,c 汉诺塔问题的递归调用过程 3 1，2，3，9 a b c 6,2,a,c,b 0,3,a,b,c 2 1 3 2 8，9 0,3,a,b,c 1 6，7 a b c 8,2,b,a,c 0,3,a,b,c 2 1 3 2 1，2，4，5 Prof. Q. Wang

State of recursive stack Level Execute lines State of recursive stack （Address, 盘号, x, y, z） 塔与圆盘的状态 6,1,b,c,a 8,2,b,a,c 0,3,a,b,c a b c 3 1，2，3，9 1 2 3 8,2,b,a,c 0,3,a,b,c a b c 2 6，7 3 2 1 8,1,a,b,c 6,2,b,a,c 0,3,a,b,c a b c 3 1，2，3，9 3 2 1 8,2,b,a,c 0,3,a,b,c a b c 2 8，9 Prof. Q. Wang 3 2 1

State of recursive stack （Address, 盘号, x, y, z） Level Execute lines 塔与圆盘的状态 0,3,a,b,c 8，9 1 a b c 3 2 1 栈空，结束 问题： 1. Hanoi塔求解中，move语句执行多少次？ 2. 递归树的概念。 Prof. Q. Wang

Recursive calling a b c a b c a b c a b c a b c a b c a b c a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 a b c 3 2 1 Hanoi (3, a, b, c) move(a,3,c) move(a,2,b) move(b,2,c) move(a,1,c) move(c,1,b) move(b,1,a) move(a,1,c) Prof. Q. Wang

Supplementary Materials Maze Eight Queen Puzzle Prof. Q. Wang

2. 递归函数到非递归函数的转换 Algorithm 3.11 Recursive program of factorial int fact( int n ) { if ( n == 0 ) return 1; else return ( n * fact( n – 1 ) ); } Prof. Q. Wang

Algorithm 3.12 Non recursive program of factorial int nfact( int n ) { int res; PSeqStack st; /* 使用顺序存储结构实现的栈 */ st = createEmptyStack_seq( ); while (n>0) { push_seq(st, n); n = n – 1; } res = 1; while (! isEmptyStack_seq(st)) { res = res * top_seq(st); pop_seq(st); return ( res ); Prof. Q. Wang

3. 简化的背包问题* 简化的背包问题： 一个背包可以放入的物品重量T，现有n件物品，重量分别为w1,w2,…,wn，问能否从这些物品中选若干件放入背包中，使得放入的重量之和正好是T? (1) 分析问题，得到数学模型 1 t = 0 0 t < 0 0 t > 0 , n < 1 knap(t, n-1) 或 knap(t-wn, n-1) 当t>0,n>=1 Knap(t,n)= Prof. Q. Wang

else if ((t<0) || ((t>0)&&(n<1))) return 0; (2) 设计算法：递归算法 (3) 程序设计： int knap (int t, int n) { if ( t == 0 ) return 1; else if ((t<0) || ((t>0)&&(n<1))) return 0; else if ( knap(t - w[n-1], n - 1) == 1 ) printf("result: n=%d ,w[%d]=%d \n",n,n-1,w[n-1]); } else return ( knap (t, n - 1) ); Prof. Q. Wang

背包问题的非递归求解 首先我们设计一个栈st，栈中的每个结点包含以下四个字段：参数s, n, 返回地址r 和结果单元k。由于knap算法中有两处要递归调用knap算法，所以返回地址一共有三种情况： 第一，计算knap( s0 , n0 )完毕，返回到调用本函数的其它函数； 第二，计算knap( s - w[n-1] , n - 1 )完毕，返回到本调用函数中继续计算； 第三，计算knap( s , n - 1 )完毕，返回到本调用函数继续计算。 为了区分三种不同的返回，r 分别用1，2，3表示，另外引入一个变量x作为进出栈的缓冲。 Prof. Q. Wang

栈用顺序存储结构实现，栈中元素和变量的说明如下： struct NodeBag /* 栈中元素的定义 */ { int s , n ; int r ; /* r的值为1,2,3 */ int k; }; typedef struct NodeBag DataType; PSeqStack st; struct NodeBag x; Prof. Q. Wang

转换的做法按以下规律进行，凡调用语句 knap(s1, n1)均代换成： (1) x.s = s1； x.n = n1 ； x.r = 返回地址编号； (2) push_seq( st, x ); (3) goto 递归入口。 将调用返回统一处理成： (1) x = top_seq( st ); (2) pop_seq( st ); (3) 根据x.r的值，进行相应处理 x.r = 1 , 返回; x.r = 2 , 继续处理1; x.r = 3 , 继续处理2; Prof. Q. Wang

st = createEmptyStack_seq( ); /* entry0: 初始调用入口 */ x.s = s; x.n = n; 并将算法中的所有局部量都改用栈st中栈顶结点的相应字段，为了在算法中直接引入栈，并在书写上一致，算法开头增加将结点( s , n , 1 )推入栈st中的动作 算法3.14 背包问题的非递归算法 int nknap (int s,int n) { struct NodeBag x; PSeqStack st; st = createEmptyStack_seq( ); /* entry0: 初始调用入口 */ x.s = s; x.n = n; x.r = 1; push_seq (st, x); Prof. Q. Wang

{ st->s[st->top].k = TRUE; goto exit2; } entry1: /* 递归调用入口 */ if (top_seq(st).s == 0) { st->s[st->top].k = TRUE; goto exit2; } else if (top_seq(st).s<0 || (top_seq(st).s>0 && top_seq(st).n<1)) { st->s[st->top].k = FALSE; else { x.s = top_seq(st).s - w[top_seq(st).n-1]; x.n = top_seq(st).n - 1; x.r = 2; push_seq(st,x); goto entry1; Prof. Q. Wang

x = top_seq(st); pop_seq(st); switch (x.r) { case 1: return(x.k); exit2: /* 返回处理 */ x = top_seq(st); pop_seq(st); switch (x.r) { case 1: return(x.k); case 2: goto L3; case 3: goto L4; } L3: /* 继续处理1 */ if (x.k == TRUE){ st->s[st->top].k = TRUE; printf("result n=%d , w=%d \n", top_seq(st).n,w[top_seq(st).n-1]); goto exit2; else { x.s = top_seq(st).s; x.n = top_seq(st).n - 1; x.r = 3; push_seq(st,x); goto entry1; Prof. Q. Wang

st->s[st->top].k = x.k; goto exit2; } L4: /* 继续处理2 */ st->s[st->top].k = x.k; goto exit2; } Prof. Q. Wang

4. Maze (a) 迷宫的图形表示 (b) 迷宫的二维数组表示 Prof. Q. Wang

入口 出口 Prof. Q. Wang

为避免走回已经进入过的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号。 求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。 为避免走回已经进入过的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号。 为了记录当前位置以及在该位置上所选的方向，算法中设置了一个栈，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即direction数组的下标值） Prof. Q. Wang

迷宫算法 do { 若当前位置可通， 则{ 将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻块为新的当前位置； } 则{ 将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻块为新的当前位置； } 否则， 若栈不空且栈顶位置尚有其它方向未经搜索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一邻块； 若栈不空且栈顶位置的四周均不可通， 则{ 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； } while (栈不空)； N W E S Prof. Q. Wang

栈用顺序存储结构实现，栈中元素的说明如下： struct NodeMaze { int x,y,d; }; typedef struct NodeMaze DataType; void mazePath (int *maze[],int *direction[],int x1,int y1,int x2,int y2) /* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2] 的一条路径 */ /* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */ 算法3.15 求迷宫中一条路径的算法 Prof. Q. Wang

st = createEmptyStack_seq( ); maze[x1][y1] = 2; /* 从入口开始进入,作标记 */ { int i,j,k,kk; int g,h; PSeqStack st; DataType element; st = createEmptyStack_seq( ); maze[x1][y1] = 2; /* 从入口开始进入,作标记 */ element.x = x1; element.y = y1; element.d = -1; push_seq(st, element); /* 入口点进栈 */ while (! isEmptyStack_seq(st)) /* 走不通时,一步步回退 */ { element = top_seq(st); i = element.x; j = element.y; k = element.d + 1; Prof. Q. Wang

while (k<=3) /* 依次试探每个方向 */ { g = i + direction[k][0]; pop_seq(st); while (k<=3) /* 依次试探每个方向 */ { g = i + direction[k][0]; h = j + direction[k][1]; if (g==x2 && h==y2 && maze[g][h]==0) /* 走到出口点 */ { printf("The path is:\n"); /* 打印路径上的每一点 */ for (kk=1; kk<=st->top; kk++) printf("the %d node is: %d %d \n", kk, st->s[kk].x,st->s[kk].y); printf("the %d node is: %d %d \n", kk, i, j); printf("the %d node is: %d %d \n", kk+1, g, h); return; } Prof. Q. Wang

if (maze[g][h]==0) /* 走到没走过的点 */ { maze[g][h] = 2; /* 作标记 */ element.x = i; element.y = j; element.d = k; push_seq(st,element); /* 进栈 */ i = g; /* 下一点转换成当前点 */ j = h; k = -1; } k = k + 1; printf("The path has not been found.\n"); /* 栈退完,未找到路径 */ 栈结束 Prof. Q. Wang

3.5 Queue and its ADT Definition A queue is a special linear list. A queue is a list in which all addition to the list are made at one end, and all deletions from the list are made at the other end. FIFO structure: The first entry which is added is the first one that will be removed. (FIFO: First In First Out) Prof. Q. Wang

Queue “队列”也是一种特殊的线性表，对于它所有的插入都在表的一端进行，所有的删除都在表的另一端进行。进行删除的这一端叫队列的“头”，进行插入的这一端叫队列的“尾”。当队列中没有任何元素时，称为“空队列”。 a1 a2 a3 … an Into the queue Out the queue front rear Prof. Q. Wang

Example Rear Head Prof. Q. Wang

Basic operations of Queue 1. Initialization； 2. Judge a Queue is empty or not； 3. Insert a element into the Queue； 4. Remove an element from the Queue； 5. Get the value of the front element in the Queue。 Prof. Q. Wang

Queue ADT ai, i=0,1,2,…. < ai , ai+1 > Create IsEmpty enQueue deQueue getFront ai, i=0,1,2,…. < ai , ai+1 > Prof. Q. Wang

3.6 Implementation of Queue Linked form (Linked queue) Sequential form Fixed length sequential queue Variable length sequential queue Prof. Q. Wang

1) Linked queue typedef struct _QNode { DataType info; struct _QNode *link; }Node, *PNode; typedef struct PNode front, rear; }LinkQueue, *PLinkQueue; create IsEmpty enQueue deQueue getFront Seq. Queue Prof. Q. Wang

Algorithm 3.21 Initialization PLinkQueue createEmptyQueue_link( ) { PLinkQueue plqu; plqu = (LinkQueue *)malloc(sizeof(LinkQueue)); if (plqu!=NULL) { plqu->front= plqu->rear = NULL; } else printf("Out space!! \n"); return plqu; Algorithm 3.22 Judge a linked queue empty or not int isEmptyQueue_link( PLinkQueue plqu ) { return (plqu->front == NULL); } Prof. Q. Wang

Algorithm 3.23 Insert an element at the rear of the linked queue void enQueue_link( PLinkQueue plqu, Datatype x ) { PNode p; if ( p == (Node *)malloc( sizeof(Node ) ) ) printf ("out of space!"); else { p->info = x; p->link = NULL; if (plqu->front == NULL) { plqu->front = p; plqu->rear = p; } plqu->rear->link = p; plqu->rear= p; Prof. Q. Wang

Algorithm 3.24 Remove the front element from the linked queue void deQueue_link( PLinkQueue plqu ) { PNode p; if ( plqu->front == NULL ) printf( "Empty queue.\n " ); else { p = plqu->front; plqu->front= plqu->front->link; free(p); } Prof. Q. Wang

Algorithm 3.25 Get the value of the front element of the linked queue Datatype frontQueue_link( PLinkQueue plqu ) { return plqu->front->info; } Prof. Q. Wang

2) Sequential queue (1) Linear queue ７ J6 ６ J5 ５ ４ ３ J3 ２ １ J2 ０ J1 Q.rear ７ J6 Q.front ６ J5 ５ ４ Q.rear ３ J3 ２ １ J2 Q.rear Q.front Q.front ０ J1 Initial state Empty Enqueue Overflow Q.rear=0 Q.front=0 Prof. Q. Wang

Issues of sequential queue Overflow real fake Strategy Circular queue Dynamic queue Linked form Variable length form J1 J2 J3 Q.front Q.rear J4 J5 J6 J7 J8 Q.front Q.rear J5 J6 J7 J8 Prof. Q. Wang

(2) Circular queue J2 J1 J3 Initial state Empty enQueue Q.front Q.rear J2 J1 J3 Q.rear Initial state Empty enQueue Prof. Q. Wang

Fig3 Full, if Q.rear+1 == Q.front J2 J1 J8 J3 J4 J7 Q.front J5 J6 Fig1 Full J1 J2 J7 J6 J5 J4 J3 Fig2 Empty Q.rear Fig3 Full, if Q.rear+1 == Q.front Prof. Q. Wang

#define MAXNUM 100 /* 队列中能达到的最大容量，这 里设为100 */ struct SeqQueue /* 顺序队列类型定义 */ { DataType q[MAXNUM]; int front, rear; }; /* 顺序队列类型的指针类型 */ typedef struct SeqQueue *PSeqQueue; create IsEmpty enQueue deQueue getFront Application Prof. Q. Wang

Algorithm 3.16 Initialization PSeqQueue createEmptyQueue_seq( void ) { PSeqQueue paqu; paqu = (struct SeqQueue *)malloc(sizeof(struct SeqQueue)); if (paqu==NULL) printf ("Out space!! \n"); else { paqu->front = 0; paqu->rear = 0; } return paqu; Prof. Q. Wang

Algorithm 3.17 Is Empty or not int isEmptyQueue_seq( PSeqQueue paqu ) { return (paqu->front == paqu->rear); } Prof. Q. Wang

Algorithm 3.18 Insert an element into the Queue void enQueue_seq( PSeqQueue paqu, DataType x ) /* 在队列尾部插入一元素x */ { if ( (paqu->rear + 1) % MAXNUM == paqu->front ) printf ( "Full queue.\n" ); else { paqu->q[paqu->rear] = x; paqu->rear = (paqu->rear + 1) % MAXNUM; } Prof. Q. Wang

Algorithm 3.19 Remove the front element from the Queue void deQueue_seq( PSeqQueue paqu ) /* 删除队列头部元素 */ { if (isEmptyQueue_seq(paqu)) printf ( "Empty Queue.\n" ); else paqu->front = (paqu->front + 1) % MAXNUM; } Prof. Q. Wang

Algorithm 3.20 Get the value of the front element in the Queue DataType frontQueue_seq( PSeqQueue paqu ) /* 对非空队列，求队列头部元素 */ { if (isEmptyQueue_seq(paqu)) printf ( “Empty queue.\n" ); else return paqu->q[paqu->front]; } Prof. Q. Wang

3) Variable length Sequential queue #define MaxQueueSize 100 typedef struct _QNode { ElemType *base; int front, rear; }SeqQueue; Status InitQueue(SeqQueue *q); void DestroyQueue(SeqQueue *q); void ClearQueue(SeqQueue *q); BOOL IsQueueEmpty(SeqQueue q); int QueueLength(SeqQueue q); Status GetHead(SeqQueue q, ElemType *elem); Status enQueue(SeqQueue *q, ElemType elem); Status deQueue(SeqQueue *q, ElemType *elem); Prof. Q. Wang

Algorithm 3.21 Initialization Status InitQueue(SeqQueue *q) { q->base = (ElemType *)malloc( sizeof(ElemType)*MaxQueueSize); assert(q->base); q->rear = q->front = 0; return OK; } Prof. Q. Wang

Algorithm 3.22 Element into the Queue Status enQueue(SeqQueue *q, ElemType elem) { PQNode pNode; if (IsQueueFull(*q)) return ERROR; q->base[q->rear] = elem; q->rear = (q->rear+1) % MaxQueueSize; return OK; } … Algorithm 3.23 Element out the Queue Status deQueue(SeqQueue *q, ElemType *elem) { if (IsQueueEmpty(*q)) return ERROR; *elem = q->base[q->front]; q->front = (q->front+1) % MaxQueueSize; return OK; } Prof. Q. Wang

3.7 Applications of Queue Fibonacci Array Yangvi Triangle Others Discrete event simulation Bank transactions Toll gate event Flight scheduling Prof. Q. Wang

Application 1: Fibonacci Array Fn=Fn-1+Fn-2, F1=1, F2=1 1 1 2 3 5 8 13 21 34 … … … … Front 1 1 Rear Front 1 1 2 Rear Prof. Q. Wang

Front 1 1 2 3 Rear Front 1 1 2 3 5 Rear Front 1 1 2 3 5 8 Front Rear 1 1 2 3 5 8 13 Rear Prof. Q. Wang

void Fibonacci ( int n ) { #include "queue.h" void Fibonacci ( int n ) { Queue q; createQueue ( &q); enQueue (&q, 1); enQueue (&q, 1); int s,t; getHead (&q, &s); deQueue (&q); printf (“%d ”, s ); for ( int i=2; i<=n; i++ ) { getHead (&q, &t); deQueue (&q); enQueue (&q, s+t ); s = t; } printf (“\n”); Prof. Q. Wang

Application 2: Yangvi Triangle Pascal’s triangle

Principle 0 1 1 0 0 1 2 1 0 0 1 3 3 1 0 0 1 4 6 4 1 0 0 1 5 10 10 5 1 0 0 1 6 15 20 15 6 1 0 0 1 7 21 35 35 21 7 1 0 Prof. Q. Wang

Principle Prof. Q. Wang

Queue q; createQueue ( &q); enQueue (&q, 1); enQueue (&q, 1); #include "queue.h" void YANGVI ( int n ) { Queue q; createQueue ( &q); enQueue (&q, 1); enQueue (&q, 1); int s = 0; for ( int i=1; i<=n; i++ ) { printf (“\n”); enQueue (&q, 0); for ( int j=1; j<=i+2; j++ ) { int t; getHead (&q, &t); deQueue (&q); enQueue (&q, s+t ); s = t; if ( j != i+2 ) printf (“%d ”, s ); } Process one row Prof. Q. Wang

“划分无冲突子集问题”求解 某运动会设立n个比赛项目，每个运动员可以参加1至3个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。 若将此问题抽象成数学模型，则归属于“划分子集”问题。n个比赛项目构成一个大小为n的集合，有同一运动员参加的项目则抽象为“冲突”关系。 Prof. Q. Wang

例如： 某运动会设有 9 个项目: A ={ 0, 1, 2, 3, 4, 5, 6, 7, 8 }， 7名运动员报名参加的项目分别为： (1, 4, 8), (1, 7), (8, 3), (1, 0, 5), (3, 4), (5, 6, 2), (6, 4) 它们之间的冲突关系为: R = {(1, 4), (4, 8), (1, 8), (1, 7), (8, 3), (1, 0), (0, 5), (1, 5), (3, 4), (5, 6), (5, 2), (6, 2), (6, 4)} |R|=13 Prof. Q. Wang

“划分子集”问题即为: 将集合A划分成k个互不相交的子集A1, A2, …, Ak(k≤n), 使同一子集中的元素均无冲突关系，并且要求划分的子集数目尽可能地少。 对前述例子而言，问题即为: 同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。 Prof. Q. Wang

求解方法 冲突关系：R = {(1, 4), (4, 8), (1, 8), (1, 7), (8, 3), (1, 0), (0, 5), (1, 5), (3, 4), (5, 6), (5, 2), (6, 2), (6, 4)} 2 1 3 7 6 8 4 5 2 1 3 7 6 8 4 5 Prof. Q. Wang

可利用“过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不和第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止。 Prof. Q. Wang

冲突关系表   1 2 3 4 5 6 7 8 0 1 0 0 1 2 1 0 1 0 2 0 0 1 2 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 2 1 0 0 012345678 0237 14568 16 458 45 8

为了减少重复察看 R 数组的时间，可另设一个数组clash[n] 记录和当前已入组元素发生冲突的元素的信息。 每次新开辟一组时，令clash 数组各分量的值均为“0”，当序号为“i”的元素入组时，将和该元素发生冲突的信息记入clash 数组。 Prof. Q. Wang

划分子集算法的基本思想: pre (前一个出队列的元素序号) = n; 组号 = 0; 全体元素入队列; while ( 队列不空 ) { if ( i < pre ) // 开辟新的组 { 组号++; clash 数组初始化; } if ( i 能入组 ) { i 入组，记下序号为 i 的元素所属组号; 修改 clash 数组; } else i 重新入队列; pre = i; Prof. Q. Wang

Application 3: Simulation of an Airport Simulation is the use of one system to imitate the behavior of another system A computer simulation is a program to imitate the behavior of the system under study Prof. Q. Wang

Airport simulation 机场调度 Airport Prof. Q. Wang

3.8 Other special list* 3.8.1 Doubled-End Queue (双端队列) 双端队列是一种特殊的线性表，对它所有的插入和删除都限制在表的两端进行。这两个端点分别记作end1和end2。它好象一个特别的书架，取书和存书限定在两边进行。 3.8.2 Double Stack (双栈) 双栈是一种增加限制的双端队列，它规定从end1插入的元素只能从end1端删除，而从end2插入的元素只能从end2端删除。它就好象两个底部相连的栈。 Prof. Q. Wang

3.8.3 Super Queue (超队列) 超队列是一种输出受限的双端队列，即删除限制在一端(例如end1)进行，而插入仍允许在两端进行。它好象一种特殊的队列，允许有的最新插入的元素最先被删除。 3.8.4 Super Stack (超栈) 超栈是一种输入受限的双端队列，即插入限制在一端（例如end2）进行，而删除仍允许在两端进行。它可以看成对栈溢出时的一种特殊的处理，即当栈溢出时，可将栈中保存最久（end1端）的元素删除。 Prof. Q. Wang

优先队列 优先权有序表：具有特征高优先权的结点将先离开的线性结构。与其到达时刻无关。 实现方法：结点中除包含数据域外，还有本结点的优先权数。   优先权有序表：具有特征高优先权的结点将先离开的线性结构。与其到达时刻无关。 实现方法：结点中除包含数据域外，还有本结点的优先权数。 优先权数越小，优先级越高。 或者： 优先权数越大，优先级越高。 Prof. Q. Wang

顺序存储的优先队列 用数组：队空：front=rear=0; 队满：rear=MaxSize-1 进队时到队尾去排队。 1 2 3 4 5 6   20 15 30 19 19 front rear a. 具有优先数为20、15、30、19的结点依次进队之后。   20 15 30 19 26 24 进队时到队尾去排队。 出队时必须进行查找，然后用最后一个结点覆盖刚刚出队的结点，代价为O(n)。 front rear b. 具有优先数为26、24的结点依次进队后。   20 24 30 19 26 front rear c. 具有最高优先数15的结点出队。用最后一个结点覆盖它。   20 24 30 26 front rear d. 剩余结点中具有最高优先数为19的结点出队之后，用最后一个结点结点覆盖它之后。

Conclusion Concepts of Stack and Queue Comparison of Stack and Queue Application of Stack Expression evaluation Expression transformation Stack and Recursion Application of Queue Discrete event simulation Review Prof. Q. Wang

补充: 中缀前缀 1) 求输入串的逆序。 2) 检查输入的下一元素。 3) 假如是操作数，把它添加到输出串中。 4) 假如是闭括号，将它压栈。 5) 假如是运算符，则    i) 假如栈空，此运算符入栈。    ii) 假如栈顶是闭括号，此运算符入栈。    iii) 假如它的优先级高于或等于栈顶运算符，此运算符入栈。    iv) 否则，栈顶运算符出栈并添加到输出串中，重复步骤5。 6) 假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 7) 假如输入还未完毕，跳转到步骤2。 8) 假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 9) 求输出串的逆序。 Prof. Q. Wang

举例 假设我们要将表达式2*3/(2-1)+5*(4-1)转换成前缀形式： 原表达式的逆序是)1-4(*5+)1-2(/3*2 Prof. Q. Wang

输出串的逆序为+/*23-21*5-41，所以，最终求得的前缀表达式是 +/*23-21*5-41。 原表达式的逆序串：)1-4(*5+)1-2(/3*2 输出串的逆序为+/*23-21*5-41，所以，最终求得的前缀表达式是 +/*23-21*5-41。 Prof. Q. Wang