python中队列的实现方法（代码示例）

来源：动视网责编：小采时间：2020-11-27 14:20:42

python中队列的实现方法（代码示例）

python中队列的实现方法（代码示例）:本篇文章给大家带来的内容是关于python中队列的实现方法（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。对于python来说，要实现一个队列的类根据已经有的方法，是很简单的。既然队列要求一端插入，一端删除。明显，pytho

推荐度：

点击下载本文 文档为doc格式

导读python中队列的实现方法（代码示例）:本篇文章给大家带来的内容是关于python中队列的实现方法（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。对于python来说，要实现一个队列的类根据已经有的方法，是很简单的。既然队列要求一端插入，一端删除。明显，pytho

本篇文章给大家带来的内容是关于python中队列的实现方法（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

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

我们用循环的顺序表来实现队列。

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

实现：

分析一下，我们可以知道

可以定义一个头指针，用于指定元素区的开始下标，self._head;

定义一个变量，用于储存元素区的长度，self._num

一个用于保存整个列表长度的变量，self._len

当然还有队列所在的列表变量, self._list

定义了几个变量之后我们来看一下几个判断：

当self._num = self._len时，说明这时候队列满了

当self._num = 0时，队列是空的

一个队列支持的操作，有几个：

建立空的队列
判断队列是否为空
取队列首位的值
出队操作
入队操作
我们还定义了一个增加列表长度的内部方法

具体实现如下：

# _*_ 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

思路很重要，怎么实现的反而不那么重要，你先实现，然后再看我的效果更好！

python中队列的实现方法（代码示例）

推荐度：

点击下载本文 文档为doc格式

标签：方法代码示例

热门焦点

python中队列的实现方法（代码示例）

python中队列的实现方法（代码示例）

python中队列的实现方法（代码示例）

最新推荐

猜你喜欢

热门推荐