Pythonでのキューの実装方法（コード例）

この記事は Python でのキューの実装方法 (コード例) についての内容であり、一定の参考価値がありますので、困っている方は参考にしていただければ幸いです。

#Python の場合、既存のメソッドに基づいてキュー クラスを実装するのは非常に簡単です。キューは一方の端で挿入し、もう一方の端で削除する必要があるためです。もちろん、Python にはこれら 2 つのツールがあり、キューの末尾を削除するには Pop(0) を使用し、先頭を挿入するには append を使用します。この点では非常にシンプルですが、常に最適解を見つける必要がありますよね。 Python の内部実装では、このメソッドの複雑さは O(n) であるため、 では Pop メソッドを使用しません。リストの最初の要素を削除すると、リストのすべての要素が前方に移動します。これが、Python がリストの整合性を維持したい理由です。

実装には循環シーケンス テーブルを使用します。待ち行列。

具体的な考え方は次のとおりです。
リストの先頭から削除を開始すると、先頭ポインタは要素領域の開始点をたどります。つまり、先頭ポインタは削除とともに変化し続けます。末尾ポインタが要素を追加したリストの最後の位置に到達すると、末尾ポインタはリストの最初のノード (空ノード) に移動します。停止用, ヘッドポインタとテールポインタが収束するとき, これは固定リスト全体が使い果たされたときを意味します. ここではまた, 内部的に呼び出されるキューの記憶領域を拡張するメソッドも定義します.がいっぱいの場合は、この内部メソッドが自動的に呼び出されます。キュー スペースを拡張します。

実装:

分析後、

• が要素領域の開始添え字 self を指定するヘッド ポインターを定義できることがわかります。 _head;

• 要素領域の長さを格納する変数 self を定義します。_num

• 要素領域全体の長さを格納する変数list 、 self._len

• もちろん、キューが配置される list 変数、 self._list

もあります。いくつか定義した後、変数を見てみましょう。 いくつかの判断:

• #self._num = self._len の場合、現時点でキューがいっぱいであることを意味します

• self._num = 0 の場合、キューが空の場合

##キューはいくつかの操作をサポートします:

空のキューを作成する
キューが空かどうか判定
キュー先頭の値を取得
デキュー操作

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 中国語 Web サイトの他の関連記事を参照してください。