Python描述数据结构之队列实战篇

时间:2020-8-22 作者:admin


文章目录

前言

  LeetCode中有关队列的题目。

1. LeetCode933:最近的请求次数

  LeetCode的第933题:最近的请求次数
  这个题首先要读懂题|ू・ω・` ),题的意思可以理解为有一个队列,然后计算队列元素在区间[t-3000,3000]内的的个数。代码如下:

class RecentCounter:
    def __init__(self):
        self.queue = []

    def ping(self, t):
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue = self.queue[1:]
        return len(self.queue)

  运行结果如下:
Python描述数据结构之队列实战篇

2. LeetCode641:设计循环双端队列

  LeetCode的第641题:设计循环双端队列
  这个题主要就是借助Python里面的collections库里面的deque类来构建双端队列,下面就介绍deque类里面几个常用的方法:

方法 功能
collections.deque(maxlen) 初始化一个最大长度为

maxlenmaxlen

双端队列,当双端队列已经满时,再插入数据,就会有相应个数的数据从另一端出来

append(value) 添加

valuevalue

到右端

appendleft(value) 添加

valuevalue

到左端

pop() 移除最右侧的元素
popleft() 移除最左侧的元素
extend(iterable) 在队列右侧添加

iterableiterable

中的元素

extendleft(iterable) 在队列左侧添加

iterableiterable

中的元素(

iterableiterable

参数的顺序将会反过来添加)

  除此之外还有clear()copy()count()index()insert()remove()reverse(),这里就不一一介绍了。

  代码如下:

class MyCircularDeque:

    def __init__(self, k):
        from collections import deque
        self.length = k
        self.queue = deque(maxlen=self.length)

    def insertFront(self, value):
        if self.isFull():
            return False
        else:
            self.queue.appendleft(value)
            return True

    def insertLast(self, value):
        if self.isFull():
            return False
        else:
            self.queue.append(value)
            return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        else:
            self.queue.popleft()
            return True

    def deleteLast(self):
        if self.isEmpty():
            return False
        else:
            self.queue.pop()
            return True

    def getFront(self):
        if self.isEmpty():
            return -1
        else:
            return self.queue[0]

    def getRear(self):
        if self.isEmpty():
            return -1
        else:
            return self.queue[-1]

    def isEmpty(self):
        if len(self.queue) == 0:
            return True
        else:
            return False

    def isFull(self):
        if len(self.queue) == self.length:
            return True
        else:
            return False

  运行结果如下:

Python描述数据结构之队列实战篇

3. LeetCode622:设计循环队列

  LeetCode的第622题:设计循环队列
  有关循环队列的操作及代码实现,请参考的我的这篇博客,这里不再叙述,代码如下:

class MyCircularQueue:

    def __init__(self, k: int):
        self.length = k + 1
        self.queue = [None] * self.length
        self.front = 0
        self.rear = 0

    def enQueue(self, value):
        if self.isFull():
            return False
        else:
            self.queue[self.rear] = value
            self.rear = (self.rear + 1) % self.length
            return True

    def deQueue(self):
        if self.isEmpty():
            return False
        else:
            self.front = (self.front + 1) % self.length
            return True

    def Front(self):
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.front]

    def Rear(self):
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear-1]

    def isEmpty(self):
        if self.front == self.rear:
            return True
        else:
            return False

    def isFull(self):
        if (self.rear + 1) % self.length == self.front:
            return True
        else:
            return False

  运行结果如下:

Python描述数据结构之队列实战篇

结束语

  队列的题貌似不太多(也许是没有找到),就选了这几个常规题先简单练习一下,大致感觉简单的队列就直接用列表,双端队列就直接使用collections库里面的deque类,其他的暂时还没有想到,嘿嘿。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。