C++ のスタックとキュー

C のスタックとキューの概要

スタックとキューは C で一般的に使用されるデータ構造であり、プログラムで広く使用されています。この記事では、スタックとキューの概念、使用法、適用シナリオについて詳しく紹介します。

1. スタックの概念

スタックは線形データ構造であり、「先入れ後出し」の特性があります。スタックでは、スタックにプッシュされたデータはスタックの底部に近くなり、後でスタックにプッシュされたデータはスタックの上部に近くなります。

スタックの主な操作はプッシュとポップです。プッシュはスタックにデータを追加すること、ポップはスタックからデータを削除することです。スタックには、スタックの最上位要素の表示 (top) とスタックが空かどうかの判断 (empty) という 2 つの重要な特殊操作もあります。

スタックの適用シナリオは非常に幅広く、たとえば関数の呼び出し時にスタックの使用が伴います。関数が呼び出されると、そのパラメータ、ローカル変数、その他の情報がスタックにプッシュされます。関数の実行が終了すると、この情報はスタックからポップされ、関数呼び出し前の状態に復元されます。

2. キューの概念

キュー (Queue) も線形データ構造であり、「先入れ先出し」の特徴があります。キューでは、先にキューに入れられたデータはキューの先頭に近くなり、後でキューに入れられたデータはキューの最後に近くなります。

キューの主な操作は、エンキューとデキューです。キューに入るということはキューの最後にデータを追加することを意味し、デキューとはキューの先頭からデータを削除することを意味します。キューには、ヘッド要素 (先頭) の表示と、キューが空 (空) かどうかの判断という 2 つの重要な特別な操作もあります。

キューも広く使用されており、たとえば、オペレーティング システムのプロセス スケジューリングでは、実行を待機しているプロセスを保存するためにキューを使用できます。システムリソースに空きがある場合、キューの先頭からプロセスが取り出され、すべてのタスクが完了するまで実行されます。

3. スタックとキューの応用例

1. 括弧の一致

プログラミングでは、文字列内の括弧が一致するかどうかを判断する必要があることがよくあります。 。たとえば、Python プログラムを作成するときに、コード ブロックが正しくインデントされているかどうかを確認する必要がある場合、スタックを使用してこれを実現できます。

具体的な実装方法は、文字列内のすべての文字をトラバースし、左括弧が見つかったときにそれをスタックにプッシュすることです。右括弧が見つかると、スタックの最上位要素が突き合わせのためにポップされます。一致が成功した場合は、トラバースを続行します。そうでない場合は、エラー メッセージが返されます。

2. プロセス スケジューリング

オペレーティング システムでは、プロセスの統合スケジューリングと調整を実現する必要があります。このとき、キューを使用して実行を待っているプロセスを保存することができ、優先順位と実行順序はオペレーティング システムによって決定されます。

具体的な実装方法は、各プロセスをプロセス番号や優先度などの情報を含むデータ構造に抽象化することです。これらの処理をキューに入れ、キュー内の処理を順番に実行します。プロセスがタスクを完了すると、キューが空になるまでキューからポップアウトされます。

4. C でのスタックとキューの実装

C では、標準ライブラリによって提供されるコンテナ クラスを使用してスタックとキューを実装できます。

1. スタックの実装

スタックは、コンテナ クラス std::stack を使用して実装できます。

std::stack は、要素タイプと基礎となるコンテナータイプを指定する必要があるテンプレート クラスです。基礎となるコンテナーの種類が指定されていない場合、デフォルトで std::deque が基礎となるコンテナーとして使用されます。

次に、単純なスタック実装例を示します。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top() << std::endl; // 输出3

    s.pop();

    std::cout << s.top() << std::endl; // 输出2

    while (!s.empty()) {
        s.pop();
    }

    return 0;
}

2. キューの実装

キューは、コンテナ クラス std::queue を使用して実装できます。

std::queue もテンプレート クラスであり、要素の種類と基礎となるコンテナの種類を指定する必要があります。基礎となるコンテナーの種類が指定されていない場合、デフォルトで std::deque が基礎となるコンテナーとして使用されます。

以下は簡単なキューの実装例です:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << q.front() << std::endl; // 输出1

    q.pop();

    std::cout << q.front() << std::endl; // 输出2

    while (!q.empty()) {
        q.pop();
    }

    return 0;
}

概要

上記の紹介からわかるように、スタックとキューは非常に実用的なデータ構造であり、多くの実際の問題を解決します。プログラミングでは、これら 2 つのデータ構造の使用法と実装原則を習得すると、プログラムの効率と信頼性を向上させることができます。

以上がC++ のスタックとキューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。