1、去银行、医院办理业务时，取号机能 按照到达时间的先后顺序，合理地安 排办事次序。这些事件对数据的处理都具有排队的 特性，可以使用队列来解决。队列的概念与特性 一、队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个 元素称为出队。n1 n2 n3 n4 nn 队尾元素 队首元素 入队 出队 图1 二、队列的特性（1）先进先出、后进后出 由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图1所示，出队时，队首元素n1优先出队，紧接着是n2,n3,nn，队尾元素nn最后出队。（2
2、）有限序列性 队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含 多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素 只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。队列的基本操作 队列一般按顺序结构存储，可以用数组来实现。如下图所示，数组que中存储了一个 队列、共有4个元素，队首元素为a1，队尾元素为a4。由于在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾 指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。a1 a2 a3 a4 0 1 2 3 队列的存储
3、 a1 a2 a3 a4 0 1 2 3 4 0 1 2 3 4 tail head 数组que的下标 head tail 队列的head、tail指针变化图 对于下图所示的队列，初始时，head指针变量与tail指针变量均记录下标为 0的位置。元素a1、a2、a3、a4依次入队后，tail值为4,head值为0。当a1、a2出队后，head记录下标为2的位置，tail值不变。当a3、a4出队后，head与tai的值均为4，队列为空。队列的常用操作有建队、入队、出队等。1.建队 由于队列以数组形式存储，因此python中用列表创建队列。例如，有4个字母“A”“B”“C”“D”按序入队、出队时，
4、可以创建一个队列que，长度为5，python代码如下所示：head=0 tail=0 que=“”*5 2.入队、出队 字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪 各元素入队。如下图所示：A01tail AB01tail ABC0123tail ABCD01234tail（1）（2）（3）（4）入队的Python代码如下：quetail=“A”#字母A入队 tail=tail+1#tail=1 quetail=“B”#字母B入队 tail=tail+1#tail=2 quetail=“C”#字母C入队 tail=tail+1#tail=3 quetail=
5、“D”#字母D入队 tail=tail+1#tail=4 出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。拓展链接：循环队列 循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列 中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有 位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。E 0 1 2 3 4 下标 head tail tail超出队列的边界 如上图所示，某队列分配的最大空间为5，其最后一个位置上的元素为“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超
6、出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。将队列改为循环队列，则在元素“E”入队后，head的值为4，队尾 指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入 到队首，然后tail的值变为1。如下图所示。0 1 2 3 4 Ehead tail“E”入队 0 1 2 3 4 head tail E F“F”入队 循环队列 队列模块queue 在python中有自带的队列模块queue，方法如下。代码 说明 import queue 导入队列模块 q=queue.Queue(5)建立一个长度为5的队列q q.put(1)将数字1入队 q.qsize()输出队
7、列中元素的个数 q.get()队首元素出队 队列的应用 例：信息的加密 给定一个字符串S1，S2，Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3SnS2；接着把S3取出，S4放到字符串的末尾S2后面直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。加密的过程，类似队列的入队、出队操作。先把原字符串中各字符 依次入队，得到一个队列，再执行加密的过程：取出队首元素，存 到密串中，队列中第二个元素升级为队首元素；再取出队首元素，并把该元素插入队
8、尾。反复操作，直至队列为空，得到密串。以字符串“STRING”为例，算法步骤如下：创建que队列，把字符串“STRING”按序压入队列，tail值为6，head值为0。加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。重复操作，直至队列为空。前两个字母的出队、入队过程如下图所示：队列 que T R I N G 0 1 2 3 4 5 6 7 head tail“S”出队 队列 que R I N G 1 2 3 4 5 6 7“T”出队 head tail 队列 que R I
9、 N G T 0 1 2 3 4 5 6 7 head tail“T”入队 用python 实现的完整程序及测试结果：s=input(“请输入字符串：”)print(“加密后的串为：”)que=“”*100 head=0 tail=0 for i in range(len(s):#把原串全部压入队列 quetail=si tail+=1 While headtail:#队列非空时 print(quehead,end=“”)head+=1 if headtail:#队列非空时，出队的元素加入队尾 quetail=quehead tail+=1 head+=1 请输入字符串：Python 加密后的
10、串为：Ptoynh 练一练 1.依次在初始为空的队列中将元素“h”，“e”，“l”，“l”，“o”入队以后，紧接着做了两次删除操作，此时的队首元素是：A.“h”B.“e”C.“l”D.“o”C 2.有如下python 程序段，使用长度为3的列表q模拟队列的出队 入队活动：q=1,2,3 ys=for i in range(4,10):ys.append(q0)q0=q1 q1=q2 q2=i print(ys,q)程序运行结束后，列表ys中元素的数量为_。6 3.有如下python程序段：from queue import Queue q=Queue(5)print(“能存放的最多元素个数=”,q.maxsize)for i in range(q.maxsize):q.put(3*i)print(“是否满：”,q.full()for i in range(q.qsize():print(“当前实际长度=”,q.qsize()print(“取出元素：”,q.get()从队列中取出的元素依次是_。0,3,6,9,12 谢 谢