用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是大于原队列长度的
　　　　  """
    old = self._data
    self._data = [<span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>] * cap
    front = self._front
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;for</span> i <span class="hljs-keyword" style="color: #ebbbff;"&gt;in</span> range(self._size):
        self._data[i] = old[front]
        front = (<span class="hljs-number" style="color: #ffc58f;"&gt;1</span> + front) % len(old)
    self._front = <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">代码中的_data为存储数据的列表，_size为队列的长度，_front为队列首位置的索引。代码认真读一下还是非常容易理解的，主要利用了%求余的方式来判断队列的头部或者要插入元素的位置。其中的_resize方法可以改变队列的长度，并且将队列的首部放到了列表的首位置。

<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">双端队列

 :
     self._size == len(self._data):
        self._resize( * len(self._data))
    temp = (self._front - ) % len(self._data)
    self._data[temp] = e
    self._front = temp
    self._size += 
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">delete_last<span class="hljs-params" style="color: #ffc58f;">(self):

<span class="hljs-keyword" style="color: #ebbbff;">if self.is_empty():

<span class="hljs-keyword" style="color: #ebbbff;">raise Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty')

temp = self._data[(self._front + self._size - <span class="hljs-number" style="color: #ffc58f;">1) % len(self._data)]

self._size -= <span class="hljs-number" style="color: #ffc58f;">1

<span class="hljs-keyword" style="color: #ebbbff;">return temp

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!