(
课件网) 选择性必修1《数据与数据结构》 第三章 字符串、队列和栈 3.3 栈的概念、特性及基本操作 情境导入 消毒桶的餐盘 知识讲解 1.栈的概念【一种受限的线性表，仅允许在一端插入或删除】 栈顶： 栈底： 李岚 张栋 陈思思 刘力源 栈顶： 栈底： 允许插入或删除的一端 表的另一端 2.栈的特性 李览 张栋 陈思思 刘力源 栈顶： 栈底： （1）先进后出、后进先出 最后入栈的栈顶元素“李览”最先出栈； 最先入栈的栈底元素“刘力源”最后出栈。 （2）有限序列性 栈可以为空，也可以包含多个元素。 栈中元素存在线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点。 其他元素既有一个前驱又有一个后继。 ？ 问题与讨论 栈与队列有什么相同点和不同点？ 不同点 相同点 栈 先进后出、后进先出； 只允许在一端进行操作 一种受限制的线性表 只允许在端点操作 队列 先进先出、后进后出； 出队（队首）、入队（队尾） 3.3.2 栈的基本操作 栈可用数组实现的原因———按顺序结构存储 C B A 栈顶：top=2 栈底 A B C 数组st 0 1 2 ①图为栈结构 ②图为用数组st存储该栈 当top=0时，st[top]存储栈底元素“A” top=1时，st[top]存储栈中第2个元素“B” top=2时，st[top]存储栈顶元素“C” 栈顶元素有一个前驱点，栈底元素有一个后继点 使用top变量来记录栈顶元素【在数组中的位置———栈顶元素的位置会变】 拓展链接 栈的链式存储结构 利用链式存储方式实现的栈称为链栈。它可以用单链表的方式实现。如图3.3.3所示，栈顶指针top为链栈的头指针。链栈的优点在于它克服了用数组实现的顺序栈空间利用率不高的缺点,但是要为每个栈元素分配额外的指针空间。 D C B A ^ top 栈的基本操作 入栈 建栈 知识讲解 1.建栈 在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。例如，要使4个字母“A”“B”“C”“D’按序人栈、出栈,可以建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为-1。 Python 代码实现如下: top=-1 st=[“ ”]*4 建队与建栈的区别？ 2.入栈、出栈 入栈又叫压栈操作，把数据元素压人栈顶。每次入栈时，栈顶指针变量top值加1,再给st[top]赋值。字母“A”“B”“C”“D”按序入栈的过程如图3.3.4所示。 A top=0 top=1 C B A B A top=3 D C B A top=2 图3.3.4 st栈中的入栈过程 top=1 C B A B A top=3 D C B A top=2 Python代码实现如下： top=top+1 #top=0 st[top]="A" #字母A入栈 top=top+1 #top=1 st[top]="B" #字母B入栈 top=top+1 #top=2 st[top]="C" #字母C入栈 top=top+1 #top=3 st[top]="D" #字母D入栈 A top=0 问题与讨论 编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问:开出火车站的顺序有多少种 请写出所有可能的出栈序列。 出栈顺序：1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 共14种出栈方式 Python程序编写：十进制n转二进制 n=int(input("请输入任意十进制数n：")) number=n s="" while n!=0: r=n%2 s=str(r)+s n=n//2 print("十进制数%d的二进制数是:%s"%(number,s)) 输出格式要求 对于第一章项目挑战中的“用户角色特征值”转换成二进制，可以采用“除二取余法”，并利用栈结构存储每次转换过程中得到的余数。 以特征值6为例，转成二进制的过程如图3.3.5所示。 除二取余数的过程中: 特征值的变化为6→3→1→0; 每一步得到的余数为0→1→1; 按序人栈，当特征值变为0时，依次取出栈中元素，得到对应的二进制数“110”。 【变量意义】 栈st:每次得到的余数， number:特征值， top:栈顶位置。 “除二取余数” 的入栈和出栈过程 0 top=0 top=1 1 ... ...
