ds3.1陆小马功钟浩.ppt

§3.1 栈 栈和栈的实现 §3.1 栈 §3.1 栈 栈及其特点 栈的ADT定义 栈的顺序存储结构——顺序栈 栈的链式存储结构——链栈 1.栈及其特点（1） （1）什么是栈？ 栈(Stack)是一种特殊的线性表。 S = (a1, a2, … , an) 仅在表尾进行插入和删除。 表尾称为栈顶(top)，表头称为栈底(bottom)。 插入元素称为入栈(push)。 删除元素称为出栈(pop)。 1.栈及其特点（2） （2）栈的操作有何特点？ 最先出栈的必定是最后进栈的栈顶元素。 后进先出(LIFO) 2.栈的ADT定义 ADT Stack { 数据对象： 数据关系： 基本操作： InitStack ( S ) 构造空栈S DestroyStack ( S ) 销毁栈S ClearStack ( S ) 清空栈S StackEmpty ( S ) 判断栈S是否为空 StackLength ( S ) 栈中元素个数 GetTop ( S, e ) 取栈顶元素 Push ( S, e ) 入栈 Pop ( S, e ) 出栈 StackTraverse ( S, visit ) 遍历栈 } ADT Stack; 3.栈的顺序存储结构——顺序栈 （1）顺序栈的类型定义 （2）顺序栈的基本形态 （3）顺序栈基本操作的实现 （4）顺序栈与顺序表 （1）顺序栈的类型定义 //顺序栈的最大容量 const int MAXSIZE = 256; //可根据实际调整 //顺序栈的类型定义 struct SqStack { ElemType elem [ MAXSIZE ]; int top; }; （2）顺序栈的基本形态 （2）顺序栈的基本形态 ① 栈空 条件：S.top==0 不能出栈，不能取栈顶元素 ② 栈满 条件：S.top==MAXSIZE 不能入栈 ③ 栈非空（非满） （3）顺序栈基本操作的实现 构造空栈S Status InitStack ( SqStack S ) { S.top = 0; return OK; } （3）顺序栈基本操作的实现 判断栈是否为空 Status StackEmpty ( SqStack S ) { return (S.top==0); } 栈的长度 int StackLength ( SqStack S ) { return S.top; } （3）顺序栈基本操作的实现 入栈 Status Push ( SqStack S, ElemType e ) { //若栈满则返回错误 if ( S.top==MAXSIZE ) return ERROR; //否则在栈顶插入元素e S.elem[S.top] = e; S.top++; //新的栈顶 return OK; } （3）顺序栈基本操作的实现 出栈 Status Pop ( SqStack S, ElemType e ) { //若栈空则返回错误 if ( S.top==0 ) return ERROR; //删除栈顶元素 e = S.elem[S.top-1]; //取出栈顶元素 S.top--; //新的栈顶 return OK; } （3）顺序栈基本操作的实现 取栈顶元素 Status GetTop ( SqStack S, ElemType e ) { //若栈空则返回错误 if ( S.top==0 ) return ERROR; //取出栈顶元素 e = S.elem[S.top-1]; return OK; } （4）顺序栈与顺序表 利用顺序表可以实现顺序栈。 typedef SqList SqStack; 构造空栈 Status InitStack ( SqStack S ) { return InitList(S); } （4）顺序栈与顺序表 入栈 Status Push ( SqStack S, ElemType e ) { return ListInsert(S, ListLength(S)+1, e); } 出栈 Status Pop ( SqStack S, ElemType e ) { return ListDelete(S, ListLength(S), e); } （4）顺序栈与顺序表 取栈顶元素 Status GetTop ( SqStack S, ElemType e ) { return GetElem(S, ListLength(S), e); } 3.栈的顺序存储结构——顺序栈 总结： 应将顺序表的表尾作为栈顶。 所有操作(除了遍历)的时间复杂度都是：O(1)。 4.栈的链式