スタックとヒープ

スタックとは、リスト項目の**と削除がトップと呼ばれる末端でのみ可能な順序付きリストのことです。したがって、スタックはLIFO（後入れ先出し）データ構造とみなされる。ヒープは、ヒープ特性と呼ばれる特殊な性質を満たす、特殊なツリーベースのデータ構造である。また、ヒープは完全木であり、木の葉の間に隙間がない。つまり、完全木では、新しいレベルが木に追加される前に各レベルが埋められ、与えられたレベルのノードは左から右へと埋められる。

スタックとは何ですか？

前述したように、スタックはトップと呼ばれる末端からしか要素が追加・削除されないデータ構造である。プッシュ操作はスタックの先頭に新しい要素を追加し、ポップ操作はスタックの先頭から要素を削除する操作である。スタックが満杯の場合、プッシュ操作時にスタックオーバーフローとして扱われる。既に空のスタックに対してpop操作を行った場合、スタックのオーバーフローとして扱われる。スタックに対して実行できる操作の数は非常に少ないため、制限されたデータ構造と考えられている。さらに、pushとpopの操作の定義から、最後に追加された要素が最初にスタックから削除されることは明らかである。したがって、スタックは後入れ先出しのデータ構造であると考えられる。

ヒープとは何ですか？

前述したように、ヒープとはヒープ性を満たす完全木のことである。ヒープ特性は、yがxの子である場合、ノードxに格納されている値がノードyに格納されている値以上であること（すなわち、値（x）≧値（y））を宣言している。この属性は、最も大きな値を持つノードが常にルートノードに配置されることを示す。この性質を利用して構築されたヒープを最大ヒープと呼ぶ。ヒープの性質の別の変種は、これの反対である。(すなわち、値 (x) ≤ 値 (y)) である。つまり、値が最小のノードは常にルートノードに置かれるため、最小ヒープと呼ばれる。ヒープに対して、最小（最小ヒープ内）や最大（最大ヒープ内）を求める、最小（最小ヒープ内）や最大（最大ヒープ内）を削除する、（最大ヒープ内で）キーを追加する、（最小ヒープ内で）キーを減算するなど、さまざまな操作を実行することができる。

スタックとヒープの違いは何ですか？