云博(司云中)
Python使用列表来实现固定长度的双端队列

阅读量:(25) 您现在所在的位置: 首页 百宝箱 Python Python使用列表来实现固定长度的双端队列 作者:SmartCloud(云中)
简介:Python使用列表来实现固定长度的双端队列

面试遇到了这样的题目,来简单记录下

刷算法题用过collections 中的deque,用起来蛮爽,这次来自己实现一个简单的版本----固定长度版, 还有一个复杂版,涉及到list的动态扩容.今天先来记录下固定长度版本,然后再拓展模仿list底层扩容来实现动态扩容版的双端队列.

class Dqueue():

    def __init__(self, size):
        if size < 0:
            raise ValueError('值不能小于0')
        self.array = [None for _ in range(size)]
        self.max_size = size  # 保存列表长度上限
        self.cur_size = 0 # 保存列表当前长度
        self.index = 0  # 指明添加元素的位置


    def empty(self):
        """
        判断双端队列是否为空
        :return: bool
        """
        return self.cur_size == 0

    def full(self):
        """
        判断双端队列是否为满
        :return: bool
        """
        return self.cur_size == self.max_size

    def push_front(self, value):
        """
        从队头添加元素
        :return: None
        """
        if self.full():
            raise ValueError('双端队列已满')
        self.index = (self.index - 1) % self.max_size # 定位到列表末尾,从后往前插
        self.array[self.index] = value
        self.cur_size += 1


    def pop_front(self):
        """
        从队头弹出元素
        :return: PyObject
        """
        if self.empty():
            raise ValueError('双端队列为空')

        result = self.array[self.index]  # 取出头部结果
        self.array[self.index] = None # 设置为空
        self.index = (self.index + 1) % self.cur_size
        self.cur_size -= 1
        return result

    def push_back(self, value):
        """
        从队尾添加元素
        :return:None
        """
        if self.full():
            raise ValueError('双端队列已满')
        self.array.append(value)
        self.cur_size += 1

    def pop_back(self):
        """
        从队尾弹出元素
        :return: PyObject
        """
        if self.empty():
            raise ValueError('双端队列为空')
        self.cur_size -= 1
        return self.array.pop()

数据测试

dqueue= Dqueue(5) # 其中5为固定大小的数组的长度
dqueue.empty()
dqueue.full()
dqueue.push_front(111)
item1 = dqueue.pop_front()
dqueue.push_front(6)
item2 = dqueue.pop_back()
dqueue.push_back(12)
print(dqueue.array)
print(item1)
print(item2)

[None, None, None, None, 12]
111
6

点赞一波

0
    评论集
  • SmartCloud(云中)    2021-03-20 17:13
    <script>alert(“hey!you are attacked”)</script>
    1 0
    回复

  • 下方评论哦~

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器