データ構造 — スタック

Nov 06 2022
ゼロからヒーローまでのアルゴリズムとデータ構造
コンピューター サイエンスでは、スタックは要素のコレクションとして機能する抽象データ型であり、要素をコレクションに追加するプッシュと、まだ削除されていない最新の追加要素を削除するポップの 2 つの主な操作があります。— ウィキペディア 基本的に、スタックとは、挿入と削除が一方の端で行われる順序付けられたリストであり、通常は端が一番上と呼ばれます。
DALL-E を使用して生成された画像

コンピューター サイエンスでは、スタックは要素のコレクションとして機能する抽象データ型であり、次の 2 つの主な操作があります。

コレクションに要素を追加するPush、および

Pop、まだ削除されていない、最後に追加された要素を削除します。— ウィキペディア

基本的に、スタックは挿入と削除が一方の端で行われる順序付けられたリストであり、通常は端が上と呼ばれます。後入れ先出し (LIFO) または先入れ先出し (FILO)。

類推

あなたがレストランでお皿を洗う仕事をしていて、食堂でお皿が積み重ねられていると想像してみてください。一番上にあるプレートが最初に取り外されます。つまり、最も低い位置に配置されたプレートが、スタックに最も長く残ります。したがって、LIFO (Last In First Out) / FILO (First In Last Out) の順序に従っていることが簡単にわかります。

時間の複雑さ:

  • プッシュ() : O(1)
  • pop() : O(1)
  • ピーク() : O(1)

配列またはリンクされたリストを使用してスタックを実装できますが、どちらかを選択することにはいくつかの長所と短所があります。

長所:

  • Linked を使用したスタック: 簡単に破損せず、オブジェクトを自動的にクリーンアップするため、より安全で信頼性が高くなります。
  • Stack using Array : ランダム アクセスがあるため、実装が簡単で、メモリに保存されたポインターは関与しません。
  • リンクを使用するスタック:追加のメモリが必要です。合計サイズを事前に定義する必要があり、スタックがメモリの外側にある場合は、通常の終了が発生する可能性があります。
  • Stack using Array : 主な欠点は、実行時のニーズに応じて拡大縮小しないことです。

スタックは、後入れ先出し (LIFO) の原則に従う線形データ構造です。これは、スタック内に挿入された最後の要素が最初に削除されることを意味します。

⬅️配列と連結リスト| 目次| 次へ(近日公開) ➡️

© Copyright 2021 - 2022 | hachiwiki.com | All Rights Reserved