(
课件网) 队列和栈复习 浙教版新教材(2019)《数据与数据结构》选择性必修1———3.2+3.3 队列和栈复习 一、队列的概念及特性 ★ 概念：一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 ★ 特性： 先进先出、后进后出 有限序列性———队列是一种线性表结构，元素个数有限。队列可以为空。 一、栈的概念及特性 ★ 概念：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。 ★ 特性： 先进后出、后进先出 有限序列性———栈是一种线性表结构，元素个数有限。栈可以为空。 课 堂 练 习 1.下列事件执行过程与队列特征不相符的是（ ） A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 C 课 堂 练 习 2.下列事件操作的原理与栈的特征不相符的是（ ） A.杂技演员表演叠罗汉时，最后上去的人总是第一个下来 B.在word、photoshop等文档或图像编辑软件中，执行“撤———操作 C.在火车站排队买票或者在超市排队购票 D.多个函数嵌套调用时，按照“后调用先返回”的原则进行 C 课 堂 练 习 3.设栈s的初始状态为空，元素a,b,c,d,e,f,g,依次入栈，入栈和出栈可以交替进行，且7个元素的出栈顺序为b,d,c,f,e,a,g,则栈s的容量至少应该为（ ） A.1 B.2 C.3 D.4 C 二、栈和队列的基本操作 存储 建队 入队 出队 存储 建栈 入栈 出栈 存储 ★ 队列的存储结构：顺序结构存储（线性表结构），可以用数组来实现，也可用链表来实现。 头指针head: 记录队首元素位置 尾指针tail: 记录队尾元素的下一个位置 初始时为空列表时，head和tail 均记录下标为0的位置 ★ 栈的存储结构：顺序结构存储（线性表结构），可以用数组来实现。 栈顶指针top: 记录当前栈顶元素位置 初始时为空栈时，top值为-1 存储 建队 建队1： head=0 tail=0 que=[""]*6 建栈1： top=-1 stack=[""]*6 建栈 建队2： head=0 tail=0 que=[0]*6 建队3： head=0 tail=0 que=[] 建栈2： top=-1 stack=[0]*6 建栈3： top=-1 stack=[] #入队1 for i in “亚洲足球崛起”： que[tail]=i tail+=1 #入栈1： for i in “亚洲足球崛起” ： top+=1 stack[top]=i 入队 入栈 #入队2 for i in range(1,20,3)： que[tail]=i tail+=1 #入队3 for i in range(1,20,3)： que.append(i) #入栈2： for i in range(1,20,3) ： top+=1 stack[top]=i #入栈3： for i in “亚洲足球崛起” ： stack.append(i) #出队1、2 while head!=tail: print(que[head]) head+=1 #出栈1、2： while top>-1: print(stack[top]) top-=1 出队 出栈 #出队3 head=0 while len(que)!=0: print(que.pop(head)) head+=1 #出栈3： while len(stack)!=0: print(stack.pop()) top!=-1 #建队 head=tail=0 que=[""]*6 #入队 for i in “中国男足加油”： que[tail]=i tail+=1 #出队 while head!=tail: print(que[head]) head+=1 Print(que) #建栈： top=-1 stack=[""]*6 #入栈： for i in “中国男足加油” ： top+=1 stack[top]=i #出栈： while top>-1: print(stack[top]) top-=1 Print(stack) 测试1 VS #建队 head=tail=0 que=[] #入队 for i in “伊朗真真不错": que.append(i) #出队 tail=len(que) while len(que)!=0: print(que.pop(head)) print(que) #建栈： top=-1 stack=[] #入栈： for i in ... ...
