概述

<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服务器响应请求。

方法，那么出队就需要一个标识来存储当前列表头部的索引，因为当有元素出队后必须改变队列头部的指向。这时就会有一个问题出现，当队列中的数据不断增多，并且出队的次数也越来越多，那么头部的索引数值也会不断增加，之前用过的头部索引的位置不再存储数据，导致该列表之前占用的位置成为了浪费的位置，这会导致列表的长度越来越大，并产生不利的影响。

一个元素都向前移动一位，使列表的第一个元素永远是队列的首个元素，但是这样每次的出队都会移动所有的队列中的元素，代价太大，不可取。

方法，即循环使用列表的方式。简单说就是先创建一个具有默认长度的空列表，向队列添加元素即为append，队首依然用一个变量保存索引，当向队列添加元素，此时的尾部已经到达了原先列表的最大长度处，则将该元素添加到列表的头部，即之前出队后空余的位置，如果空余的位置也没有的话，则将列表的长度扩大，并将队首放到列表的首位置。

代码：

 :
    
<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;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></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>

<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;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></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>

    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>

<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;">"""
　　　　　 默认cap是大于原队列长度的

　　　　 """

<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;<a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></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>

 :
     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

<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


<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


函数中可以选择一个名为maxlen的参数，它可以设定双端队列的固定长度，当队列已经满的时候，再添加元素，比如append(e),此时并不会报错，而是在队列的另一端进行了pop处理。

如果您也喜欢它,动动您的小指点个赞吧