【久远讲算法6】队列——先进先出的数据结构

“阅读本文大概需要6分钟”

你好，我是久远，上次我们进行了关于栈的讲解，我们先来对知识进行回顾：

• 什么是栈

栈是有序集合，队列元素的增添和移除总是发生在同一端的，这一端我们称之为栈顶，另一端称之为栈底，栈中的元素离底端越近，代表其在栈中的时间越长，最新添加的元素将被最先移除。这种排序原则被称作 LIFO（last-in first-out），即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。

• 栈的重要操作

栈中最重要的两个操作是出栈和入栈，我们在 python 中一般通过列表来实现栈的出入。

接下来我们来进行队列的学习，队列和栈一样，是非常简单的数据结构，但是也是非常常见的数据结构。

什么是队列

队列和栈一样，也是有序集合，但它不同于栈的地方在于，队列中的元素是从一端进入，另一端出去。添加操作发生在“尾部”，移除操作则发生在“头部”。新元素从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO（first-in first-out），即先进先出，也称先到先得。

队列字如其名，它的例子在生活中也是比比皆是的，我们现实中的排队即为队列的应用。

日常生活中，我们进电影院要排队，在超市结账要排队，好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。

队列的实现

队列的实现分为队列的定义和操作，如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 先进先出（FIFO），它支持以下操作。

• Queue() ：创建一个空队列。它不需要参数，且会返回一个空队列。
• enqueue( item ) ：在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值。
• dequeue() ：从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队 列的内容。
• isEmpty() ：检查队列是否为空。它不需要参数，且会返回一个布尔值。
• size() ：返回队列中元素的数目。它不需要参数，且会返回一个整数。

创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样，我们利用简洁强大的列 表来实现队列。既然要创建队列，我们首先要确认队列的头尾，在这里我们假设队列的尾部在列表的位置 0 处。

首先我们对队列类进行定义，一个队列中最主要最核心的要素就是队列中的元素，而新生成一个队列时，这个队列中往往没有任何元素，因此我们对队列的初始化定义为：队列中的元素为空，即引用的列表为空列表。

代码如下：

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

当一个队列生成以后，最常见的计算队列长度的操作是必不可少的，因此只需要计算引入列表的长度即可。

代码如下：

def size(self):
        return len(self.items)

既然可以计算长度，那么我们也可以判断队列是否为空，通常我们只需判断引入的列表是否为空列表即可判断队列是否为空了。

代码如下：

def isEmpty(self):
        return self.items == []

接下来就是我们似曾相识，但是又用途非常广泛的两种操作了，插入和删除，我们在前面讲解栈的时候进行了出栈和入栈的操作，而在队列中也有类似的操作，即入队和出队，而队列和栈最大的不同便是，入队和出队并不是在同一个地方执行的。添加操作发生在“尾部”，移除操作则发生在“头部”。

我们在此设引入的列表的 0 号位为队列的尾部，传入要插入的元素 item ，默认将其插入到列表首位，即队列的入队操作，代码如下：

def enqueue(self, item):
        self.items.insert(0,item)

我们在此设引入的列表的表尾为队列的头部，要进行出队操作，只需删除列表的最后一个元素即可。代码如下：

def dequeue(self):
        return self.items.pop()

整体的代码如下：

class Queue:
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)
    
    def enqueue(self, item):
        self.items.insert(0,item)
        
    def dequeue(self):
        return self.items.pop()

总结

恭喜你又学完了一个知识点，队列和栈的知识是不是很简单呢？只需要掌握列表的一些要点，就可以轻松的将队列和栈实现，我们在基础篇只讲解了最基础的实现方法，在后续的提高篇里会告诉大家在考试或者就业面试中，站和队列要怎么运用。

流沙团队联合AI悦创|久远·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线，随时响应！