スタックデータ構造

1. 序章

このチュートリアルでは、スタックとは何かを学び、それがどのように機能するかを理解します。さらに、スタックデータ構造とその基本的な操作の概要を説明します。

スタックは日常生活の多くの場所に現れます。たとえば、ディスクホルダー内の本、プレート、ディスクのスタック。本の山を例にとってみましょう。本を挿入したり、スタックの一方の端からのみ本を削除したりするなどの操作を実行できます。

同様に、スタックは、リストの一方の端でのみ挿入と削除が許可されるリストです。この端は、スタックのtopと呼ばれます。

スタックの最上位の要素は、挿入操作を使用して最後に挿入された要素であり、削除操作によって最初に削除される要素でもあるため、スタックは後入れ先出し（LIFO）と呼ばれます。リスト。

つまり、最初にスタックに挿入された要素が、最後にスタックから削除される要素でもあるということです。したがって、スタックは後入れ先出し（FILO）リストとも呼ばれます。

スタックは、LIFOストレージを必要とするすべてのアプリケーションに役立ちます。たとえば、文脈自由言語の解析、算術式の評価、関数呼び出しの管理などです。

さらに、スタックの表現を見てみましょう。

次の図は、メモリ内のスタックの表現を示しています。前述のように、スタックはLIFOの順序に従い、スタックの最上位にのみアクセスできます。

次に、スタックで実行できる基本的な操作を見てみましょう。

スタックで実行できる一般的な操作には、挿入、削除、ピーク、およびスタックがいっぱいか空かどうかの確認が含まれます。

これらすべての操作の擬似コードを見てみましょう。

まず、挿入操作を見てみましょう。 スタックの一番上に新しい要素を挿入することは、プッシュ操作と呼ばれます。

次の擬似コードは、push操作の詳細を示しています。

A 、 B 、およびCを空のスタックに挿入する例を見てみましょう。まず、 A を押して、topポイントをAに置きます。次に、 B をスタックにプッシュすると、topがBを指すように更新されます。最後に、 C をスタックにプッシュすると、topがCを指すように更新されます。

次に、削除操作を見てみましょう。 スタックの最上位から要素を削除することは、ポップ操作と呼ばれます。

次の擬似コードは、pop操作の詳細を示しています。

A、B、およびCを含むスタックから最上位の要素を削除する例を見てみましょう。

上部の要素、つまり C が削除されると、topがBを指し始めることがわかります。

第3に、 peek 操作は、スタックから要素を削除せずに、スタックの最上位にある要素を取得します。

次の擬似コードは、peek操作の詳細を示しています。

スタックが完了しているかどうかをチェックします。

次の擬似コードは、isFull操作の詳細を示しています。

最後に、isEmpty操作を見てみましょう。 スタックが空かどうかをチェックします。

次の擬似コードは、isEmpty操作の詳細を示しています。

スタックは、すべての操作でLIFOの順序に従います。つまり、topは常に最上位の要素を指しています。したがって、すべての一般的な操作の時間計算量はO（1）です。

要約すると、スタックと呼ばれるデータ構造について説明しました。スタックの基本的な定義を学びました。さらに、スタックの基本的な機能と一般的な操作についても学びました。最後に、これらの一般的な操作を実装するための擬似コードを調べました。