栈和队列61资料教程.ppt

(Stack)是限定仅在表的一端(一般指表尾)进行插入和删除操作的线性表。允许插入、删除的这一端称为栈顶(Top),另一端称为栈底(Bottom)。栈的插入操作通常称为入栈或进栈(push),而栈的删除操作则称为出栈或退栈(pop)。=(a0,a1,a2,…an-1),则a0称为栈底元素,an-1称为栈顶元素。栈中元素按a0,a1,a2,…an-1的次序入栈,出栈的第一个元素应为栈顶元素an-1。也就是说,栈的操作是按后进先出的原则进行的。因此,栈又称为后进先出(LastInFirstOut)的线性表(简称LIFO表)。入栈出栈栈底栈顶an-1···:⑴InitStack(s):栈初始化。初始条件:栈s不存在操作结果:构造了一个空栈。⑵StackEmpty(s):判栈空。初始条件:栈s已存在操作结果:若s为空栈则返回1,否则返回0。⑶Push(s,e):入栈。初始条件:栈s已存在操作结果:在栈s的顶部插入一个新元素e,e成为新的栈顶元素。栈发生变化。栈是一种特殊的线性表,因此栈也可采用两种存储结构: (1)顺序栈的存储结构顺序栈是指采用顺序存储结构存储的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针(下标)top,指示栈顶元素的当前位置。对于用C语言描述的顺序栈通常用top=-1表示空栈;入栈时,栈顶指针top增1;出栈时,栈顶指针top减1。:#defineMAXSIZE100typedefintElemType;typedefstructstack{ ElemTypeelem[MAXSIZE];//存栈顺序表inttop; //栈顶下标}SQSTACK;(2)顺序栈的基本操作①栈的初始化(即构造一个空栈)voidInitStack(SQSTACK*ps){ps->top=-1;}②判栈空intStackEmpty(SQSTACKs){if(==-1)return1;elsereturn0;}③入栈intPush(SQSTACK*ps,ElemTypee){if(ps->top==MAXSIZE-1)//判栈满{cout<<"Stackisfull“<<endl;return1;}ps->top++;ps->elem[ps->top]=e;return0;}