python中隊列的實作方法（程式碼範例）

這篇文章帶給大家的內容是關於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時，佇列是空的

一個佇列支援的操作，有幾個：

1. 建立空的佇列

2. #判斷佇列是否為空

3. 取佇列首位的值

4. 出隊運算

5. #入隊運算

6. 我們也定義了一個增加清單長度的內部方法

##具體實作如下：

# _*_ 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中隊列的實作方法（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！