《数据结构第3章.ppt

第3章 第3章 栈和队列 栈和队列内容 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.1 栈 ( Stack ) 1.定义：限定只在表的一端(表尾)进行 插入和删除操作的线性表 特点:后进先出(LIFO) 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 栈的常用运算 置空栈—完成对栈的初始化。 判断栈空—若栈S为空则返回真，否则返回假。 进栈——Push(S，e)，在栈S的栈顶插入数据元素 e。 出栈—Pop(S)，删除栈S的栈顶数据元素，并将数据元素返回。 取栈顶元素—GetTop(S)，取栈S的栈顶数据元素，并把数据元素返回。该操作完成后，栈的状态不变。 2. 栈的表示和实现 1）顺序栈——栈的顺序存储结构 2）链栈——栈的链式存储结构 3）静态分配整型指针 1）顺序栈——栈的顺序存储结构 限定在表尾进行插入和删除操作的顺序表 指针类型定义: (p46) typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; SqStack s; 说明： base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 top为栈顶指针（所指单元为空） a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 stacksize ——当前栈可使用的最大容量 几点说明： 栈空条件：s. top =s. base 此时不能出栈 栈满条件：s.top-s.base=s.stacksize 进栈操作：*s.top++=e; 或*s.top=e; s.top++; 退栈操作：e=*--s.top； 或s.top--； e=*s.top； 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。 基本操作的实现 栈的初始化操作 p47 Status InitStack(SqStack S) 取栈顶元素 p47 Status GetTop(SqStack S, SElemType e) 进栈操作 p47 Status Push(SqStack S, SElemType e) 退栈操作 p47 Status Pop(SqStack S, SElemType e) 栈的初始化操作 p47 Status InitStack (SqStack S) { S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.base) return (OVERFLOW); S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; } 取栈顶元素 p47 Status GetTop(SqStack S, SElemType e) { if (S.top == S.base) return ERROR; e = *(S.top-1); return OK; } 进栈操作 p47 Status Push(SqStack S, SElemType e) { if (S.top-S.base=S.stacksize) { S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT) *sizeof(ElemType)); if (!S.base) return (OVERFLOW); S.top = S.base +S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; /* *S.top = e; S.top = S.top+1; return OK; } 退栈操作 p47 Status Pop(SqStack S, SElemType e)