用Python实现数据结构之队列

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10332235"&gt;
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">队列
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">队列与栈的类型很相似，但它遵循的原则是先进先出（FIFO），也就是元素插入的时候只能在该数据结构的末端，而删除只能删除最前面的元素。队列同样应用广泛，例如打印机的队列或者是一个web服务器响应请求。

<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class <span class="hljs-title" style="color: #7285b7;">Queue<span class="hljs-params" style="color: #ffc58f;">():

<span class="hljs-string" style="color: #d1f1a9;"&gt;"""
基于循环列表的队列
"""</span>

DEFAULT_CAPACITY = <span class="hljs-number" style="color: #ffc58f;"&gt;10</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__init__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self._data = [<span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>] * Queue.DEFAULT_CAPACITY
    self._size = <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>
    self._front = <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__len__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._size

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;is_empty</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._size == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;first</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Queue is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self._data[self._front]

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;dequeue</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>

    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Queue is empty'</span>)
    temp = self._data[self._front]
    self._front = (self._front + <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>) % len(self._data)
    self._size -= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> temp

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;enqueue</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,e)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self._size == len(self._data):
        self._resize(<span class="hljs-number" style="color: #ffc58f;"&gt;2</span> * len(self._data))
    temp = (self._front + self._size) % len(self._data)
    self._data[temp] = e
    self._size += <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;_resize</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,cap)</span>:</span>
　　　　  <span class="hljs-string" style="color: #d1f1a9;">"""

　　　　　 默认cap是大于原队列长度的
                        
（编辑：安卓应用网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!