Chapter 03 Stack & Queue 第三章 栈和队列

Presentation on theme: "Chapter 03 Stack & Queue 第三章 栈和队列"— Presentation transcript:

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

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

3 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

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

5 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

6 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

7 Examples of Push and Pop
Prof. Q. Wang

8 Prof. Q. Wang

9 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

10 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

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

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

13 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

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

15 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

16 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

17 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

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

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

20 Example Prof. Q. Wang

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

22 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

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

24 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

25 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

26 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

27 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

28 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

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

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

31 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

32 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

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

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

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

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

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

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

39 + ( 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

40 算法: 求中缀表达式值 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

41 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

42 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

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

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

45 算法: 求后缀表达式值 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

46 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

47 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

48 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

49 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

50 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

51 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

52 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

53 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

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

55 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

56 #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

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

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

59 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

60 #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

61 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

62 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

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

64 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

65 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

66 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

67 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

68 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

69 规则: 多个函数嵌套调用时，按照“后调用先返回”的原则进行。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

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

71 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

72 Tree of subprogram calls
Prof. Q. Wang

73 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

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

75 Recursive solution of Hanoi tower
Line void Hanoi (int n, char x, char y, char z) 1 { if (n = = 1) move(x, 1, z); else { Hanoi (n-1, x, z, y); move (x, n, z); Hanoi (n-1, y, x, z); } 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

76 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

77 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

78 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

79 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

80 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

81 Supplementary Materials
Maze Eight Queen Puzzle Prof. Q. Wang

82 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

83 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

84 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

85 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

86 背包问题的非递归求解 首先我们设计一个栈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

87 栈用顺序存储结构实现，栈中元素和变量的说明如下： 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

88 转换的做法按以下规律进行，凡调用语句 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

89 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

90 { 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

91 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

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

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

94 入口 出口 Prof. Q. Wang

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

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

97 栈用顺序存储结构实现，栈中元素的说明如下： 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

98 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

99 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

100 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

101 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

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

103 Example Rear Head Prof. Q. Wang

104 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

105 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

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

107 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

108 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 Judge a linked queue empty or not int isEmptyQueue_link( PLinkQueue plqu ) { return (plqu->front == NULL); } Prof. Q. Wang

109 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

110 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

111 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

112 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

113 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

114 (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

115 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

116 #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

117 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

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

119 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

120 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

121 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

122 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

123 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

124 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

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

126 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

127 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

128 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

129 Application 2: Yangvi Triangle
Pascal’s triangle

130 Principle Prof. Q. Wang

131 Principle Prof. Q. Wang

132 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

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

134 例如： 某运动会设有 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

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

136 求解方法 冲突关系：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

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

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

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

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

141 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

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

143 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

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

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

146 顺序存储的优先队列 用数组：队空：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的结点出队之后，用最后一个结点结点覆盖它之后。

147 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

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

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

150 输出串的逆序为+/*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