顺序栈基本操作的实现(算法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)alil=selem[i] delete Selem;selem=a; s. stacksize + inc size; void Push sq (SqStack &S, ElemType e)i if (s top== S. stacksize-1)Increment(S); elem[++s top]=ej bool Pop sq(sqstack &S, ElemType &e)t if (stop ==-1)return false; e=selems.top--] return true 2021/1/29 数据结构及其算法第4章栈和队列
•顺序栈基本操作的实现（算法4.4、4.5） 2021/1/29 数据结构及其算法 第4章 栈和队列 7 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; }
链栈:栈的链式存储结构 类似链表 由于插入、删除只在栈顶进行,因此将栈顶设为首元结点, 方便操作 typedef LinkList LinkStack 链栈基本操作的实现(算法4.6、4.7) void Initstack L(LinkStack &s)i SE NULL data next 找顶 void DestroyStack L(LinkStack &s)i While(S)i Linkstack p= S;S=S->next; delete p; A栈底 2021/1/29 数据结构及其算法第4章栈和队列
•链栈：栈的链式存储结构 • 类似链表 • 由于插入、删除只在栈顶进行，因此将栈顶设为首元结点， 方便操作 •链栈基本操作的实现（算法4.6、4.7） 2021/1/29 数据结构及其算法 第4章 栈和队列 8 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; } }
链栈基本操作的实现(算法4.8~4.10) bool GetTop L(LinkStack S, Elem Type &e)i if(s return false; s->data; return true; void Push L(LinkStack &S, Elem Type e)i Linkstack p= new LNode p->data =e; p->next =S;s=p; bool Pop L(LinkStack &S, Elem Type &e)i if (s return false; LinkStack p= S:S=S->next p->data; delete p; return true; 思考:顺序栈和链栈何者更优?为什么? 2021/1/29 数据结构及其算法第4章栈和队列
•链栈基本操作的实现（算法4.8~4.10） 2021/1/29 数据结构及其算法 第4章 栈和队列 9 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) { if (!S) return false; LinkStack p = S; S = S->next; e = p->data; delete p; return true; } 思考：顺序栈和链栈何者更优？为什么？
4.3栈的应用 例:数制转换问题 基本 N=( n div o)×d+ n mod d 计算过程 算出的余数逆序排列即为输出结果 81348 余数可以利用栈实现 8168 算法4.11 821 void conversion (int N, int d)i if(n<=0 d<=0)ErrorMsg("Input error); 82 Stack S; Initstack(s); ile(N)i Push(S, N%d) N/d;] int e (1348)10=(2504)8 While(Pop(s, e))icout < e; y 止t<<endl 2021/1/29 数据结构及其算法第4章栈和队列
4.3 栈的应用 •例：数制转换问题 •基本等式：N = (N div d) × d + N mod d •计算过程 2021/1/29 数据结构及其算法 第4章 栈和队列 10 8 1348 8 168 8 21 8 2 0 余数 4 0 5 2 (1348)10=(2504)8 算出的余数逆序排列即为输出结果 可以利用栈实现 算法4.11 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; }
例:括号匹配问题 如{[(3+5)×2]-7}÷3是合法的表达式, [(3+5]×2)-7或者(3+5)×2]-7)÷3非法 规则:从左向右,第一个出现的右括号需要和最后 个出现的左括号配对,“后进先出” 算法4.12 初始化栈 从左向右读入表达式中的括号 如果是左括号,进栈 如果是右括号,检查栈顶的左括号是否与它配对,若配对则左括 号出栈,否则错误 读入结束后,栈应该是空的,否则错误 思考:如何对算法进行改进,进一步检查括号的优 先级?即:[]中不能有{},()中不能有[]和{} 2021/1/29 数据结构及其算法第4章栈和队列
•例：括号匹配问题 •如{[(3+5)×2]-7}÷3是合法的表达式， [(3+5]×2)-7或者((3+5)×2]-7)÷3非法 •规则：从左向右，第一个出现的右括号需要和最后 一个出现的左括号配对，“后进先出” •算法4.12 • 初始化栈 • 从左向右读入表达式中的括号 • 如果是左括号，进栈 • 如果是右括号，检查栈顶的左括号是否与它配对，若配对则左括 号出栈，否则错误 • 读入结束后，栈应该是空的，否则错误 •思考：如何对算法进行改进，进一步检查括号的优 先级？即：[]中不能有{}，()中不能有[]和{} 2021/1/29 数据结构及其算法 第4章 栈和队列 11