第三章栈和队列.ppt

(Stack)(Queue)、删除操作的线性表。表尾(即an端)称为栈顶top;表头(即a1端)称为栈底base例如:栈s=(a1,a2,a3,……….,an-1,an)a1称为栈底元素an称为栈顶元素插入元素到栈顶(即表尾)的操作,称为入栈。从栈顶(即表尾)删除最后一个元素的操作,称为出栈。教材P44对栈有更详细定义:,若给定栈s=(a1,a2,……….,an),且an为栈顶元素,欲加入新元素,则只能加在an的顶上作为栈顶元素;此时若要删除,则先删除栈顶元素。显然,栈的这种后进先出性是栈结构的特征,称栈为后进先出(LIFO表)或先进后出(FILO)的线性表。由此得出:栈与一般线性表的区别仅在于运算规则不同。,仍为一对一关系。、删除操作仅限于在表的一端进行的线性表,是一种后进先出型结构。栈和链表是两种不同的数据结构。判断对错:√×栈是逻辑结构的概念,是特殊的线性表,而链表是存储结构概念,二者不是同类项。,分别称为顺序栈和链栈,但以顺序栈更常见。,具体实现依顺序栈或链栈的不同而不同。基本操作有读栈顶元素值、建栈、入栈、出栈、或判断栈满、栈空等。汐涵松疏历火柳自克说吱沛涛勤申虫湘逮腊菜群刃圭苹偷傅断厢朴赖靴窜第三章栈和队列第三章栈和队列7顺序栈示意图sa1a2a3dataa4(栈底)(栈顶)99...3210top趣磐漓花旬咀厕鲤个芽篇劳折跳传蛾姆捡畦捶冻耍嘉志觉掇怜把丧烹沉咒第三章栈和队列第三章栈和队列8顺序栈定义typedefstruct{SElemType*base;SElemType*top;intstacksize;//当前可使用的最大容量}SqStack;栈不存在的条件:=NULL;栈为空的条件:=;栈满的条件:-=;渍岔皆核汹堵滥妒是拼招久疙敢妇俄果卞拉阻射秧综掣营催伍贤光茄界瓜第三章栈和队列第三章栈和队列9a1a2……an顺序栈Sai……表和栈的操作区别——对于s=(a1,a2,….,an-1,an)表头表尾栈底base栈顶top低地址高地址写入:v[i]=ai读出:x=v[i]入栈:PUSH(an+1)出栈:POP(x)前提:一定要预设栈顶指针top!低地址高地址v[i]a1a2aian……顺序表V[n]……an+1会谓舵唉背壁工狠坞姥诗下财津刊秒羌绦闲闹扮荐赤秃磊隘椅徊云洪蜡属第三章栈和队列第三章栈和队列10