[Programmers] 10. デフォルトデータ構造:キュー(1):キューデフォルト

誤りに対する批判、質問、討論を歓迎します.自由にコメントを残しておきましょう!!

データ構造キュー

は、1つはデータのみ、もう1つはデータのみを格納します.

の順序でデータを入力して取り出すことができます.これは「先入先出」(FIFO:First in First Out)のデータ構造です.

キュー内のエラー

空のキューからデータを取出そうとすると(キューの底流:Queue Underflow)

.
フルキューにデータを入れようとすると(キューオーバーフロー:Queue Overflow)、

キュー内の演算

size():現在のキュー内のデータ要素の数を返します.

isEmpty():現在のキューが空であるかどうかを判断します.
空はTrue、空でなければFalseを返します.

enqueue(x):キューにデータxを追加します.

dequeue():キューの先頭に格納されているデータ要素を削除して返します.

時間複雑度:O(N)O(N)O(N)O(N)配列記録を実施した後、すべての要素を1つ前に進めて先頭の要素を取り出す必要があるため、時間複雑度はリストの長さに比例する.
したがって、

は、キューを双方向(冗長)接続リストとして実装すると、多くの時間を節約することができる.

peek():キューの先頭に格納されているデータ要素を返します.

<注>アレイがキュー演算を実装する時間的複雑さ

計算の複雑さsize()O(1)O(1)O(1)O(1)O(1)O(1)Enqueue(1)O(1)O(1)Dequeue(O(N)O(N)O(N)O(N)Peek(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O

キュー実装

配列実装の使用:Pythonリストと関数の使用

class ArrayQueue:
    def __init__(self):
        self.data = []

    def size(self):
        return self.len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

双方向(デュアル)接続リストを使用した実装:双方向接続リスト

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListQueue:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.nodeCount

    def isEmpty(self):
        return self.data.nodeCount == 0

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.data.nodeCount+1, node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.getAt(1).data

キューの使用

材料を作成する操作が材料を使用する操作と非同期である場合、

.

複数の場所でデータを作成するとき

材料を作成し、これらの材料を使用する作業が同時に複数の場所で発生する場合、

新しいデータを作成するために

のデータを処理する必要があり、その後もこれらのデータを処理する必要がある場合は、

を処理する必要がある.

この記事は、プログラマーアカデミー人工知能Defcosコースで学んだ内容をもとにまとめたものです.