データ構造 — スタック

プログラミングでは、大量のデータを処理する必要があります。したがって、データを効率的に保存して整理する必要があります。このような場合にデータ構造が役に立ちます。データ構造を使用して、データを保存、整理、処理、取得できます。データ構造は、データの配置方法に応じてさらに 2 つのカテゴリに分類できます。

この記事では、線形構造(スタック)について説明します。非線形構造と比較して、線形構造の背後にある概念は比較的理解しやすいです。このような線形構造の例としては、スタック、キュー、デキュー、リストなどがあります。これらのデータ構造を 1 つずつ見ていきます。これらの線状構造は 2 つの端があると考えることができます。(前部と後部 | 左部と右部 | 上部と下部) 一部の線形構造では要素の挿入または削除が一方の端でのみ可能ですが、一部の構造ではどちらの端でも要素の挿入または削除が可能です。

1. スタック

• 基本的に、スタックは要素の順序付けされたコレクションであり、項目の挿入と削除が同じ端で行われます。この端は一般に「トップ」として知られています。また、上部の反対側の端を「下部」と呼びます。
• また、新しいアイテムは上部近くにあり、古いアイテムは下部近くにあります。したがって、スタックから項目を削除する順序は、スタックに項目を挿入する順序の逆になります。
• スタックの動作をよく理解したところで、スタック データ構造に関連するいくつかの重要な操作を見てみましょう。
• Push (要素) — Push メソッドは、スタックの先頭に項目を挿入するために使用されます。
• Pop () - Pop メソッドは、スタックから一番上の項目 (ほとんどの項目) を削除するために使用されます。
• Peak () — Peek メソッドは、スタックの現在の最上位の項目を確認するために使用されます。
• size () — スタック上に存在する項目の数を返します。
• is_empty () — このメソッドは、スタックが空かどうかを確認するのに役立ちます
• ここでは、リストの最後がスタックの最上位と見なされることに注意してください。(時間計算量 — O(1))リストの先頭をスタックの先頭とみなすことができますが、項目をプッシュまたはポップするときの時間計算量はO(n)になるため、あまり効率的ではありません。
• リストの最後をスタックの先頭とみなす場合


• スタックの実装方法がわかったので、次にスタック データ構造の使用が重要になるいくつかのシナリオを見てみましょう。
• 数値体系の変換
• まず最初に、スタックを使用して 10 進数を 2 進数に変換する方法を見てみましょう。

• 次に、上記のアルゴリズムを拡張して、10 進数を 2 から 16 までの任意の数体系に変換してみましょう。


世の中のほぼすべてのプログラミング言語では、構文内に括弧が使用されています。したがって、括弧をバランスよく使用しないと、構文エラーが発生する可能性があります。

• この問題の最初の段階では、1 種類の括弧、たとえば () だけを考えます。チェックする必要があるのは、括弧のセットのバランスが取れているかどうかです。バランスが取れている場合は true を返し、そうでない場合は false を返す必要があります。
• ( ) — バランスのとれた | ( ( ) ) — バランスの取れた | ( ( ( )( ) ) ) — バランスのとれた
• ( ( ) バランスが取れていません | ( ) ( ) ( — バランスが取れていません | ( ( ( ) ) ( ) — バランスが取れていません

• ( [ ] ) — バランスのとれた | ( ( ) { } ) — バランスの取れた | ( ( [ { } [ ] ] ) ) — バランスの取れた
• ( ( ) バランスが取れていません | ( ) { } ]— バランスが取れていません | ( ( { } [ [ ) — バランスが取れていません


3. スタックを使用して文字列を反転する



4. インフィックス | 後置記法と前置記法

コンピューターサイエンスでは、多くの算術式を扱わなければなりません。式は、演算子 (+、-、​​、/ など)、オペランド (A、B、c、d、1、2、…)、および括弧などの記号で構成されます。

• 中置表記法 —この表記法では、演算子がオペランドの間に置かれます。(<オペランド> <演算子> <オペランド>)
• 式が 1 つの演算子のみで構成されている場合 (例: 2 + 3、4 * 6)、式をすぐに解くことができます。ただし、式に複数の演算子がある場合、式のあいまいさのため、直接解決することはできません。この式1 + 4 * 5を考えてみましょう。最初に加算を実行すると、[ ( 1 + 4 ) * 5 ] = 25 として答えが得られ、最初に乗算を実行すると、[1 + (4 * 5) として答えが得られます。 )] = 21. ご覧のとおり、この表記には多少のあいまいさがあります。したがって、これを解決するために、「演算子の優先順位」と呼ばれるものを使用します。演算子の優先順位に従って、乗算は加算の前に実行する必要があります。したがって、正しい答えは 25 ではなく 21 になるはずです。
• 基本的に、中置記法で書かれた式を解くには、一連のルールに従う必要があり、括弧も追加する必要があります。したがって、この表記法は解決中により多くのメモリを必要とする可能性があります。そこで、これらの課題を克服するために、科学者は他の 2 つの表記法、接頭辞と接尾辞を考案しました。
• 接頭記法では、演算子はオペランドの前に配置されます(<演算子><オペランド> <オペランド>)。後置記法では、演算子はオペランドの後に配置されます。(<オペランド> <オペランド><演算子>)
• 中置記法と比較すると、他の 2 つの記法は人間が読んで理解するのが非常に困難です。ただし、これら 2 つの表記法には括弧などの追加の記号がなく、曖昧さが含まれていないため、これら 2 つの形式で書かれた式はコンピュータで簡単に読み取ることができます。


• 後置式の評価:後置式を評価する必要がある場合は、演算子が見つかるまで左からスキャンを開始する必要があります。演算子を見つけたら、演算子の左側の最初の 2 つのオペランドに対して関連する代数演算を実行する必要があります。

• まず最初に、入力内のすべてのスペースを削除する必要があります。したがって、分割方法を使用する必要があります。次に、式を左から右にスキャンする必要があります。数値に遭遇した場合は、それをスタックにプッシュする必要があります。演算子に遭遇した場合は、スタック内の最上位の項目を 2 つポップする必要があります。次に、算術演算を行うためにヘルパー関数を呼び出す必要があります。その後、結果をスタックにプッシュします。スキャンが完了すると、スタックに残っているもの、つまり評価された後置式の答えが返されます。


• ここで、Python を使用して中置形式の式を後置形式に変換する方法を見てみましょう。