初学者的每日学习笔记 2020.12.2
队列
队列的定义
为什么要用队列：
你们在用电脑时有没有经历，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算rest时。突然他像酒醒了一样，把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。
再比如向移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客户人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前打客服电话的客户进行排队处理。
操作系统和客服系统中，都是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First in First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
假设队列是q=（a1,a2,…,an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然在队伍的最后。
队列在设计程序中用的非常频繁。比如用键盘进行各种字母或数字的输入，到显示器如记事本软件上的输出，其实就是对列的典型应用，假如你本来和女友聊天，想表达你是我的上帝，输入的是god，而屏幕上却显示出了dog发了出去，这真是要气死人了。
队列的概念：
栈和队列
是一对好兄弟，前面我们介绍过
数据结构与算法—栈详解
，那么栈的机制相对简单，后入先出，就像进入一个狭小的山洞，山洞只有一个出口，只能后进先出(在外面的先出去)。而队列就好比是一个隧道，后面的人跟着前面走，前面人先出去(先入先出)。日常的
排队
就是队列运转形式的一个描述！
所以队列的
核心理念
就是：先进先出！
队列的概念：
队列是一种特殊的
线性表
，特殊之处在于它只允许在表的
前端（front）
进行删除操作，而在表的
后端（rear）
进行插入操作，和栈一样，队列是一种
操作受限制
的线性表。进行插入操作的端称为
队尾
，进行删除操作的端称为
队头
。
队头front：
删除数据的一端。对于数组，
从后面插入更容易，前面插入较困难
，所以一般用数组实现的队列队头在前面。(删除，直接index游标前进，不超过队尾即可)。而对于链表。插入删除在
两头分别进行
那么
头部(前面)删除尾部插入
是最方便的选择。
队尾rear：
插入数据的一端，同上，在数组和链表中
通常均在尾部位置
。当然，其实数组和链表的front和rear还有点小区别，后面会具体介绍。
enQueue(入队)：在
队尾
rear插入元素
deQueue(出队)：在
对头
front删除元素
普通队列
按照上述的介绍，我们很容易知道数组实现的方式。用
数组模拟
表示队列。要考虑初始化，插入，问题。
- 初始化：数组的front和rear都指向0.
-
入队：
队不满
，
数组不越界
，先队尾位置传值，再队尾下标+1 - 出队：队不空，先取队头位置元素，在队头+1，
但是很容易发现问题，
每个空间域只能利用一次
。造成
空间
极度
浪费
。并且非常容易
越界
！
循环队列
针对上述的问题。有个较好的解决方法！就是对已经申请的(数组)内存
重复利用
。这就是我们所说的循环队列。
而数组实现的循环队列就是在
逻辑上
稍作修改。我们
假设
(约定)数组的最后一位的下一个index是首位。因为我们队列中只需要front和tail两个指标。不需要数组的实际地址位置相关数据。和它无关。所以我们就只需要考虑尾部的特殊操作即可。
- 初始化：数组的front和rear都指向0.
-
入队：
队
不满，先队尾位置传值，再
rear=(rear + 1) % maxsize;
-
出队：队不空，先取队头位置元素，
front=(front + 1)%maxsize;
-
是否为空：
return rear == front;
-
大小：
return (rear+maxsize-front)%maxsize;
这里面有几个大家需要注意的，就是指标相加如果遇到最后需要转到头的话。可以判断是否到数组末尾位置。也可以直接+1求余。其中
maxsize
是数组实际大小。
一、 队列的实现 Python
队列的定义：
def __init__(self,size = 100):
self.queue = [0 for _ in range(size)] #限定队列的大小
self.rear = 0 #队尾
self.front = 0 #队首
self.size = size
1.1 入队操作
算法：
步骤一：判断是否溢出，若溢出给出提示结束程序，否则跳到步骤二
步骤二：输入入队的元素
步骤三：将元素存于队尾处
步骤四：队尾下标自增
//入队操作
def push(self,element):
if not self.is_filled():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is filled")
1.2 出队操作
算法：
步骤一：判断是有元素，若无元素则给出提示结束程序，否则跳到步骤二
步骤二：用e接收出队的元素
步骤三：
步骤四：队尾下标自增
//出队操作
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty.")
1.3 判断队空
rear == front
def is_empty(self):
return self.rear == self.front
1.4判断队满
（rear+1)%size == front
def is_filled(self):
return (self.rear+1)%self.size == self.front
二、 Python中的内置队列模块
这里有个很容易搞混的：
import queue 只是为了保证线程安全
真正的队列模块是：
from collections import deque
它内部是一个双向队列。
from collections import deque
q = deque([1,2,3,4,5],5) #后面的5限制队列的大小，如果队满，就自动把队首的出去
q.append() #从队尾进队，即右边进队
q.popleft() #从队首出队，即左边出队
#前面这属于单向队列
q.appendleft() #从队首进队，即左边进队
q.pop() #从队尾出队，即右边出队
引用和参考：
数据结构-队列 – Timcode – 博客园www.cnblogs.com
数据结构与算法-队列图文详解 – bigsai – 博客园www.cnblogs.com
