北京工业大学：数据结构和算法分析 教学第三章 栈和队.ppt

typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr; 链队列——链式映象 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列 0 1 2 3 4 5 6 7 a b c Q.rear Q.front Q.rear d 按循环机制使用数组空间 Q.rear = (Q.rear+1) Q.front = (Q.front+1) 通过头尾指针的循环使用,顺序空间即可当循环空间来使用，称循环队。循环使用指针在技术上是由取模实现的： % MAXQSIZE; % MAXQSIZE; 队列的上机大作业: 离散事件模拟（银行的排队事例） 请先阅读材料 [1] P65~69 [3] P250~259 * 第三章 栈与队 栈与队是一种限定性结构 3.1 栈的类型定义 3.2 栈的应用举例 3.3 栈类型的实现 3.4 队列的类型定义 3.5 队列类型的实现 3.1 栈的类型定义 ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack InitStack(S) DestroyStack(S) ClearStack(S) StackEmpty(s) StackLength(S) GetTop(S, e) Push(S, e) Pop(S, e) StackTravers(S, visit( )) A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. 例一、 数制转换 算法基于原理： N = (N div d)×d + N mod d  3.2 栈的应用举例 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2 计算顺序 输出顺序 void conversion () { InitStack(S); cinN; while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); coute; } } // conversion 在实际问题中全进全退是特殊情况，一般进栈与退栈往往是交错进行的。 例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 (( )]) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。 分析可能出现的不匹配的情况: 到来的右括弧非是所“期待”的; 例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 到来的是“不速之客”; 直到结束，也没有到来所“期待”的括弧; 算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则与栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余