3.3栈 课件-2022-2023学年浙教版（2019）高中信息技术选修1

3.3栈 选修1《数据与数据结构》 栈的概念和特性 栈：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。 HUAWEI (H) - HUAWEI (H) - 栈的概念和特性 1.先进后出、后进先出 D C B A 栈顶 栈底 最后入栈的"D"最先出栈，最先入栈的"A"最后出栈 弹匣的装弹过程（入栈） 栈的概念和特性 2.有限序列性 栈可以是空的，也可以包含多个元素。 栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素 有一个后继点，其他元素既有一个前驱点，又有一个后继点。 栈的概念和特性 【思考】栈与队列有什么相同点和不同点？ 数据结构 队列 栈 相同点 都是一种操作受限的线性表，都具有有限序列性的特点。 不同点 两端开放：队尾入队，队首出队 先进先出 一端开放：栈顶入栈出栈 先进后出 栈的基本操作 栈，一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中 的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位 置。如下图所示，①图为栈结构，②图为用数组st存储该栈。 C B A 栈顶：top=2 栈底： A B C 数组st 0 1 2 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"按序入栈的过程如下图所示。 0 1 2 3 空栈 A B A C B A D C B A top 0 1 2 3 top 1 0 2 3 top 2 0 1 3 top 3 0 1 2 满栈 ④ ② ③ ① ⑤ st栈的入栈过程 top = -1 st = [""] * 4 top +=1 st[top] = "B" top +=1 st[top] = "A" top +=1 st[top] = "C" top +=1 st[top] = "D" top -1 栈的基本操作 Python代码实现如下： top=-1 st=[""]*4 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入栈 top=-1 st=[""]*4 s=["A","B","C","D"] for i in s:#所有字母依次入栈 __________ __________ top=top+1 st[top]=i 栈的基本操作 3.出栈 出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时， 即top=-1，不能进行出栈操作。 D C B A 1 top 3 0 2 满栈 ④ ② ③ ① ⑤ C B A top 2 0 3 1 print(st[top]) top-=1 B A top 1 0 2 3 print(st[top]) top-=1 A top 0 1 2 3 print(st[top]) top-=1 print(st[top]) top-=1 0 1 2 3 空栈 top -1 栈的基本操作 Python代码实现如下： st=["A","B","C","D"] top=3 print(st[top])#字母D出栈 top-=1 #top=2 print(st[top])#字母C出栈 top-=1 #top=1 print(