アルゴリズムの旅について話しましょう：スタック

[[379190]]

スタックの本質は、特殊なデータ構造です。その特殊な構造は、データのエントリと終了のルールが先入れ後出しと後入れ先出しである点で、配列やリンク リストとは異なります。

その特殊な特性により、ブラウザの前進や後退の効果など、特定のシナリオでよく使用されます。

ブラウザの特徴は、以前訪問したウェブサイトを訪問できるだけでなく、後から訪問したウェブサイトを遡って訪問することもできることです。

ブラウザのこの機能はスタックの構造に完全に一致します。

使用する必要があるのは、ブラウザの前方アクセスを表すスタック 1 つと後方アクセスを表すスタック 1 つの 2 つだけです。

データ セットが、一方の端でのみデータの挿入と削除を伴い、先入れ後出しと後入れ先出しの特性を満たしている場合、最初に考えるべきことは、必要なシナリオをより適切に実装できるかどうかを確認するためのスタックです。

スタックを実装する方法は 2 つあります。1 つは配列ベースの実装で、シーケンシャル スタックと呼ばれます。もう 1 つはリンク リスト ベースの実装で、リンク スタックと呼ばれます。

これら 2 つの実装に大きな違いはありません。実装後、スタック アクセスと終了の時間計算量は O(1) になります。

違いは、配列に基づくスタックでは、ポインターを保存する必要がないため、消費するメモリが少なくなることです。

しかし、配列に基づいて実行する必要があるもう 1 つの追加事項は、不定サイズのスタックを実装する必要がある場合、すべての配列ベースの実装で必須である動的拡張を実装する必要があることです。

次に、配列ベースのシーケンシャルスタックを実装します。複雑さを軽減するために、容量の拡張は考慮しません。

// 配列実装に基づく順次スタック class ArrayStack(private val n: Int) { private val items = arrayOfNulls (n) // スタック配列 private var count = 0 // スタックの現在のサイズ // プッシュ fun push(item: String): Boolean { // 配列に十分なスペースがないため、直接 false を返し、プッシュは失敗します if (count == n) return false // 添字 count の位置に item を配置し、count に 1 を追加します items[count] = item ++count return true } // ポップ fun pop(): String? { // スタックが空の場合は、直接 null を返します if (count == 0) return null // 添字 count-1 の配列要素を返し、スタック内の要素数を 1 つ減らします val tmp = items[count - 1] --count return tmp }}

上記の実装に基づいて、スタックアクセスの時間計算量は O(1) であると簡単に結論付けることができます。

一方、追加のスペースは割り当てられないため、スタックの空間計算量はO(1)です。

上記で実装したのは固定シーケンシャルスタックです。つまり、スタックのサイズは初期化時に指定されます。スタックがいっぱいになると、スタックにデータを追加できなくなります。もちろん、リンク リストに基づくリンク スタックにはこの制限はありません。

シーケンシャル スタックのこの制限を解決するには、配列セクションでも説明されているように、データを拡張する必要があります。

したがって、拡張をサポートするスタックを実装する場合は、最下位レベルでの拡張に基づく配列にのみ依存する必要があります。

具体的な展開図は以下のとおりです。

具体的なコード実装については、データ拡張を参照してください。

次に、配列の拡張に基づいてスタックの時間計算量を分析してみましょう。

まず、スタックサイズに達していない場合、このステージは固定シーケンシャルスタックと同じであり、エントリと終了の時間計算量はO(1)です。

データが K で拡張の臨界点に達すると、配列のサイズを元のサイズの 2 倍に拡張し、以前のデータを新しい配列にコピーする必要があります。この段階で消費される時間計算量は O(K) です。

拡張が完了すると、スタックへの出入りが継続され、時間計算量は再び O(1) になります。

再び 2k に達すると、再度拡張する必要があり、データを新しい配列にコピーする必要があります。このときに費やされる時間計算量は O(2k) です。

上記の手順を繰り返します。

これは、拡張をサポートするシーケンシャル スタックの時間計算量の変化です。つまり、最良の場合の時間計算量は O(1)、最悪の場合の時間計算量は O(n) です。平均時間計算量はどうでしょうか?

「アルゴリズム ツアー: 複雑性分析」で言及されている償却時間複雑度を覚えていますか?

次に、償却時間計算量を使用して平均時間計算量を分析します。実際、償却時間計算量のアルゴリズムは、図を見れば理解できます。

毎回、拡張によって消費される時間を後続のスタック プッシュに分散します。償却前は、スタックへのプッシュにプッシュ時間が必要であり、償却後は、スタックへのプッシュにプッシュ時間とデータ移動時間が必要になります。プッシュとムーブの時間計算量はO(1)です。

したがって、償却後、スタック全体の時間計算量は O(1) になります。つまり、スタックの平均計算量は O(1) になります。

スタックについて包括的に理解できたので、スタックをデータ構造として完全に統合するには、あとは実践して慣れるだけです。

例: 単純な文字列式の値を計算する基本的な計算機を実装します。文字列式には、左括弧 (、右括弧)、プラス記号 +、マイナス記号 -、負でない整数、およびスペースを含めることができます。

式ベースの操作はスタック構造に非常に適しており、スタックを使用して実装できます。実装のアイデアは次のとおりです。

符号ビットを設定すると、すべての演算が加算に変換されます。

数字が見つかるたびに、前の符号ビットが繰り上がり、前の結果に加算されます。

'(' に遭遇したら、前の符号ビットと結果をスタックに保存し、手順 1 と 2 を繰り返して括弧内の値を計算します。

')' に遭遇すると、以前に保持された符号ビットと結果を取り出し、現在の結果に追加します。

/** * O(n) */ fun calculate(s: String): Int { val numberStack = Stack () var sign = 1 // 符号ビットvar result = 0 var index = 0 while (index < s.length) { when (s[index]) { '+' -> { sign = 1 } '-' -> { sign = -1 } '(' -> { // 現在の結果をスタックに追加します numberStack.push(result) result = 0 // 現在の符号ビットをスタックに追加します numberStack.push(sign) sign = 1 } ')' -> { // 以前に保持した符号ビットと結果を取り出し、現在の結果に追加します result = numberStack.pop() * result + numberStack.pop() } ' ' -> { } else -> { // 現在の値を計算します。複数桁の数値になる場合がありますvar cur = s[index] - '0' while (index + 1 < s.length && s[index + 1].isDigit()) { cur = cur * 10 + (s[++index] - '0') } // 前の符号ビットを持つ数値に遭遇した場合、それを前の結果に追加します result += cur * sign } } index++ } return result}

スタックに関する古典的な演習もいくつかあります。これらをマスターできれば、スタック アルゴリズムに問題はありません。

バックスペースで文字列を比較する

野球の試合

次の大きな要素

有効な括弧

ソースコードは Github に置いてありますので、必要な場合はチェックしてください。

この記事はWeChatの公式アカウント「Android Supply Station」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合はAndroid Supply Station公式アカウントまでご連絡ください。