第2章之栈和队列.ppt

第2章之栈与队列 西安交通大学计教中心 ctec.xjtu.edu.cn 要点 栈和队列结构的特点 逻辑结构和物理结构的特点 操作的特点 栈的定义 堆栈(Stack) 栈是允许在同一端进行插入和删除操作的特殊线性表。 允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动； 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表（LIFO）。 栈有关概念 栈上溢 栈空间是有限的，若栈已满，在进行入栈操作时，就要产生上溢。 栈下溢 若栈空，再要执行出栈操作，则会发生下溢。 栈顶指针 在栈操作过程中，有一个专门的栈指针（习惯上称它为TOP），指出栈顶元素所在的位置。 栈的顺序存储结构 同顺序表一样，可利用一维数组来实现。 C++语言定义如下： struct SqStack{ ElemType *data; //存储元素的数组 int top; //栈顶指针，存储栈顶元素下标 int stacksize; //最大可用空间数量 }; SeqStack s; //定义一个堆栈s 栈操作举例 例 有三个元素的进栈序列是1，2，3。写出可能的出栈序列。 栈的基本运算 InitStack（Stack） 置栈为空； Empty（Stack） 判定栈是否为空； Push（Stack，x） 进栈操作，在栈顶插入元素； Pop（Stack） 出栈操作，删除栈顶元素； Gettop（Stack） 取栈顶元素 （1）顺序栈初始化 栈的初始化主要是为存储元素的数组申请空间（长度为size）。 void InitStack(SqStack *s, int size) { if( size 0 ) { s-stacksize = size; s-top = -1; s-data = new ElemType[size]; // 申请空间 } else cout堆栈初始化长度错误; } （2）进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。 算法步骤: step1 判别栈满否，若满，则显示栈溢出信息，停止执行；否则，执行step 2； Step2 栈顶指针top上移(加1)； Step3 在top所指的位置插入元素x。 进栈程序算法 void Push(SqStack *s, ElemType x) { if(s-top s-stacksize-1) //是否为空 { s-top++; //Top加 1 s-data[top]=x; //x进栈 } else cout“栈满”; } （3）出栈操作 若栈不空，则删除s的栈顶元素，用e返回其值。 算法步骤: step1 判别栈是否为空；若空，则输出 栈下溢信息，并停止执行；否则， 执行step2； step2 弹出（删除）栈顶元素； step3 栈顶指针top下移(减1)。 出栈算法程序 void Pop (SqStack *s, ElemType e) { if(s-top -1) { e= s-data[s-top]; s-top--; } else cout“栈空”; } （4）取栈顶元素 若栈不空，则用e返回s的栈顶元素。 void GetTop(SqStack *s, ElemType e) { if(s-top -1) //若栈非空 e= s-data[s-top]; //取栈顶元素 else cout“栈空”; } 多栈共享问题 多栈共享是充分利用栈空间的一种策略。具体作法是： 对两栈共享情况来说，将两个栈底分别设在两端，两个栈顶指针top1和top2相对中间位置动态移动，两个栈之间的分界线是不定的。 栈的链式存储结构 由前面介绍的链表结构可知，链结构操作灵活。对栈结构也是一样的。 顺序栈最多可用于2个栈的共享，对于更多的栈就难于表达了。 对于最大空间需要量事先不知的情况，就不能使用顺序栈了。这时，就需要采用链栈。 链栈存储结构 栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的