3.3栈 教学课件 浙教版.pptxVIP

3.3栈选修1《数据与数据结构》栈：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。 栈的概念和特性1.先进后出、后进先出DCBA栈顶栈底弹匣的装弹过程（入栈）最后入栈的D最先出栈，最先入栈的A最后出栈 栈的概念和特性2.有限序列性栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。 栈的概念和特性【思考】栈与队列有什么相同点和不同点？数据结构队列栈相同点都是一种操作受限的线性表，都具有有限序列性的特点。不同点两端开放：队尾入队，队首出队先进先出一端开放：栈顶入栈出栈先进后出 栈的概念和特性栈，一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位置。如下图所示，①图为栈结构，②图为用数组st存储该栈。topCBA栈顶：top=2ABC数组st012栈底：②①栈的存储 栈的基本操作1.建栈在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。例如，要使4个字母ABCD按序入栈、出栈，可以建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为-1。Python代码实现如下：top=-1st=[]*4 栈的基本操作2.入栈入栈又叫压栈操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。字母A,B,C,D按序入栈的过程如下图所示。333ABACBADCBA3top 322top 2221top op 0空栈top -1满栈①②③④⑤ top = -1st = [] * 4top +=1st[top] = Atop +=1st[top] = Btop +=1st[top] = Ctop +=1st[top] = Dst栈的入栈过程 栈的基本操作Python代码实现如下：top=-1st=[]*4top=top+1 #top=0st[top]=A #字母A入栈top=top+1 #top=1st[top]=B #字母B入栈top=top+1 #top=2st[top]=C #字母C入栈top=top+1 #top=3st[top]=D #字母D入栈top=-1st=[]*4s=[A,B,C,D]for i in s:#所有字母依次入栈____________________ top=top+1st[top]=i 栈的基本操作3.出栈出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时，即top=-1，不能进行出栈操作。3DCBACBA3top 33ABA32top 22221top op 0满栈空栈top -1①②③④⑤ print(st[top])top-=1print(st[top])top-=1print(st[top])top-=1print(st[top])top-=1 栈的基本操作Python代码实现如下：st=[A,B,C,D]top=3print(st[top])#字母D出栈top-=1 #top=2print(st[top])#字母C出栈top-=1 #top=1print(st[top])#字母B出栈top-=1 #top=0print(st[top])#字母A出栈top-=1 #top=-1st=[A,B,C,D]top=3while __________:#所有字母依次出栈 print(st[top])__________top-1top-=1 栈的基本操作编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问：开出火车站的顺序有多少种？请写出所有可能的出栈序列。进入栈中的元素可停留、可出栈（1）若火车①最先出栈，只能是①进①出，剩下②③④，则有：出入栈方式出栈序列②进②出，③进③出，④进④出①②③④②进②出，③进，④进④出，③出①②④③②进，③进③出，②出，④进④出①③②④②进，③进③出，④进④出，②出①③④②②进，③进，④进④出，③出，②出①④③②先进后出 问题与讨论（2）若火车②最先出栈，只能是①进，②进②出，剩下 ③④，则有：出入栈方式出栈序列①出，③进③出，④进④出②①③④①出，③进，④进④出，③出②①④③③进③出，①出，④进④出②③①④③进③出，④进④出，①出②③④①③进，④进④出，③出，①出②④③① 问题与讨论（3）若火车