(
课件网) 课时3 栈 第三章 字符串、队列和栈 1.通过问题解决，理解栈的概念和特性。2.掌握栈的基本操作，并能编程实现。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.栈的概念 (1)栈也是一种操作受限的线性表，仅允许表的_____进行插入或删除操作。 (2)进行插入或删除操作的一端称为_____，位于栈顶位置的元素称为栈顶元素；表的另一端为_____，位于栈底位置的元素称为栈底元素。 一端 栈顶 栈底 2.栈的特性 (1)_____或_____。 (2)_____。 栈可以是空的，也可以包含多个元素。 3.栈的基本操作 (1)栈的创建 在存储n个元素的栈时，可以用列表创建一个长度为n的栈。 (2)入栈(push)、出栈(pop) 入栈操作：入栈也叫_____操作，把数据元素压入栈顶，每次入栈时，栈顶指针变量top值_____，再给st[top]赋值。 先进后出 后进先出 有限序列性 压栈 加1 出栈操作：出栈时把栈顶元素取出，同时_____。如果栈中没有元素时，即top＝－1，不能进行出栈操作。 top值减1 4.使用列表模拟栈操作 a＝[] #建栈 a.append(″data1″) #入栈 a.append(″data2″) #入栈 a.append(″data3″) #入栈 print(a.pop()) #出栈 print(a.pop()) #出栈 print(a.pop()) #出栈 5.建立stack类并进行栈操作 class Stack()： def_ _init_ _(self)： #建栈 self.my_stack＝[] def push(self，data)： #入栈 self.my_stack.append(data) def pop(self)： #出栈 return self.my_stack.pop() def size(self)： #栈空判断 return len(self.my_stack) def isEmpty(self)： return self.my_stack＝＝[] stack＝Stack() a＝[″data1″，″data2″，″data3″] for item in a： #入栈 stack.push(item) print(″栈中元素个数为：″，stack.size()) while not stack.isEmpty(): #出栈 print(stack.pop()) 例题精析 2 例1 若某栈的容量是 3，即栈内最多只能容纳 3 个元素，若其某个出栈序列是a，b，c，d，e，那么它可能的入栈序列是( ) A.c，b，a，e，d B.d，c，b，a，e C.b，c，a，e，d D.a，e，d，c，b A 解析 A选项c，b，a依次入栈，a，b，c依次出栈，接着e，d入栈后再出栈。B选项a要出栈，d，c，b，a需入栈，栈空间超过3。C选项b先于c入栈，则c需先出栈。D选项a入栈并出栈后，剩余4个元素入栈，超过栈容量。 变式训练 有1个栈初始为空，其元素入栈顺序依次为s，t，r，w，u，y，m，若经过进栈和出栈操作后，栈底至栈顶元素分别为t，w，y，则第3个出栈元素为( ) 解析 根据栈的特性，在栈中元素后进先出，因此第1个入栈和出栈的元素是s，第3个入栈第2个出栈的元素是r，第5个入栈第3个出栈的元素是u。 C A.m B.w C.u D.s 例2 公交车上有时候会出现人太多无法挤到后门下车而从前门下车的情况，因此若一个序列在有3个或以下元素时按队列方式离开序列，但在3个以上元素时按栈方式离开序列，则对于依次进入序列的xl，x2，x3，x4，x5，x6，离开序列的顺序可能为( ) A.x1，x4，x6，x2，x3，x5 B.x4，x1，x6，x2，x3，x5 C.x1，x2，x3，x6，x4，x5 D.x6，x5，x4，x3，x1，x2 解析 A选项x1小于3个元素按队列方式出列，x4进入序列时，还有x2，x3，x4共3个元素，按队列方式出列，也就是x2出列，如果按栈离开，则必须x5进入序列，那就是x5先出。B选项x4按出栈方式离开，剩下x1，x2，x3，因此x1按队列方式离开。当x5、x6进入序列，x6按出栈方式离开。剩下3个按队列方式离开。C选项x1，x2，x3按队列方式离开，则x4，x5，x6进入序列后只能按队列方式离开。D选项x6先离开，全部元素进入序列，前面3个元素按出栈方式离开，后面3个元素只能是按队列方式离开。 B 变式训 ... ...
