第3章栈和队列分解.ppt

?§3.1 栈(Stack) §3.2 栈的应用举例 §3.3 栈与递归的实现 §3.4 队列(Queue) 栈：是一种插入和删除操作被限定在表尾的线性表。 记作:S=(a1,a2,…,an) 栈底：线性表的第一个元素 栈顶：线性表的最后一个元素 栈空：线性表长度为0 操作特点： 先进后出（First In Last Out）? 或后进先出（Last In First Out） 思考：A, B, C, D依次进栈，以下出栈序列中，哪些是可能的？哪些是不可能的？ 栈的基本运算: 初始化空栈： InitStack(S) 销毁栈： DestroyStack(S) 清空栈： ClearStack(S) 判栈空: StackEmpty(S) 求栈长： StackLength(S) 读栈顶： GetTop(S, e)或 GetTop(S) 进栈： Push(S, e) 出栈： Pop(S, e) 一、顺序存储结构----顺序栈 二、链式存储结构----链栈 一、顺序栈 typedef struct { SElemType *base; //数组首地址 SElemType *top; //栈顶指针 int stacksize; //栈容量 }SqStack； 基本运算在顺序栈上的实现 读栈顶： 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 StackEmpty(SqStack S){ //若栈空，返回TRUE；否则返回FALSE。 if(S.top==S.base) return TRUE； //栈空 else return FALSE; }//StackEmpty 基本运算在顺序栈上的实现 进栈： Status Push(SqStack S, SElemType e){ //插入元素e为新的栈顶元素 if(S.top-S.base==S.stacksize) {//栈满，追加空间 S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.stacksize+=STACKINCREMENT; } *(S.top++)=e; return OK; }//Push 基本运算在顺序栈上的实现 出栈： status Pop(SqStack S, SElemType e){ //若栈不空，则删除栈顶元素，用e返回其值，并返回OK； //否则返回ERROR if(S.top==S.base) return ERROR; //栈空 e=*（--S.top）; return OK; }//Pop 链栈结点存储结构： typedef struct SNode{ ElemType data； struct SNode *next； }SNode ，LinkStack； 基本运算在链栈上的实现 入栈： status Push(LinkStack S, SElemType e){ //插入元素e为新的栈顶元素 p=（LinkStack）malloc（sizeof（SNode））； if(!p) exit(OVERFLOW); p-data=e; p-next=S-next; S-next=p; //头插栈顶元素 return OK; }//Pusp 基本运算在链栈上的实现 出栈： status Pop(LinkStack S, SElemType e){ //若栈不空，则删除栈顶元素，用e返回其值，并返回OK； //否则返回ERROR if(S-next==NULL) return ERROR; //栈空 p=s-next; e=p-data; S-next=p-next; free(p); //删除栈顶元素 return OK; }//Pop 三、多个栈共享存储空间 问题：多个同类型的栈，但多数时候某些栈不满，而某些栈过剩，如何更合理利用存储空间？ 解决：多个栈共享同一个静态