数据结构-第三章-栈和队列.ppt

文档介绍：(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。栈是限定仅能在表尾一端进行插入、删除操作的线性表(a1,a2,...,ai-1,ai,ai+1,…,an)插入删除什么是栈一、栈的定义进行插入和删除的一端是浮动端,通常被称为栈顶,并用一个“栈顶指针”指示;而另一端是固定端,通常被称为栈底。通常将栈用下图的形式描述:1)限定在线性表的一端进行插入。2)限定在线性表的一端进行删除。3)后进先出(LastInFirstOut),简称为LIFO线性表。第一个进栈的元素在栈底,最后一个进栈的元素在栈顶,第一个出栈的元素为栈顶元素,最后一个出栈的元素为栈底元素。不含元素的栈称为空栈。出栈Pop进栈Push栈顶栈底topbottom空栈topbottoman...a2a1bottomtopbottomtopAABCDEAB栈操作图示A进栈BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO入栈与出栈topbottomtopbottomtoptoptop栈的表示和实现顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指向栈顶元素在顺序栈中的下一个位置, base为栈底指针,指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop思考:假设有A,B,C三个元素进S栈的顺序是A,B,C,写出所有可能的出栈序列。ABBACBCA如果是4个元素,那么它不可能的出栈序列有哪些?可能的出栈序列:12431324134221342143231424313241321434214321不可能出现的出栈序列:2413312434124123423142134312