数据结构必会｜队列和双端队列（Python）

队列

1. 队列是什么

​ 队列的思想比较贴近于我们的生活，当我们在超市排队结账的时候，其实就是一个队列的实现，也就是先排队的人先结账，后排队的人后结账的思想。

​ 和栈一样，队列也是一个有序的集合，添加操作发生在尾部，移除操作则发生在头部，新元素会从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。

​ 队列的性质规定了最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素排在头部，这种原则被称为FIFO（first-in first-out）

2. 队列的实现

​ 队列的实现方式很简单，我们只要保证元素“从哪进，不从哪出”就可以了，使用列表的方式实现队列我们可以从尾部使用insert()函数插入元素，再使用pop()推出头部的元素。具体的实现方法如下：

class Queue:
    def __init__(self):
        self.items = []
    
    # 判断是否为空队列
    def isEmpty(self):
        return self.items == []

    # 入队列
    def enqueue(self, item):
        self.items.insert(0, item)

    # 出队列
    def dequeue(self):
        return self.items.pop()

    # 队列的长度
    def size(self):
        return len(self.items)

​ 测试结果如下：

# 测试队列
q = Queue()
q.isEmpty()

# 传入元素
q.enqueue('I')
q.enqueue('like')
q.enqueue('python')
q.size()
q.dequeue()

# 输出
'I'

双端队列

1. 双端队列的概念

​ 双端队列相对于之前的数据结构来说更加的自由，双端队列对于在哪一端进行添加和移除元素是没有限制的，也就意味着可以从任意一端进行元素的添加和移除。

​ 双端队列的性质也决定了其具有两种不同的原则：LIFO和FIFO。

2. 双端队列的实现

​ 实现双端队列的时候我们可以把之前用在栈和队列上面的做法结合在一起来实现LIFO和FIFO两种思想。具体的实现方法如下：

class Deque:
    def __init__(self):
        self.items = []

    # 判断是否为空
    def isEmpty(self):
        return self.items == []

    # 从前端插入数据
    def addFront(self, item):
        self.items.append(item)

    # 从尾端插入数据
    def addRear(self, item):
        self.items.insert(0, item)

    # 从前端删除数据
    def removeFront(self):
        return self.item.pop()

    # 从尾端删除数据
    def removeRear(self):
        return self.item.pop(0)

    # 队列的长度
    def size(self):
        return len(self.items)

​ 测试结果如下：

# 测试
d = Deque()
d.isEmpty()

# 插入元素
d.addFront('I')
d.addFront('like')
d.addRear('Python')

# 测试长度
d.size()

# 输出
3