高中信息技术浙教版选修1 算法与程序设计2队列和栈专题复习课件

队列和栈复习 队列和栈复习 一、队列的概念及特性 ★ 概念：一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 ★ 特性：〠先进先出、后进后出 〠有限序列性——队列是一种线性表结构，元素个数有限。队列可以为空。 二、栈的概念及特性 ★ 概念：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。 ★ 特性：〠先进后出、后进先出 〠有限序列性——栈是一种线性表结构，元素个数有限。栈可以为空。 队列特性（单向队列） 栈特性 ①队列长度:tail-head ①栈的长度:top+1 ②空队列判断:if tail==head (只有非空队列，才能出栈取数) ②非空栈的判断:if top！=-1 (只有非空栈，才能出栈取数) ③入队:q[tail]=值， tail=tail+1 ③入栈:top=top+1，stack[top]=值 ④出队:取q[head]， head=head+1 ④出栈:取stack[top]，top=top-1 ⑤队列切片:q[head:tail]表示队列内所有元素 ⑤栈切片:st[:top+1]表示栈内所有元素 ⑥满队列判断:if tail==n： ⑥满栈的判断:if top==n-1： 重难点2 循环队列 对于队列的操作,由于多次出队、入队操作后,就会出现tail指针已经指向了队列最后一个位置,这样队尾无法继续进行入队操作,而head指针前又存在空余部分,这种现象叫作队列"假溢出",如下图所示: 解决"假溢出"的办法,可在队满时,就再从数组的前部继续入队,形成头尾相接的结构。我们把队列的这种头尾相接的顺序存储结构称为循环队列,如下图所示。 三、循环队列 头啊 付月月 章鼎昊 李帅 宋炜涛 陈悦 head=0 tail=6 head=6 定义的列表是否为空？是否能入队？ 循环队列： 将队列的队首和队尾连接起来，形成逻辑上的环状结构。 当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。 尝试设计 循环队列各种状态的判断： 利用队首和队尾(队首索引为head,队尾为tail,队列最大长度为n)指针位置判定循环队列状态: 队列为空:head=tail 队列为满:(tail+1)%n=head 队列长度:(tail-head+n)%n 入队:tail=(tail+1)%n 入队x个:tail=(tail+x)%n 出队:head=(head+1)%n 出队y:head=(head+y)%n 二、队列和栈的基本操作 存储 建队 入队 出队 存储 建栈 入栈 出栈 存储 ★ 队列的存储结构：顺序结构存储（线性表结构），可以用数组来实现，也可用链表来实现。 〄 头指针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 “亚洲足球崛起” ：