目標

用python實現(xiàn)循環(huán)隊列，與python list以及python的Queue模塊進行運行速度上的對比

隊列：

顧名思義，可以將它理解為現(xiàn)實生活中的排隊，我們去KFC排隊點餐，永遠都是先排隊的先點餐，后排隊的后點餐（如果世界美好，沒人插隊）
對于隊首：比如現(xiàn)在處于隊首的是小明，排在小明后面的是小紅，小明點完了餐，離開了隊伍，排在小明后面的所有顧客前進一步，此時小紅就成了隊首
對于隊尾：比如現(xiàn)在處于隊尾的是大雄，這時來了一個胖虎，由于世界和平，不許插隊，胖虎只能乖乖排在大雄后面，隊尾就變成了胖虎

image.png

可以看到，入隊的時間復雜度為O(1)，出隊以后，為了維護隊列的隊首，后面所有成員都需要往前挪一位，此時時間復雜度為O(n)，這種效率顯然是不可以接受的，那么能不能不讓所有成員都往前挪一位呢？因此就有了循環(huán)隊列

循環(huán)隊列：

對于循環(huán)隊列，我們需要定義一個變量（front）指向隊首，同樣需要定義（tail）指向下一個元素入隊的位置
當隊列為空時，front == tail
對于隊首：比如現(xiàn)在處于隊首的是小明，front就指向小明，小明點完了餐，離開了隊伍，排在小明后面的是小紅，那么就將front指向小紅（front += 1）。
對于隊尾：比如現(xiàn)在處于隊尾的是大雄，tail就指向大雄后一個位置，這時來了一個胖虎，由于世界和平，不許插隊，胖虎只能乖乖排在大雄后面，隊尾就變成了胖虎后一個位置，此時tail指向胖虎后一個位置（tail += 1）

image.png

乍一看，似乎不將后面所有成員往前挪，只需維護一下front的指向（front += 1）就可以保證隊首，但是我們可以想象下，如果一直只有出隊操作，卻沒有入隊操作，在這種情況下，會發(fā)生什么？

image.png

根據(jù)隊列的特性，如果我們需要再添加成員，只能在胖虎后面添加了，那么胖虎前面的這一打空間很顯然就浪費了。

然而事實上并不像看到的那么簡單，我們不僅僅是浪費了空間，由于這個隊列是基于list實現(xiàn)的，所以這個隊列實際上是有一個初始容量存在的，不過我們平時使用python list的時候是看不到的（關于python list的底層實現(xiàn)，這里有篇伯樂在線的文章：http://python.jobbole.com/82549/），當我們將元素入隊的時候，如果元素個數(shù)達到了這個初始容量，即可判斷隊列為滿，此時如果將元素入隊，就需要進行擴容，以便裝下更多的元素，同理，若元素出隊較多，元素個數(shù)降低到某個程度（我們可以自己定義），就進行縮容，以此節(jié)省空間，下圖是python list的列表空間分配策略：

image.png

OK，現(xiàn)在假設胖虎所在的隊列已經(jīng)滿了，由于只能往后面添加元素，也就是說，哪怕隊列里只有一個胖虎，我們也要進行擴容，擴容的原理是重新定義一個容量更大的列表，將原列表的元素遍歷賦值給新列表，這是個O(n)復雜度的操作，因此我們需要將前面浪費的空間重新利用起來，一方面減少空間的浪費，另一方面減少擴容的次數(shù)，從而提升入隊操作的運行速度，這就是循環(huán)隊列的意義所在了。

我們繼續(xù)將元素入隊，不進行擴容，當隊列最后一個位置入隊元素后，我們從隊列最開始的位置繼續(xù)入隊元素

image.png

由于當tail == front時，我們判斷隊列為空，所以當出現(xiàn)上圖這種情況時，我們判斷隊列為滿，也就是說我們特意浪費了一個空間以維護隊列

利用取余，我們判斷隊列為滿的條件如下：

class LoopQueue(object):
    def __init__(self, n=10):
        self.arr = [None] * (n+1)  # 由于特意浪費了一個空間，所以arr的實際大小應該是用戶傳入的容量+1
        self.front = 0
        self.tail = 0
        self.size = 0

    def is_full(self):
        return (self.tail+1) % len(self.arr) == self.front  

何時擴容、縮容？

擴容方法(resize)：

    def resize(self, new_capacity):
        new_arr = [None] * (new_capacity+1)
        for i in range(self.size):
            new_arr[i] = self.arr[(i+self.front) % len(self.arr)]

        self.arr = new_arr
        self.front = 0
        self.tail = self.size

resize方法的時間復雜度為O(n)

這里我定義為，當隊列滿時，以當前隊列容積的2倍進行擴容（這里的容積指的是隊列實際可存儲的元素個數(shù)）
當元素個數(shù)少于容積的1/4并且元素個數(shù)>1時，以當前隊列容積的1/2倍進行擴容（也就是縮容）

注意：
在沒有觸發(fā)擴容、縮容條件的時候，我們的入隊、出隊操作的時間復雜度僅僅為O(1)，我們只需要維護front和tail即可，但是一旦觸發(fā)擴容、縮容條件，就需要執(zhí)行一次resize這個時間復雜度為O(n)的操作
縮容操作之所以定義在當元素個數(shù)少于容積的1/4時才進行，而不是1/2，是因為存在一種極端情況：
比如我們的隊列此時已經(jīng)滿了，入隊一個元素，我們需要擴容（2倍），如果縮容條件僅僅是容積（2倍擴容后）的1/2，那么此時我們出隊一個元素，就需要進行一次縮容操作，也就是說...當隊列滿的時候，無限入隊一個元素，無限出隊一個元素，就要無限進行resize這個時間復雜度為O(n)的操作，因此這里選擇犧牲了一點空間來避免這種極端情況的出現(xiàn)

時間復雜度

現(xiàn)在假設我們的容積capacity為n，我們用enqueue方法n+1次，才會觸發(fā)一次resize，而一次resize，進行了n次操作，也就是說，平均每次enqueue，我們執(zhí)行的基本操作次數(shù)為： (n+1)+n/n+1 ≈ 2，enqueue操作的時間復雜度為O(1)，同理，dequeue（出隊）方法也是O(1)級別的時間復雜度

Python實現(xiàn)循環(huán)隊列的代碼

import datetime


class LoopQueue(object):
    def __init__(self, n=10):
        self.arr = [None] * (n+1)  # 由于特意浪費了一個空間，所以arr的實際大小應該是用戶傳入的容量+1
        self.front = 0
        self.tail = 0
        self.size = 0

    def __str__(self):
        return str(self.arr)

    def __len__(self):
        return len(self.arr)

    def __iter__(self):
        return iter(self.arr)

    def get_size(self):
        # 獲取隊列元素個數(shù)
        return self.size

    def get_capaticty(self):
        # 獲取隊列容積（實際可存儲元素個數(shù)）
        return self.__len__() - 1

    def is_full(self):
        # 判斷隊列是否為滿
        return (self.tail+1) % len(self.arr) == self.front

    def is_empty(self):
        # 判斷隊列是否為空
        return self.size == 0

    def get_front(self):
        # 獲取隊首
        return self.arr[self.front]

    def enqueue(self, e):
        # 入隊
        if self.is_full():
            self.resize(self.get_capaticty() * 2)  # 如果隊列滿，以當前隊列容積的2倍進行擴容
        self.arr[self.tail] = e
        self.tail = (self.tail+1) % len(self.arr)
        self.size += 1

    def dequeue(self):
        # 出隊
        if self.is_empty():
            raise Exception("Cannot dequeue from en empty queue")

        result = self.arr[self.front]
        self.arr[self.front] = None
        self.front = (self.front+1) % len(self.arr)
        self.size -= 1

        # 如果元素個數(shù)少于容積的1/4并且元素個數(shù)
        if self.size < self.get_capaticty() // 4 and self.get_capaticty() > 1:
            self.resize(self.get_capaticty() // 2)
        return result

    def resize(self, new_capacity):
        new_arr = [None] * (new_capacity+1)
        for i in range(self.size):
            new_arr[i] = self.arr[(i+self.front) % len(self.arr)]

        self.arr = new_arr
        self.front = 0
        self.tail = self.size

    def main(self):
        loop_queue = LoopQueue()
        start_time = datetime.datetime.now()
        for i in range(5000000):
            loop_queue.enqueue(i)
        print('\n---------測試enqueue----------')
        print('Loop_Queue： size = {0} , capacity = {1}\n'.format(loop_queue.get_size(), loop_queue.get_capaticty()), loop_queue)
        print('is_empty：', loop_queue.is_empty())
        print('is_full：', loop_queue.is_full())
        print('get_front：', loop_queue.get_front())

        for i in range(5000000):
            loop_queue.dequeue()
        last_time = datetime.datetime.now() - start_time
        print('\n---------測試dequeue----------')
        print('Loop_Queue： size = {0} , capacity = {1}\n'.format(loop_queue.get_size(), loop_queue.get_capaticty()),
              loop_queue)
        print('is_empty：', loop_queue.is_empty())
        print('is_full：', loop_queue.is_full())
        print('get_front：', loop_queue.get_front())
        print('Loop_Queue運行時間：', last_time)


if __name__ == '__main__':
    loop_queue = LoopQueue()
    loop_queue.main()

與List，python自帶的Queue模塊進行運行速度的對比

自己實現(xiàn)的循環(huán)隊列

出入隊各5000000次，測試運行時間

    def main(self):
        loop_queue = LoopQueue()
        start_time = datetime.datetime.now()
        for i in range(5000000):
            loop_queue.enqueue(i)
        print('\n---------測試enqueue----------')
        print('Loop_Queue： size = {0} , capacity = {1}\n'.format(loop_queue.get_size(), loop_queue.get_capaticty()), loop_queue)
        print('is_empty：', loop_queue.is_empty())
        print('is_full：', loop_queue.is_full())
        print('get_front：', loop_queue.get_front())

        for i in range(5000000):
            loop_queue.dequeue()
        last_time = datetime.datetime.now() - start_time
        print('\n---------測試dequeue----------')
        print('Loop_Queue： size = {0} , capacity = {1}\n'.format(loop_queue.get_size(), loop_queue.get_capaticty()),
              loop_queue)
        print('is_empty：', loop_queue.is_empty())
        print('is_full：', loop_queue.is_full())
        print('get_front：', loop_queue.get_front())
        print('Loop_Queue運行時間：', last_time)

image.png

Python List

由于實在太慢，將出入隊改為各1000000次...

import datetime

a = []
start = datetime.datetime.now()
for i in range(1000000):
    a.append(i)

for i in range(1000000):
    a.remove(i)
last_time = datetime.datetime.now() - start

print(a)
print(last_time)

image.png

Python Queue

同樣是出入隊各5000000次

image.png