数据结构基础知识06--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（六） 【知识要点】 数据结构-----------队列 队列（queue）是一种先进先出的（First In First Out）的线性表，简称FIFO。队列允许在一端进行插入操作，而在另一端进行删除操作。允许插入的一端为队尾tail，允许删除的一端为队头head。队列不允许在中间部位进行操作，故其操作是受限的。队列只规定了插入和删除的方式，但并未规定其存储结构，所以队列既可以用数组实现，又可以用链表实现。例图1 #1.创建队列 head = 0   #队首指针 tail = 0   #队尾指针 que = ['']*4   #存储空间（数组方式） #2.入队 que[tail] = 'a'   #从队尾入队 tail += 1       #队尾后移 que[tail] = 'b'   #从队尾入队 tail += 1       #队尾后移 que[tail] = 'c'   #从队尾入队 tail += 1       #队尾后移 que[tail] = 'd'   #从队尾入队 tail += 1       #队尾后移 #3.出队 if head<tail:     print(que[head])   #输出队首内容，出队     head += 1        #队首后移 #4.循环队列以及假溢出问题 #根据上面的操作，我们发现此时tail=4,已经无法在插入数据，但实际上que[0]的数据已经出队，存储空间可用，这种情况便称之为“假溢出”。 #对于存储空间有限的情况，可以使用循环队列增加存储空间的利用率。 #循环队列入队 if tail-head<4:     que[tail%4] = 'e'  #通过取模运算实现存储空间复用     tail += 1          #队尾的数值继续累加 else:     print("存储空间已满，等待出队中") #注意：此时tail的值已经超出索引范围，但只要保证头尾之前的存储空间不超过数组范围，就可以用取模的方式实现空间复用而不会覆盖未出队的数据。 #python自带的队列模块 import queue q = queue.Queue(10)   #生成一个存储空间为10的队列q q.put("A")       #入队 q.put("B")       #入队 print(q.qsize())     #输出队列中的元素的个数 print(q.get())       #队首元素出队，出队的元素为'A' print(q.qsize())    #输出队列中的元素的个数 print(q.empty())     #判断队列是否为空,空则返回True,否则返回False print(q.full())     #判断队列是否为满,满则返回True,否则返回False 数据结构-----------栈 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的先入后出（FILO）特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底top，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针，栈也只规定了插入和删除的方式，但并未规定其存储结构，所以栈也可以用数组或链表实现。 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 #1.创建栈 top = -1     #栈顶 st = ['']*4   #栈空间 #2.入栈 top += 1 st[top] = 'a' top += 1 st[top] = 'b' top += 1 st[top] = 'c' top += 1 st[top] = 'd' #3.出栈 if top>-1:     print(st[top]) top -= 1 #补充案例：逆波兰式 def compValues(postorde_exp):     operators = "+-*/"     st = []     exp_list = postorde_exp.split()     print(exp_list)     for x in exp_list:         if x not in operators:             st.append(x)         else:             b = st.pop()             a = st.pop()             c = eval(a + x + b)     #注意转换方式