スタックとキュー ||パイソン ||データ構造とアルゴリズム

スタック

スタック - 後入れ先出し(LIFO)順による検索をサポートするストレージコンテナです。スタックはおそらく、バッチ ジョブを処理する場合など、取得順序がまったく重要でない場合に使用するのに適したコンテナです。

たとえば、 カフェテリアで使用されるプレートのスタックを考えてみましょう。アクセスできるのは上部のプレートのみであるため、プレートがスタックから取り除かれる順序は追加された順序の逆になります。 .

スタックに対する INSERT 操作は PUSH と呼ばれることが多く、要素引数をとらない DELETE 操作は POP と呼ばれることがよくあります。

Push (x,s): 項目 x をスタック s の先頭に挿入します。

Pop(s) : スタック s の一番上の項目を返します (そして削除します)。

冷蔵庫に入れられた食品は、賞味期限があるにもかかわらず、通常同じように出てきます。アルゴリズム的には、再帰アルゴリズムの実行中に LIFO が発生する傾向があります。

スタックのアプリケーション -

1. 関数呼び出し: 関数の実行と再帰を管理するために使用されます。
2. 操作を元に戻す: エディターでの「元に戻す/やり直し」の変更を追跡します。
3. ブラウザ履歴: バックトラッキングのために訪問したページを保存します。
4. 式の解析: 数式を評価し、変換します。
5. 構文検証: コード内の括弧またはタグと一致します。
6. メモリ管理: プログラム実行中のコールスタックを管理します。
7. DFS: グラフ アルゴリズムに深さ優先検索を実装します。

配列を使用したスタックの実装 -

• push() - 要素をスタックに挿入します
• pop() - スタックから要素を削除します
• top() - スタックの最上位要素を返します。
• isEmpty() - スタックが空の場合は true を返し、それ以外の場合は false を返します。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

列

Queue - 先入れ先出し (FIFO) 順序による取得をサポートするストレージ コンテナです。キューに対する INSERT 操作を ENQUEUE と呼び、DELETE 操作を DEQUEUE と呼びます。スタック操作 POP と同様に、DEQUEUE は要素引数を取りません。スタックとキューは、DELETE 操作によってセットから削除される要素が事前定義されている動的セットです。

Enqueue(x,q): 項目 x をキュー q の最後に挿入します。

Dequeue(q): キュー q から先頭の項目を返します (および削除します)。

キューには先頭と末尾があります。

• 要素がキューに入れられると、新しく到着した顧客が列の最後尾に配置されるのと同じように、その要素はキューの最後尾に配置されます。

• キューから取り出される要素は、常にキューの先頭にある要素です。たとえば、列の先頭にいる最も長く待っている顧客などです。

キューのアプリケーション -

1. タスクのスケジューリング: CPU プロセスとジョブを順番に管理します。
2. BFS: グラフに幅優先検索を実装します。
3. 印刷キュー: 印刷ジョブを順番に処理します。
4. ネットワーク ルーティング: 送信用のデータ パケットをバッファリングします。
5. コールセンター: 顧客からの電話を待機順に管理します。
6. ストリーミング: ビデオまたはオーディオ ストリームをリアルタイムでバッファリングします。
7. 入力イベント: GUI システムでのキーボードとマウスの入力を処理します。

配列を使用したキューの実装-

• enqueue() – キューへの要素の挿入。
• dequeue() – キューからの要素の削除。
• peek() またはfront()- キューのフロントノードで使用可能なデータ要素を削除せずに取得します。
• isEmpty() – キューが空かどうかを確認します。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

スタックを使用してキューを実装する -

• push(x) - すべての要素をスタック 1 からスタック 2 に移動して順序を逆にし、すべての要素をスタック 2 からスタック 1 に戻します。
• pop() - キューの先頭から要素を削除して返します
• peek() - キューの先頭の要素を返します
• empty() - キューが空の場合は true、それ以外の場合は false を返します。

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

キューを使用したスタックの実装 -

• push(x) - 新しい要素を 2 番目のキューに追加し、すべての要素をキュー 1 からキュー 2 に移動してスタック順序 (LIFO) を維持し、キューを交換します。
• pop() - スタックの一番上の要素を削除して返します
• peek または top() - キューの先頭にある要素を返します
• empty() - キューが空の場合は true、それ以外の場合は false を返します。

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

以上がスタックとキュー ||パイソン ||データ構造とアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。