数据结构基础3.pptVIP

第三章 栈和队列 本章学习目的、要求、重点、难点 栈和队列是两种重要的线性结构。从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表，因此，可称为限定性的数据结构；但从数据类型的角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛的应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。 //-----基本操作的算法描述（部分）----- Status InitStack (SqStack S ); // 构造一个空栈S S.base = (SElemType*) malloc (STACK_INIT_SIZE?sizeof (ElemType)); if (! S.base) exit(OVERFLOW); //存储分配失败 S.top =S.base; S.stacksize =STACK_INIT_SIZE; return OK; }//InitStack Status GetTop (SqStack S , SElemType e ) //若栈不空，则用e返回S的栈顶元素，并 //返回OK，否则返回ERROR if(S.top ==S.base) return ERROR; e=*(S.top-1); return OK; }// GetTop Status Push (SqStack S , SElemType e ) { // 插入元素e为新的栈顶元素 if(S.top -S.base = S.stacksize) { { // 当前存储空间已满，增加分配 S.base = (ElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof (ElemType)); if (! S.base ) exit(OVERFLOW); // 存储分配失败 S.top =S.base+S.stacksize; S.stacksize+= STACKINCREMENT //增加存储容量 } *S.top++=e; return OK; }// Push Status Pop (SqStack S , SElemType e ) //若栈不空，则删除S的栈顶元素，并 //用e返回其值，并返回OK，否则返回 //ERROR if(S.top ==S.base) return ERROR; e=*--S.top; return OK; }// Pop 如何从后缀式求值？ 先找运算符，再找操作数 OperandType EvaluateExpression() { //算术表达式求值的算符优先算法。设OPTR和OPND //分别为运算符栈和运算数栈，OP为运算符集合。 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’=’: //脱括号并接受下一字符