コンテンツ

• 比較表
• スタックの定義
• 例
• キューの定義
• 例
• スタック実装
• キューの実装
• スタックの操作
• キューでの操作
• スタックの用途
• キューのアプリケーション
• 結論

スタックとキューはどちらも非プリミティブデータ構造です。スタックとキューの主な違いは、スタックがLIFO（後入れ先出し）メソッドを使用してデータ要素にアクセスおよび追加するのに対して、キューはFIFO（先入れ先出し）メソッドを使用してデータ要素にアクセスおよび追加することです。

一方、スタックでは、データ要素をプッシュおよびポップするために一方の端のみが開いており、キューでは、データ要素をエンキューおよびデキューするために両端が開いています。

スタックとキューは、データ要素を保存するために使用されるデータ構造であり、実際にはいくつかの現実世界の同等物に基づいています。たとえば、スタックはCDのスタックであり、CDのスタックの一番上からCDを取り出して挿入できます。同様に、キューは劇場チケットのキューであり、最初に立っている人、つまりキューの先頭が最初に処理され、到着した新しい人がキューの後ろ（キューの後端）に表示されます。

1. 比較表
2. 定義
3. 主な違い
4. 実装
5. オペレーション
6. 用途
7. 結論

比較表

比較の根拠	スタック	キュー
動作原理	LIFO（後入れ先出し）	FIFO（先入れ先出し）
構造	同じ端が要素の挿入と削除に使用されます。	一方の端は挿入、つまり後端に使用され、もう一方の端は要素の削除、つまり前端に使用されます。
使用されたポインターの数	1	2（単純なキューの場合）
実行された操作	プッシュアンドポップ	エンキューとデキュー
空の状態の検査	トップ== -1	前部== -1 ||フロント==リア+ 1
完全な状態の検査	トップ==最大-1	背面==最大-1
バリエーション	バリアントはありません。	循環キュー、優先キュー、二重終了キューなどのバリアントがあります。
実装	よりシンプル	比較的複雑

スタックの定義

スタックは、非プリミティブな線形データ構造です。これは、新しいアイテムが追加され、既存の要素がスタックの最上部（TOS）と呼ばれる一方の端からのみ削除される順序付きリストです。スタック内のすべての削除と挿入はスタックの最上部から行われるため、最後に追加された要素がスタックから最初に削除されます。これが、スタックが後入れ先出し（LIFO）タイプのリストと呼ばれる理由です。

スタックで頻繁にアクセスされる要素は最上位の要素であるのに対し、最後に利用可能な要素はスタックの最下部にあることに注意してください。

例

ビスケット（またはポピンズ）を食べる人もいます。想定すると、カバーの片側だけが破れ、ビスケットが1つずつ取り出されます。これはポッピングと呼ばれるものです。同様に、ビスケットをしばらく保存したい場合は、プッシュと呼ばれる同じ引き裂かれた端からそれらをパックに戻します。

キューの定義

キューは、非プリミティブ型のカテゴリに含まれる線形データ構造です。これは、類似したタイプの要素のコレクションです。新しい要素の追加は、リアエンドと呼ばれる一端で行われます。同様に、既存の要素の削除は、フロントエンドと呼ばれるもう一方の端で行われ、論理的には先入れ先出し（FIFO）タイプのリストです。

例

私たちの日々の生活の中で、私たちは目的のサービスを待つ多くの状況に出くわします。そこで、私たちはサービスを受ける順番を待つ列に入らなければなりません。この待機キューは、キューと考えることができます。

1. 一方、スタックはLIFOメカニズムに従い、キューは要素を追加および削除するためにFIFOメカニズムに従います。
2. スタックでは、要素の挿入と削除に同じ端が使用されます。それどころか、要素を挿入および削除するためにキューで2つの異なる端が使用されます。
3. スタックにはオープンエンドが1つしかないため、1つのポインターのみを使用してスタックの最上部を参照する理由です。ただし、キューは2つのポインターを使用して、キューの前端と後端を参照します。
4. スタックは、キューでエンキューおよびデキューと呼ばれるプッシュとポップとして知られる2つの操作を実行します。
5. スタックの実装は簡単ですが、キューの実装は扱いにくいです。
6. キューには、循環キュー、優先キュー、二重終了キューなどのバリアントがあります。対照的に、スタックにはバリアントがありません。

スタック実装

スタックは2つの方法で適用できます。

1. 静的実装 配列を使用してスタックを作成します。静的実装は簡単な手法ですが、プログラムの設計中にスタックのサイズの宣言を行う必要があるため、サイズを変更できないため、柔軟な作成方法ではありません。また、静的な実装はメモリ使用率に関してあまり効率的ではありません。 （スタックを実装するための）配列は、操作の開始前（プログラム設計時）に宣言されるため。スタック内のソートされる要素の数が非常に少ない場合、静的に割り当てられたメモリが無駄になります。一方、スタックに格納する要素の数が増えると、新しい要素を収容できるように配列のサイズを変更して容量を増やすことはできません。
2. 動的な実装 リンクリスト表現とも呼ばれ、ポインタを使用してデータ構造のスタックタイプを実装します。

キューの実装

キューは2つの方法で実装できます。

1. 静的実装：配列を使用してキューを実装する場合、設計時または処理開始前に配列のサイズを宣言する必要があるため、キューに格納する要素の正確な数を事前に確認する必要があります。この場合、配列の先頭がキューの先頭になり、配列の最後の場所がキューの末尾として機能します。次の関係は、配列を使用して実装された場合、キューに要素全体が存在することを示します。
   フロント–リア+ 1
   「後部<前部」の場合、キューには要素が存在しないか、キューは常に空になります。
2. 動的な実装：ポインターを使用してキューを実装すると、主な欠点は、リンクされた表現のノードが、配列表現の対応する要素よりも多くのメモリ空間を消費することです。各ノードには少なくとも2つのフィールドがあり、1つはデータフィールド用で、もう1つは次のノードのアドレスを格納しますが、リンクされた表現ではデータフィールドのみがあります。リンクされた表現を使用するメリットは、他の要素のグループの途中で要素を挿入または削除する必要がある場合に明らかになります。

スタックの操作

スタックで操作できる基本操作は次のとおりです。

1. 押す：新しい要素がスタックの一番上に追加されるときは、プッシュ操作と呼ばれます。スタック内の要素をプッシュすると、新しい要素が上部に挿入されるため、要素の追加が呼び出されます。プッシュ操作ごとに、上部が1つ増加します。配列がいっぱいで、新しい要素を追加できない場合は、STACK-FULL状態またはSTACK OVERFLOWと呼ばれます。プッシュ操作-Cの機能：
   スタックの考慮は
   int stack、top = -1;
void push（）
{
intアイテム。
if（トップ<4）
{
f（「数字を入力してください」）;
scan（ "％d"、＆item）;
top = top + 1;
stack = item;
}
他に
{
f（「スタックがいっぱいです」）;
}
}
2. ポップ：要素がスタックの最上部から削除されるとき、POP操作と呼ばれます。ポップ操作が行われるたびに、スタックが1つ減少します。スタックに要素が残っていない状態でポップが実行されると、スタックが空であることを意味するスタックアンダーフロー状態になります。 POP操作– Cの機能：
   スタックの考慮は
   int stack、top = -1;
void pop（）
{
intアイテム。
if（トップ> = 4）
{
アイテム=スタック;
top = top-1;
f（「削除された数=％d」、アイテム）;
}
他に
{
f（「スタックは空です」）;
}
}

キューでの操作

キューで実行できる基本的な操作は次のとおりです。

1. エンキュー：キューに要素を挿入するには：Cのキューイング操作関数：
   キューは次のように宣言されます
   int queue、Front = -1およびrear = -1;
void add（）
{
intアイテム。
if（リア<4）
{
f（「数字を入力してください」）;
scan（ "％d"、＆item）;
if（front == -1）
{
前部= 0
後部= 0;
}
他に
{
後部=後部+ 1;
}
queue = item;
}
他に
{
f（ "キューがいっぱいです"）;
}
}

2. デキュー：queue.Enqueuing操作関数からCの要素を削除するには：
   キューは次のように宣言されます
   int queue、Front = -1およびrear = -1;
void delete（）
{
intアイテム。
if（front！= -1）
{
アイテム=キュー;
if（フロント==リア）
{
front = -1;
後部= -1;
}
他に
{
front = front + 1;
f（「削除された数=％d」、アイテム）;
}
}
他に
{
f（ "キューは空です"）;
}
}

スタックの用途

• コンパイラで解析します。
• Java仮想マシン。
• ワードプロセッサで元に戻します。
• Webブラウザの[戻る]ボタン。
• ers用のPostScript言語。
• コンパイラーでの関数呼び出しの実装。

キューのアプリケーション

• データバッファ
• 非同期データ転送（ファイルIO、パイプ、ソケット）。
• 共有リソース（プロセッサ、プロセッサ）にリクエストを割り当てます。
• トラフィック分析。
• スーパーマーケットにいるレジ係の数を決定します。

結論

スタックとキューは、動作メカニズム、構造、実装、バリアントなどの特定の点で線形のデータ構造が異なりますが、どちらもリストに要素を格納し、要素の追加や削除などのリストに対する操作を実行するために使用されます。ただし、他のタイプのキューを使用することで取り戻されるシンプルキューにはいくつかの制限があります。