数据结构与算法：栈.pptx

栈; 3 栈; 3 栈;2. 栈的顺序存储与运算 栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。 ◆ 静态顺序栈实现简单，但不能根据需要增大栈的存储空间； ◆ 动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。 ; 采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。 ◆ 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。 ◆ 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。 ◆ 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;;◆ 结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。 下图是一个动态栈的变化示意图。;设栈s的初始状态为空，元素a,b,c,d,e,f,g 分别入栈，下列出栈序列不可能的是( ) a,b,c,d,e,f ,g b,c,a,f,e,g,d a,e,d,c,b,f,