您现在的位置是:网站首页>Python编程Python编程

python中队列的实现方法(代码示例)

少儿编程网2020-02-14 18:44:11Python编程 人已围观 来源:少儿编程 -用户投稿

简介本篇文章给大家带来的内容是关于python中队列的实现方法(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。对于python来说,要实现一个队列的类根据已经有的方法,是很简单的。既然队列要求一端插入,一端删除。明显,python就有这两个工具,对于队列的尾部删除用pop(0

本篇文章给大家带来的内容是关于python中队列的实现方法(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

对于python来说,要实现一个队列的类根据已经有的方法,是很简单的。既然队列要求一端插入,一端删除。明显,python就有这两个工具,对于队列的尾部删除用pop(0)就可以做到,头部插入,用append就可以做到。从这方面来说确实很简单,但总是要找到最优解不是吗?所以我们不用pop方法,因为对于python内部实现而言,这个方法的复杂度是O(n),为什么呢?我们删除列表的首位列表的全部元素都会往前移,这是python要保持列表的完整性E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

我们用循环的顺序表来实现队列。E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

具体思路如下:E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台
我们从列表前面开始删除的时候,头部指针跟着元素区的起点,也就是头指针是不断随着删除向后面变化的,那么前面空着的节点,我们不浪费,当尾部指针随着加入元素走到列表最后一个位置的时候,尾部指针从新走向列表的第一个节点(空的节点),至于停止,当我们的头部指针和尾部指针汇合的时候,说明这个时候才是整个固定列表全部用完的时候,这里我们还定义了一个扩大队列可存储空间的方法,在内部调用的,当队列满时,我们就自动调用这个内部方法,扩大队列空间。E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

实现:E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

分析一下,我们可以知道E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 可以定义一个头指针,用于指定元素区的开始下标,self._head;E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 定义一个变量,用于储存元素区的长度,self._numE83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 一个用于保存整个列表长度的变量,self._lenE83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 当然还有队列所在的列表变量, self._listE83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

定义了几个变量之后我们来看一下几个判断:E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 当self._num = self._len时,说明这时候队列满了E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  • 当self._num = 0时,队列是空的E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

一个队列支持的操作,有几个:E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  1. 建立空的队列E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  2. 判断队列是否为空E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  3. 取队列首位的值E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  4. 出队操作E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  5. 入队操作E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

  6. 我们还定义了一个增加列表长度的内部方法E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

具体实现如下:E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

# _*_ coding: utf-8 _*_

class OverFlowError(ValueError):
    pass

class Queue:
    def __init__(self, init_len=0):
        self._len = init_len
        self._list = [0] * init_len
        self._num = 0 # 计数元素
        self._head = 0 # 头指针

    def is_empty(self):
        return self._num == 0

    def peek(self):
        if self._num == 0:
            raise OverFlowError("取队列首位值,但队列为空")
        return self._list[self._head]

    def enqueue(self, elem):
        if self._num = self._len:
            self._extend()
        self._list[(self._head + self._num) % self._len] = elem
        self._num += 1

    def dequeue(self):
        if self._num == 0:
            raise OverFlowError("队列首位出队列,但队列为空")
        e = self._list[self._head]
        self._head = (self._head + 1) % self._len
        self._num -= 1
        return e

    def _extend(self):
        new_len = self._len * 2
        new_list = [0] * new_len
        i = 0
        p = self._head
        while not p == (self._head + self._num) % self._len:
            new_list[i] = self._list[p]
            i += 1
        self._len = new_len
        self._list = new_list
        self._head = 0

思路很重要,怎么实现的反而不那么重要,你先实现,然后再看我的效果更好!E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

以上就是python中队列的实现方法(代码示例)的详细内容,更多请关注少儿编程网其它相关文章!E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台

来源:php中文网E83少儿编程网-Scratch_Python_教程_免费少儿编程学习平台


相关文章:

支持一下 ( )

python中队列的实现方法(代码示例)

      匿名评论
    • 评论
    人参与,条评论
    python中队列的实现方法(代码示例)

客服在线

服务时间

周一至周日 9:00-21:00