データ構造：スタック

「スタックは、線形のデータ構造であり、挿入と削除が一端、つまりトップという名前の端で行われる。連続的なアロケーションでは、「トップ」というポインタがスタックのトップを示す。挿入には、「トップ」をインクリメントし、新しい値を挿入し、削除には、「トップ」をデクリメントし、値を回復する。両方の操作にはO(1)の複雑さがある。 連結アロケーションでは、トップは単方向連結リストの最初のノードである。挿入には、新しいノードをアロケートし、値を挿入し、トップに接続する。削除には、トップの値を回復し、トップを次のノードに移動し、削除されたノードを解放する。再び、操作にはO(1)の複雑さがある。 スタックの操作、つまり挿入と削除は、構造の端で行われるため、定数時間の複雑さで効率的な操作を保証する。」