常用数据结构之Queue(队列)

ゞ浴缸里的玫瑰 2022-12-10 10:06 134阅读 0赞

# 1.定义 #

接着上一篇[常用数据结构之栈][Link 1]，我们趁热打铁，今天来聊一聊队列。我们都知道栈是一种有限制的线性表，只能从顶部入顶部出，即后进先出。队列是一种和栈非常相似的数据结构，也是一种有限制的线性表。其限制条件是FIFO(先进先出)，就好像我们平时排队一样，新来的人需要排在队尾，排在最前面的人最先上车。

![20200925140607666.png][]

# 2.顺序队列代码实现 #

我们使用python列表来实现一个简单的队列，包括入队，出队；这里每次出队的时候直接取第一个位置，然后其它的元素一次往上移动。

#-*- coding:utf-8 -*-
    #此处Queue类是否需要继承object,属于历史遗留问题
    #python2的时候如果继承object表示新式类，在子类方法调用时采用广度优先；否则为旧式类，采用深度优先搜索
    #但是python3已经进行了统一，都用广度优先；所以此处不需要继承object
    class Queue:
        def __init__(self):
            self.array = []
            self.front = 0
            self.rear = 0
        #插入一个元素到队列尾部
        def in_queue(self,v):
            self.array.append(v)
            self.rear += 1
        #出队列
        def out_queue(self):
            return self.array.pop(self.front)
        def get_size(self):
            return len(self.array)
        def is_empty(self):
            return self.array == []
        def list_queue(self):
            return self.array
    queue = Queue()
    queue.in_queue(1)
    print(queue.list_queue())

# 3.双端队列Deque #

上面我们介绍了顺序队列，只能从尾部添加，顶部弹出，类似于我们平时的排队上车的场景；现在想像这么一个场景，早晨去公司排队等电梯。假设有两个电梯A和B，并且一次只有一个电梯运行(有点坑)。这样两边都会有人等，也都可以上。只不过并不是先来的人就一定会先上。

双端队列就是这样一种结构，它运行从顶部和尾部两处入队和出队,这样的话提供了更大的灵活性。如果你只用他一端的功能，那它就是一个顺序队列。下面是简单的python实现。

#-*- coding:utf-8 -*-
    class Deque:
        def __init__(self):
            self.array = []
        def add_front(self,v):
            self.array.insert(0,v)
        def add_rear(self,v):
            self.array.append(v)
        def pop_front(self):
            return self.array.pop(0)
        def pop_rear(self):
            return self.array.pop(-1)
        def get_size(self):
            return len(self.array)
        def is_empty(self):
            return self.array == []
        def list_item(self):
            return self.array

# 4.双端队列检验回文 #

对于经典的回文问题，给定一个字符串‘abcdcba’,如果首和尾相同，并且最后中间留一个字，则判断其为回文。使用双端队列可以很容易的解决该问题，将每一个字符入队，每次弹出队首的和队尾的进行比较，如果有一个不相同即不是回文。否则就是回文。

我们发现解决一些经典的算法问题，使用合适的数据结构是非常重要的。它往往可以把复杂的问题变得简单！

def palindrome(str):
        deque = Deque()
        for char in str:
            deque.add_rear(char)
        print(deque.list_item())
        while deque.get_size()>1:
            first_char = deque.pop_front()
            last_char = deque.pop_rear()
            if first_char != last_char:
                return False
        return True
    str = 'abcdcba'
    print(palindrome(str))

# 5.优先队列 #

在排队的时候，还真的有不少的事，不少的规矩；接下来介绍的就是优先队列。这种队列出队次序跟入队的顺序没有关系，你可以想象这些人都是一些关系户。大家一起来办业务，和董事长有关系的优先级高，下来是和总经理有关系的，然后总监，一般中层，小组长这样；每个元素按照优先级大小出队；

一般的实现我们采用堆的结构，堆顶的元素总是最大的。具体可以参考我们以前的文章[数据结构之堆][Link 2]，在此不再赘述！

# 6.总结 #

本章中我们讨论了队列这种数据结构，它是一种符合先进先出原则的线性表，只能够从尾部添加元素，从顶部移除。接着我们介绍了一些它的变种，比如双端队列，首尾都可以添加和删除元素；优先队列,按照元素的优先级来决定出队次序。总体来讲的话比较简单，但是队列的用途还是很广泛的。比如，我发了这篇文章之后，平台就会提醒我‘您的文章已经进入审核队列’。对于数据结构的学习，还是应该将不同的内容联系对比着学，效率会稍微高一些。加油！

# 7.闲言 #

世界是一个谜团，解开这个谜团的关键就在于如何去解释其中的“随机性”这一概念。我们知道随机扔一枚硬币，正反面朝上的概率都是1/2；可是为什么我扔出了正面朝上，说好的大家都一样呢？这样的结果对反面来说公平吗？我跟很多赌博输钱的人一样，都完全不能理解这个问题。人们把这种现象叫做随机，所谓的随机就是未来在翻牌子吗？到底有没有随机这回事呢？现在世界的认知体系是承认它的存在的，也就是所谓的未来还没来。就好像我们往前不断的走，但其实前面是没有路的，当你的脚落下去的那一瞬间路就产生了。吓得人心惊胆战，人们怎么就那么自信的觉得到了明天世界就会有明天的样子呢？一件事情发生之前需不需要先把它的房子准备好，好让它能住进去呢。

要不然就这么想，其实所有的路都已经产生了，我们这才不会害怕。其实并没有所谓的随机，时间并不是一个线性的概念。它是一个大棋盘，这是一场对抗、一场博弈。随机并不是一种盲目的瞎选，而是一种强大到我们所不能理解的算法。

【全球爆红出道曲】Avril Lavigne - Complicated (Live at All That) 2002.10.26

#  #

[Link 1]: https://mp.csdn.net/console/editor/html/108782686
[20200925140607666.png]: /images/20221123/321c8a914c7d4ac89d2a624e7760b255.png
[Link 2]: https://blog.csdn.net/gaobing1993/article/details/108768791