关于数据结构:久远讲算法6队列先进先出的数据结构

53次阅读

共计 2180 个字符，预计需要花费 6 分钟才能阅读完成。

你好，我是长远，上次咱们进行了对于栈的解说，咱们先来对常识进行回顾：

什么是栈

栈是有序汇合，队列元素的削减和移除总是产生在同一端的，这一端咱们称之为栈顶，另一端称之为栈底，栈中的元素离底端越近，代表其在栈中的工夫越长，最新增加的元素将被最先移除。这种排序准则被称作 LIFO（last-in first-out），即后进先出。它提供了一种基于在汇合中的工夫来排序的形式。最近增加的元素凑近顶端，旧元素则凑近底端。

AI 悦创·推出辅导班啦，包含「Python 语言辅导班、C++ 辅导班、算法 / 数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 安排作业 + 我的项目实际等。QQ、微信在线，随时响应！V：Jiabcdefh

栈的重要操作

栈中最重要的两个操作是出栈和入栈，咱们在 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()

祝贺你又学完了一个知识点，队列和栈的常识是不是很简略呢？只须要把握列表的一些要点，就能够轻松的将队列和栈实现，咱们在根底篇只解说了最根底的实现办法，在后续的进步篇里会通知大家在考试或者待业面试中，站和队列要怎么使用。