algorithm - 中間要素に対する操作を含むスタックを設計する

Question

O(1) 時間の複雑さで次の操作をサポートするスタックを実装する方法は?

1. 要素をスタックの一番上に追加するプッシュ。
2. スタックの一番上から要素を削除するポップ。
3. スタックの中間要素を返す Middle を見つけます。
4. 中央の要素を削除する中間の削除

Answer 1

先頭、末尾、および中間の要素へのポインタを含む LinkedList データ構造を使用します。

これにより、中間要素のプッシュ、ポップ、削除、および検索に O(1) 時間の複雑さが生じます。

唯一のトリックは、このデータ構造から要素を追加または削除するときに、「中間」要素ポインターを正しく移動することです。