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

3.3 栈 栈：一种操作受限的线性表，仅允许在表的 一端进行插入或删除。进行插入或删除操作 的一端称为栈顶，位于栈顶位置的元素称为 栈顶元素；相应地，将表的另一端称为栈底， 位于栈底位置的元素为栈底元素。 栈的特性 1.先进后出、后进先出 赵六 王五 李四 张三 栈顶 栈底 最后入栈的“赵六”最先出栈，最先入栈的“张三”最后出栈 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 空栈 top=-1 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栈的入栈过程 Python代码实现如下： top=top+1 #top=0 st[top]=“A” #字母A入栈 top=top+1 #top=1 st[top]=“B