cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学

Presentation on theme: "cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学"— Presentation transcript:

1 http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
Data Structure and Algorithm 《数据结构及其算法》 cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学

2 第4章 栈和队列 4.1 栈的基本概念 4.2 栈的表示与实现 4.3 栈的应用 4.4 队列的基本概念 4.5 队列表示与实现
4.6 队列的应用 4.7 递归及其应用 2018/12/3 数据结构及其算法 第4章 栈和队列

3 4.1 栈的基本概念 栈(stack)：限定仅在表尾进行插入或删除操作的 线性表
从数据结构角度看，栈也是线性表，或操作受限的 线性表，称为限定性数据结构 Data_Structure = (D,S) 从抽象数据类型角度看，允许的操作不一样，则数 据类型不同 ADT = (D,S,P) 2018/12/3 数据结构及其算法 第4章 栈和队列

4 詹天佑设计的人字形铁路（北京青龙桥车站附近）
设栈S = (a1,a2,...,an) a1称为栈底(bottom)元素 an称为栈顶(top)元素 栈顶插入元素 – 入栈 栈顶删除元素 – 出栈 后进先出(last in first out, LIFO) 出栈 入栈 栈顶 an … 詹天佑设计的人字形铁路（北京青龙桥车站附近） a2 栈底 a1 2018/12/3 数据结构及其算法 第4章 栈和队列

5 4.2 栈的表示与实现 顺序栈：栈的顺序存储结构 类似顺序表 由于总在栈顶插入、删除，保留栈顶位置方便操作 typedef struct {
ElemType *elem; // 基地址 int stacksize; // 当前分配内存大小，单位是sizeof(ElemType) int top; // 栈顶位置，定义为表长-1 } SqStack; 2018/12/3 数据结构及其算法 第4章 栈和队列

6 顺序栈基本操作的实现（算法4.1~4.3） void InitStack_sq(SqStack &S, int msize) {
S.elem = new ElemType[msize]; S.stacksize = msize; S.top = -1; } void DestroyStack_sq(SqStack &S) { delete []S.elem; S.stacksize = 0; bool GetTop_sq(SqStack S, ElemType &e) { if (S.top == -1) return false; e = S.elem[S.top]; return true; 2018/12/3 数据结构及其算法 第4章 栈和队列

7 顺序栈基本操作的实现（算法4.4、4.5） const int SQSTACK_INC_SIZE = 10;
void Increment(SqStack &S, int inc_size = SQSTACK_INC_SIZE) { ElemType *a = new ElemType[S.stacksize + inc_size]; for (int i=0; i<=S.top; ++i) a[i] = S.elem[i]; delete []S.elem; S.elem = a; S.stacksize += inc_size; } void Push_sq(SqStack &S, ElemType e) { if (S.top == S.stacksize-1) Increment(S); S.elem[++S.top] = e; bool Pop_sq(SqStack &S, ElemType &e) { if (S.top == -1) return false; e = S.elem[S.top--]; return true; 2018/12/3 数据结构及其算法 第4章 栈和队列

8 链栈：栈的链式存储结构 链栈基本操作的实现（算法4.6、4.7） 类似链表 由于插入、删除只在栈顶进行，因此将栈顶设为首元结点， 方便操作
typedef LinkList LinkStack; void InitStack_L(LinkStack &S) { S = NULL; } void DestroyStack_L(LinkStack &S) { while (S) { LinkStack p = S; S = S->next; delete p; 2018/12/3 数据结构及其算法 第4章 栈和队列

9 链栈基本操作的实现（算法4.8~4.10） 思考：顺序栈和链栈何者更优？为什么？
bool GetTop_L(LinkStack S, ElemType &e) { if (!S) return false; e = S->data; return true; } void Push_L(LinkStack &S, ElemType e) { LinkStack p = new LNode; p->data = e; p->next = S; S = p; bool Pop_L(LinkStack &S, ElemType &e) { LinkStack p = S; S = S->next; e = p->data; delete p; return true; 思考：顺序栈和链栈何者更优？为什么？ 2018/12/3 数据结构及其算法 第4章 栈和队列

10 4.3 栈的应用 例：数制转换问题 基本等式：N = (N div d) × d + N mod d 计算过程
算出的余数逆序排列即为输出结果 可以利用栈实现 算法4.11 1348 8 168 21 2 余数 4 5 (1348)10=(2504)8 void conversion(int N, int d) { if (N<=0 || d<=0) ErrorMsg("Input error"); Stack S; InitStack(S); while (N) { Push(S, N%d); N = N/d; } int e; while (Pop(S, e)) { cout << e; } cout << endl; } 2018/12/3 数据结构及其算法 第4章 栈和队列

11 如{[(3+5)×2]-7}÷3是合法的表达式， [(3+5]×2)-7或者((3+5)×2]-7)÷3非法
例：括号匹配问题 如{[(3+5)×2]-7}÷3是合法的表达式， [(3+5]×2)-7或者((3+5)×2]-7)÷3非法 规则：从左向右，第一个出现的右括号需要和最后 一个出现的左括号配对，“后进先出” 算法4.12 初始化栈 从左向右读入表达式中的括号 如果是左括号，进栈 如果是右括号，检查栈顶的左括号是否与它配对，若配对则左括 号出栈，否则错误 读入结束后，栈应该是空的，否则错误 思考：如何对算法进行改进，进一步检查括号的优 先级？即：[]中不能有{}，()中不能有[]和{} 2018/12/3 数据结构及其算法 第4章 栈和队列

12 例：N皇后问题 国际象棋中的“后”可以吃掉与她同一行、同一列、同一对 角线的棋子，如何在N×N的棋盘摆上N个皇后，使得她们 彼此吃不到对方？ 典型算法：试探-回溯法 思路： 逐行试探，先在第一行摆一个，再在第二行摆一个，…… N行全部摆好，说明找到一种解法 如果某一行无法摆放，说明之前行的摆法不可行，退回到上一行重新摆放 数据结构： 采用栈记录皇后摆放位置，以便回溯 附设列、左下对角线、右下对角线三个数组防止皇后冲突 2018/12/3 数据结构及其算法 第4章 栈和队列

13 思考：如何对程序进行修改以找出所有的解？
void queen(int N) { // 使用栈求解N皇后问题 bool *A = new bool[N], *B = new bool[2*N-1], *C = new bool[2*N-1]; for (int i=0; i<N; ++i) A[i] = false; for (int i=0; i<2*N-1; ++i) B[i] = false; for (int i=0; i<2*N-1; ++i) C[i] = false; Stack S; InitStack(S); int sj = 0; while (true) { int i = StackLength(S); bool feasible = false; if (i < N) for (int j = sj; j < N; ++j) { if (place(i, j, N, A, B, C)) { mark(i, j, N, true, A, B, C); Push(S, j); if (i == N-1) { print(S); return; } feasible = true; break; } if (!feasible) { int j; if (!Pop(S, j)) break; mark(i-1, j, N, false, A, B, C); sj = j+1; else sj = 0; bool place(int i, int j, int N, bool *A, bool *B, bool *C) { return !(A[j] || B[i+j] || C[i-j+N-1]); } void mark(int i, int j, int N, bool flag, bool *A, bool *B, bool *C) { A[j] = B[i+j] = C[i-j+N-1] = flag; } 思考：如何对程序进行修改以找出所有的解？ 2018/12/3 数据结构及其算法 第4章 栈和队列

14 一般的算术表达式又称中缀表达式(infix notation)，如：4×2+(7-8÷2)，运算符在操作 数中间，需要用括号来表示运算顺序
例：表达式求值问题（算符优先法） 一般的算术表达式又称中缀表达式(infix notation)，如：4×2+(7-8÷2)，运算符在操作 数中间，需要用括号来表示运算顺序 例：计算一位整数、无括号的四则运算7-8÷2+… 7 操作数 - 运算符 8 操作数 此时不能计算7-8，后续可能×或÷，7、8、-分别保存 ÷ 运算符 2 操作数 + 运算符 前一运算符÷可做，因为÷优先于+ 计算8（前一操作数）÷2，运算结果为4 再前一运算符-可做，因为左侧-优先于+ 计算7-4，运算结果为3，保存 …… 2018/12/3 数据结构及其算法 第4章 栈和队列

15 运算符：要和前一个比较优先级 操作数：要和前一个进行计算 表达式求值算法 设两个栈 运算符栈保存暂时不能计算的运算符
操作数栈保存暂时不能计算的操作数或中间结果 虚设一对'#'构成整个表达式的界限符(delimiter) 读入操作数直接入栈 读入运算符或()或#，进行算符优先级判断和相应操作 设两个栈 2018/12/3 数据结构及其算法 第4章 栈和队列

16 例：计算#4×2+(7-8÷2)#的过程 OPTR OPND OPTR OPND # OPTR OPND # 8 + 7 ( - ) + )
3 OPTR OPND # 8 + # 7-4 8+3 3 11 2018/12/3 数据结构及其算法 第4章 栈和队列

17 算法4.16 char Precede(char c1, char c2) {
if (c1 == '+' && c2 == '+') return '>'; ... } 算法4.16 int EvaluateExpression(char *expr) { Stack SOP, SVAL; InitStack(SOP); Push(SOP, '#'); InitStack(SVAL); expr[strlen(expr)] = '#'; char tmp[2]; int i=0; char c=expr[i++]; while (c != '#' || GetTop(SOP) != '#') { if (!IsOperator(c)) { tmp[0] = c; tmp[1] = '\0'; Push(SVAL, atoi(tmp)); c = expr[i++]; } else switch(Precede(GetTop(SOP), c)) { case '<': Push(SOP, c); c = expr[i++]; break; case '=': Pop(SOP, c); c = expr[i++]; break; case '>': char theta; Pop(SOP, theta); int a, b; Pop(SVAL, b); Pop(SVAL, a); Push(SVAL, Operate(a, theta, b)); break; expr[strlen(expr)] = '\0'; return GetTop(SVAL); bool IsOperator(char c) { return c == '+' || c == '-' ... } int Operate(int a, char c, int b) { if (c == '+') return a+b; ... } 2018/12/3 数据结构及其算法 第4章 栈和队列

18 三种表达式 表达式的相互转换 如4×2+(7-8÷2)转为逆波兰式：42×782÷-+ 逆波兰式中，运算符的出现顺序决定了运算顺序
将中缀表达式转为逆波兰式，可以用操作符栈来实现 对逆波兰式求值，可以用操作数栈来实现 表达式 前缀(prefix)表达式 中缀(infix)表达式 后缀(postfix)表达式 别名 波兰式(Polish notation) 逆波兰式(Reverse Polish notation) 特点 运算符在操作数之前 运算符在操作数中间 需要括号表示优先级 运算符在操作数之后 例 *a+bc a*(b+c) abc+* 2018/12/3 数据结构及其算法 第4章 栈和队列

19 逆波兰式求值（算法4.14） 例：42×782÷-+ 出现操作数则入栈 出现运算符则出栈两个数，运算结果入栈 OPND OPND OPND
3 4 8 8 8 11 2018/12/3 数据结构及其算法 第4章 栈和队列

20 中缀表达式转为逆波兰式（算法4.15） 例：4×2+(7-8÷2) 出现操作数则直接输出 出现运算符则与栈顶元素比较优先级 ) # ÷ -
OPTR OPTR OPTR 4 2 × 7 8 2 ÷ - + 2018/12/3 数据结构及其算法 第4章 栈和队列

21 4.4 队列的基本概念 队列(queue)：只允许在表的一端插入元素、而在 另一端删除元素的线性表 插入端：队尾(rear, back)
同样是操作受限的线性表 插入端：队尾(rear, back) 删除端：队头(front) 先进先出(first in first out, FIFO) 2018/12/3 数据结构及其算法 第4章 栈和队列

22 队列应用举例 若队列中数据元素有优先级，则称优先队列 银行排队系统（客户取号、柜台叫号） 计算机操作系统中的多任务调度 2018/12/3
数据结构及其算法 第4章 栈和队列

23 双端队列(double-ended queue, deque)：只 允许插入和删除操作在表的两端进行的线性表 栈、队列都是双端队列的特例
C++中提供stack、queue、deque三个类 2018/12/3 数据结构及其算法 第4章 栈和队列

24 4.5 队列表示与实现 链队列：队列的链式存储结构 头指针 – 指向附设头结点，便于删除元素 尾指针 – 便于插入元素
typedef LinkList QueuePtr; typedef struct { QueuePtr front; // 头指针 QueuePtr rear; // 尾指针 } LinkQueue; 2018/12/3 数据结构及其算法 第4章 栈和队列

25 链队列基本操作的实现 构造空队列 判断队列是否为空 void InitQueue_L(LinkQueue &Q) {
Q.front = Q.rear = new LNode; Q.front->next = NULL; } bool QueueEmpty_L(LinkQueue Q) { return Q.front == Q.rear; // 或者 return Q.front->next == NULL; } 2018/12/3 数据结构及其算法 第4章 栈和队列

26 入队 出队 void EnQueue_L(LinkQueue &Q, ElemType e) {
QueuePtr p = new LNode; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; } bool DeQueue_L(LinkQueue &Q, ElemType &e) { if (QueueEmpty_L(Q)) return false; QueuePtr p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; // 注意：队列变空特殊处理 delete p; return true; } 2018/12/3 数据结构及其算法 第4章 栈和队列

27 简单照搬顺序表的实现方法，造成存储空间浪费， 移动元素太耗时 解决方法：假想存储空间为“环形”
顺序队列：队列的顺序存储结构 头指针指向队首元素 约定：尾指针指向队尾元素的下一个位置 简单照搬顺序表的实现方法，造成存储空间浪费， 移动元素太耗时 解决方法：假想存储空间为“环形” 2018/12/3 数据结构及其算法 第4章 栈和队列

28 循环队列：用假想的“环形”存储空间表示的队列 实际存储空间为线性，“环形”是通过计算来模拟
用长度为R的数组来表示环，则某一位置x的下一位置为 (x+1)%R 两个位置x和y之间的距离为 (y-x+R)%R 2018/12/3 数据结构及其算法 第4章 栈和队列

29 循环队列的问题：如何区分队空和队满 解决方案：少用一个元素空间，约定 “头指针在尾指针的下一位置”表示队满 “头尾相等”表示队空
2018/12/3 数据结构及其算法 第4章 栈和队列

30 循环队列的实现 循环队列基本操作的实现 构造空队列 typedef struct { ElemType *elem; // 基地址
int queuesize; // 当前分配内存大小 int front; int rear; } SqQueue; void InitQueue_sq(SqQueue &Q, int msize) { Q.elem = new ElemType[msize]; Q.queuesize = msize; Q.front = Q.rear = 0; } 2018/12/3 数据结构及其算法 第4章 栈和队列

31 求队列长度 入队 出队 int QueueLength_sq(SqQueue Q) {
return (Q.rear - Q.front + Q.queuesize) % Q.queuesize; } void EnQueue_sq(SqQueue &Q, ElemType e) { if ((Q.rear+1) % Q.queuesize == Q.front) Increment(Q); Q.elem[Q.rear] = e; Q.rear = (Q.rear+1) % Q.queuesize; } bool DeQueue_sq(SqQueue &Q, ElemType &e) { if (Q.front == Q.rear) return false; e = Q.elem[Q.front]; Q.front = (Q.front+1) % Q.queuesize; return true; } 2018/12/3 数据结构及其算法 第4章 栈和队列

32 思考：还有哪些方法可以实现循环队列，避免队空 和队满的混淆问题？ 方法1：设变量length表示队列长度
方法2：设标志位full表示是否队满 方法3：设标志位empty表示是否队空 typedef struct { ElemType *elem; // 基地址 int queuesize; // 当前分配内存大小 int front, rear, length; // 保留front或者rear之一即可 } SqQueue; 2018/12/3 数据结构及其算法 第4章 栈和队列

33 4.6 队列的应用 例：打印二项式系数 常规算法（使用两个辅助数组） void yanghui(int n) {
int *k_line = new int[n+1], *kp_line = new int[n+1]; k_line[0] = 1; k_line[1] = 1; int k = 1; while (k <= n) { for (int i=0; i<n-k; ++i) cout << ' '; for (int i=0; i<k+1; ++i) cout << k_line[i] << ' '; cout << endl; if (k == n) break; kp_line[0] = 1; for (int i=1; i<k+1; ++i) kp_line[i] = k_line[i-1] + k_line[i]; kp_line[k+1] = 1; int *p = kp_line; kp_line = k_line; k_line = p; ++k; } 2018/12/3 数据结构及其算法 第4章 栈和队列

34 算法4.27（使用队列） void yanghui_queue(int n) {
SqQueue Q; InitQueue_sq(Q, n+3); EnQueue_sq(Q, 0); EnQueue_sq(Q, 1); EnQueue_sq(Q, 1); int k = 1; int s, e; while (k < n) { for (int i=0; i<n-k; ++i) cout << ' '; EnQueue_sq(Q, 0); do { DeQueue_sq(Q, s); GetHead_sq(Q, e); if (e) cout << e << ' '; else cout << endl; EnQueue_sq(Q, s+e); } while (e); ++k; } DeQueue_sq(Q, e); while (QueueLength_sq(Q) > 0) { DeQueue_sq(Q, e); cout << e << ' '; cout << endl; 2018/12/3 数据结构及其算法 第4章 栈和队列

35 仿真(simulation)是一类重要的计算机应用，可 以辅助系统设计与优化 数据结构：客户、银行窗口、排队
例：银行排队系统仿真 仿真(simulation)是一类重要的计算机应用，可 以辅助系统设计与优化 数据结构：客户、银行窗口、排队 typedef struct { char *name; // 客户姓名 int arrival; // 客户到达银行的时间 int service_time; // 客户办理业务所需时间 } customer; enum status {idle, busy}; status cur_status; // 窗口当前状态：忙or闲 int cur_start_time; // 当前状态开始的时间 int cur_customer; // 当前服务客户的编号（如果在忙） } window; void bank_simulation(int, customer*, int, window*); 2018/12/3 数据结构及其算法 第4章 栈和队列

36 void bank_simulation(int nc, customer *cust, int nw, window *win) {
const int TIME = 60; int t = 0; int c, w; int idw = nw; SqQueue Q; InitQueue_sq(Q, 100); cout << "Bank open now" << endl; ... // 所有窗口状态初始化为idle while (t < TIME || QueueLength_sq(Q) > 0 || idw < nw) { if (t < TIME) for (c=0; c<nc; ++c) if (cust[c].arrival == t) EnQueue_sq(Q, c); for (w=0; w<nw; ++w) if (win[w].cur_status == busy) { c = win[w].cur_customer; if (t - win[w].cur_start_time == cust[c].service_time) { win[w].cur_status = idle; win[w].cur_start_time = t; ++idw; }} for (w=nw-1; w>=0; --w) { if (win[w].cur_status == idle && QueueLength_sq(Q) > 0) { DeQueue_sq(Q, c); --idw; ... // 将窗口状态改为busy ++t;} cout << "Bank close now" << endl; } 2018/12/3 数据结构及其算法 第4章 栈和队列

37 4.7 递归及其应用 程序设计中如何实现函数调用？ 后调用，先返回——使用栈 int main() {
int s = first(1,2,3); printf("%d\n", s); } int first(int a, int b, int c) { return a + second(b, c); } int second(int x, int y) { return x - third(y); } int third(int z) { return z * z; } 后调用，先返回——使用栈 2018/12/3 数据结构及其算法 第4章 栈和队列

38 函数调用的执行过程 系统工作栈：用于函数调用的栈结构 栈中的数据元素为函数的工作状态 以递归函数为例，解释系统工作栈原理
调用之前，将调用函数的工作状态（当前位置、当前变量 等）入栈保存 调用：形实结合、转移到被调用函数并执行 调用之后：出栈恢复调用函数的工作状态，继续执行调用 函数 系统工作栈：用于函数调用的栈结构 栈中的数据元素为函数的工作状态 当前位置、当前变量等 以递归函数为例，解释系统工作栈原理 2018/12/3 数据结构及其算法 第4章 栈和队列

39 递归函数：（直接或间接）调用自身的函数 很多数学函数是用递归的方式定义的 递归函数的正确性判断：有限步终止 如斐波那契数列
int fib(unsigned int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); } int fib(unsigned int n) { return fib(n-1) + fib(n-2); } 要理解递归，先要理解递归 int fib(unsigned int n) { if (n <= 1) return n; else return fib(n+2) - fib(n+1); } 2018/12/3 数据结构及其算法 第4章 栈和队列

40 Hanoi塔问题 最简问题：将1个盘子由X移到Z 问题规约：将n个盘子由X移到Z 算法4.31 将n-1个盘子由X移到Y 将盘子n由X移到Z
将n-1个盘子由Y移到Z 算法4.31 void hanoi(int n, char x, char y, char z) { if (n==1) move(x,1,z); else { hanoi(n-1, x, z, y); move(x,n,z); hanoi(n-1, y, x, z); } void move(char u, int i, char v) { printf("move %d from %c to %c", i, u, v); } 2018/12/3 数据结构及其算法 第4章 栈和队列

41 系统工作栈示例 int main() { hanoi(3, 'A', 'B', 'C'); 0 }
1 void hanoi(int n, char x, char y, char z) { 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 } } 返回位置 当前变量 n=3,x=A,y=B,z=C 返回位置 当前变量 6 n=2,x=A,y=C,z=B n=3,x=A,y=B,z=C 返回位置 当前变量 6 n=1,x=A,y=B,z=C n=2,x=A,y=C,z=B n=3,x=A,y=B,z=C 系统工作栈示例 2018/12/3 数据结构及其算法 第4章 栈和队列

42 系统工作栈示例 int main() { hanoi(3, 'A', 'B', 'C'); 0 }
1 void hanoi(int n, char x, char y, char z) { 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 } } 返回位置 当前变量 n=3,x=A,y=B,z=C 返回位置 当前变量 6 n=2,x=A,y=C,z=B n=3,x=A,y=B,z=C 返回位置 当前变量 8 n=1,x=C,y=A,z=B 6 n=2,x=A,y=C,z=B n=3,x=A,y=B,z=C 系统工作栈示例 2018/12/3 数据结构及其算法 第4章 栈和队列

43 系统工作栈示例 int main() { hanoi(3, 'A', 'B', 'C'); 0 }
1 void hanoi(int n, char x, char y, char z) { 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 } } 返回位置 当前变量 n=3,x=A,y=B,z=C 返回位置 当前变量 8 n=2,x=B,y=A,z=C n=3,x=A,y=B,z=C 返回位置 当前变量 6 n=1,x=B,y=C,z=A 8 n=2,x=B,y=A,z=C n=3,x=A,y=B,z=C 系统工作栈示例 2018/12/3 数据结构及其算法 第4章 栈和队列

44 系统工作栈示例 int main() { hanoi(3, 'A', 'B', 'C'); 0 }
1 void hanoi(int n, char x, char y, char z) { 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 } } 返回位置 当前变量 n=3,x=A,y=B,z=C 返回位置 当前变量 8 n=2,x=B,y=A,z=C n=3,x=A,y=B,z=C 返回位置 当前变量 8 n=1,x=A,y=B,z=C n=2,x=B,y=A,z=C n=3,x=A,y=B,z=C 系统工作栈示例 2018/12/3 数据结构及其算法 第4章 栈和队列

45 时间复杂度分析 void hanoi(int n, char x, char y, char z) {
if (n==1) move(x,1,z); else { hanoi(n-1, x, z, y); move(x,n,z); hanoi(n-1, y, x, z); } ℎ(𝑛)= 𝑛=1时 2 𝑛≠1时 2+2ℎ(𝑛−1) h(n)=O(2n) 2018/12/3 数据结构及其算法 第4章 栈和队列

46 当递归函数计算复杂度过高时，应考虑不用递归的 替代方案
递归函数的特点 优点 结构清晰、可读性好 正确性容易证明 缺点 时间复杂度高（递归自身特性、函数调用） 空间复杂度高（系统工作栈） 递归函数可以用栈改写 当递归函数计算复杂度过高时，应考虑不用递归的 替代方案 如：计算斐波那契数列的非递归算法 2018/12/3 数据结构及其算法 第4章 栈和队列

47 算法4.32 N皇后问题的递归算法 思考：对比13页算法，修改程序找出第一组解就返回
void queen_recur(int i, int N, bool *A, bool *B, bool *C, int *result) { for (int j = 0; j < N; ++j) { if (place(i, j, A, B, C)) { mark(i, j, true, A, B, C); result[i] = j; if (i==N-1) { for (int k=0; k<N; ++k) cout << result[k] << ' '; cout << endl; } else queen_recur(i+1, N, A, B, C, result); mark(i, j, false, A, B, C);} void queen2(int N) { // 递归算法求解N皇后问题 bool *A = new bool[N], *B = new bool[2*N-1], *C = new bool[2*N-1]; for (int i=0; i<N; ++i) A[i] = false; for (int i=0; i<2*N-1; ++i) B[i] = false; for (int i=0; i<2*N-1; ++i) C[i] = false; int *res = new int[N]; queen_recur(0, N, A, B, C, res); 思考：对比13页算法，修改程序找出第一组解就返回 2018/12/3 数据结构及其算法 第4章 栈和队列

48 本章复习提纲 栈和队列的基本概念 栈和队列的表示与实现 栈的应用 系统工作栈、递归函数、递归与栈的等价性 顺序栈、链栈、循环队列、链队列
基本操作的实现 栈的应用 表达式求值（三种表达式） 系统工作栈、递归函数、递归与栈的等价性 2018/12/3 数据结构及其算法 第4章 栈和队列

49 作业 4.2, 4.6, 4.8, 4.11, 4.14, 4.16 4.2 出栈序列 4.6 判断逆序序列算法 4.8 转逆波兰式算法
4.11 循环队列算法 4.14 递归转非递归算法 4.16 递归单链表逆序算法 2018/12/3 数据结构及其算法 第4章 栈和队列