严蔚敏版数据结构第三章.ppt

(Stack)(Queue),仍为一对一关系。用顺序栈或链栈存储均可,但以顺序栈更常见只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。(只能在栈顶操作)3问:堆栈是什么?它与一般线性表有什么不同?:堆栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。与一般线性表的区别:仅在于运算规则不同。一般线性表堆栈逻辑结构:一对一逻辑结构:一对一存储结构:顺序表、链表存储结构:顺序栈、链栈运算规则:随机存取运算规则:后进先出(LIFO)“进”=压入=PUSH(x)“出”=弹出=POP(y)4栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶top;表头(即a1端)称为栈底base例如:栈s=(a1,a2,a3,……….,an-1,an)a1称为栈底元素an称为栈顶元素插入元素到栈顶(即表尾)的操作,称为入栈。从栈顶(即表尾)删除最后一个元素的操作,称为出栈。教材P44对栈有更详细定义:强调:插入和删除都只能在表的一端(栈顶)进行!5栈的表示和实现顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指向栈顶元素在顺序栈中的下一个位置, base为栈底指针,指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetop6顺序栈示意图sa1a2a3data(栈底)(栈顶)99...3210top顺序栈的类型表示:#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefcharStackData;typedefstruct{ //顺序栈定义StackData*base;//栈底指针 StackData*top;//栈顶指针 intstacksize;//当前已分配的存储空间}SeqStack;8判栈空intStackEmpty(SeqStack*S){if(S->top==S->base)return1//空则返回1elsereturn0;//否则返回0 }判栈满intStackFull(SeqStack*S){if(S->top-S->base>=S->StackSize)return1//判栈满,满则返回1 elsereturn0;//否则返回0}顺序栈的基本运算:9初始化voidInitStack(SeqStack*S){//置空栈S->base=(StackData*)malloc(STACK_INIT_SIZE* sizeof(StackData));if(!S->base)exit(OVERFLOW);S->top=S->base;S->stacksize=STACK_INIT_SIZE;Returnok;}10