Stackはデータ要素をプッシュしたりポップしたりするために一方の端だけを開いています。一方、Queueはデータ要素をエンキューおよびデキューするために両方の端を開いています。
スタックとキューは、データ要素を格納するために使用されるデータ構造であり、実際には同等の現実世界に基づいています。 たとえば、スタックはCDのスタックで、CDのスタックの一番上からCDを出し入れすることができます。 同様に、キューは、最初に立った人、すなわちキューの前に立っている人が最初にサービスされ、到着した新しい人がキューの後ろ（キューの後端）に現れるシアターチケット用のキューです。
比較表
| 比較基準 | スタック | キュー |
|---|---|---|
| 動作原理 | LIFO（後入れ先出し） | FIFO（先入れ先出し） |
| 構造 | 要素の挿入と削除にも同じ終わりが使用されます。 | 一方の端部は挿入に使用され、すなわち後端部であり、他方の端部は要素の削除に使用され、すなわち前端部である。 |
| 使用されているポインターの数 | 1 | 2つ（単純キューの場合） |
| 実行した操作 | プッシュアンドポップ | エンキューとデキュー |
| 空き状況の検討 | トップ== -1 | フロント== -1 || フロント==リア+ 1 |
| 満腹検査 | トップ==最大 - 1 | 背面==最大 - 1 |
| 変種 | バリアントはありません。 | それは循環キュー、優先度キュー、二重終了キューのようなバリアントを持っています。 |
| 実装 | もっと簡単 | 比較的複雑 |
スタックの定義
スタックは、非プリミティブな線形データ構造です。 これは、新しい項目が追加され、既存の要素が一方の端からのみ削除される順序付きリストです。これはスタックの先頭（TOS）と呼ばれます。 スタックへの削除と挿入はすべてスタックの先頭から行われるため、最後に追加された要素がスタックから削除される最初の要素になります。 それが、スタックが後入れ先出し（LIFO）タイプのリストと呼ばれる理由です。
スタック内で頻繁にアクセスされる要素は一番上の要素ですが、最後に使用可能な要素はスタックの一番下にあります。
例
あなたの何人かはビスケット（またはポピンズ）を食べるかもしれません。 あなたが仮定するならば、カバーの片側だけが引き裂かれます、そして、ビスケットは一つずつ取り出されます。 これはポップと呼ばれるもので、同様に、後でしばらくの間ビスケットを保存したい場合は、プッシュと呼ばれる同じ破れた端を通してそれらをパックに戻すことになります。
キューの定義
キューは、非プリミティブ型のカテゴリに入る線形データ構造です。 それは似たタイプの要素の集まりです。 新しい要素の追加は後端と呼ばれる一端で行われます。 同様に、既存の要素の削除はフロントエンドと呼ばれるもう一方の端で行われ、それは論理的に先入れ先出し（FIFO）タイプのリストです。
例
日々の生活の中で、私たちは希望するサービスを待つために外出する多くの状況に出くわします、そこで我々はサービスを受けるために私たちの番のために待ち行列に入る必要があります。 この待機キューは、キューと見なすことができます。
スタックとキューの主な違い
- スタックはLIFOメカニズムに従うのに対して、キューは要素を追加および削除するためにFIFOメカニズムに従います。
- スタックでは、要素の挿入と削除に同じ終わりが使用されます。 反対に、要素を挿入および削除するために、キュー内で2つの異なる端が使用されます。
- スタックにはオープンエンドが1つしかないため、スタックの最上部を参照するために1つのポインタだけを使用する理由です。 しかし、キューはキューの前端と後端を参照するために2つのポインタを使用します。
- スタックでは、キュー内ではエンキューとデキューとして知られる、プッシュとポップとして知られる2つの操作を実行します。
- スタックの実装は簡単ですが、Queueの実装は難しいです。
- キューには、循環キュー、優先度キュー、二重終了キューなどのバリアントがあります。対照的に、スタックにはバリアントがありません。
スタック実装
スタックは2つの方法で適用できます。
- 静的実装は配列を使用してスタックを作成します。 静的実装は、楽な手法ですが、スタックのサイズの宣言はプログラム設計中に行わなければならないため、柔軟な作成方法ではありません。その後、サイズを変更することはできません。 さらに、静的な実装はメモリ使用率に関してあまり効率的ではありません。 （スタックを実装するための）配列は、（プログラム設計時に）操作の開始前に宣言されているため。 ソートされる要素の数がスタック内で非常に少ない場合は、静的に割り当てられたメモリは無駄になります。 一方、スタックに格納する要素の数がそれ以上ある場合は、配列のサイズを変更して容量を増やすことができないため、新しい要素に対応できます。
- 動的実装はリンクリスト表現とも呼ばれ、ポインタを使用してデータ型のスタック型を実装します。
キュー実装
キューは2つの方法で実装できます。
- 静的実装 ：配列を使用してキューを実装する場合は、設計時または処理開始前に配列のサイズを宣言する必要があるため、キューに格納する要素の正確な数を事前に確認する必要があります。 この場合、配列の先頭がキューの先頭になり、配列の最後の位置がキューの末尾になります。 次の関係式は、配列を使用して実装された場合に、要素全体がキューに存在することを示します。
フロント - リア+ 1
“ rear <front”の場合、キューに要素はなく、キューは常に空になります。 - 動的実装 ：ポインタを使用してキューを実装する場合の主な欠点は、リンク表現内のノードが配列表現内の対応する要素よりも多くのメモリ領域を消費することです。 各ノードには少なくとも２つのフィールドがあるので、１つはデータフィールド用であり、もう１つは次のノードのアドレスを記憶するためであるが、リンク表現ではデータフィールドのみがある。 リンク表現を使用するメリットは、他の要素のグループの途中で要素を挿入または削除する必要がある場合に明らかになります。
スタック上の操作
スタック上で操作できる基本操作は以下のとおりです。
- PUSH ：新しい要素がスタックの最上部に追加されたときは、PUSH操作と呼ばれます。 新しい要素が一番上に挿入されるため、スタック内の要素を押すと要素の追加が呼び出されます。 各プッシュ操作の後、トップは1ずつ増えます。 配列がいっぱいで、新しい要素を追加できない場合は、STACK-FULL状態またはSTACK OVERFLOWと呼ばれます。 プッシュ操作 - Cの機能：
スタックを考慮すると、次のように宣言されます。int stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP ：要素がスタックの一番上から削除されると、POP操作と呼ばれます。 ポップ操作が行われるたびに、スタックは1ずつ減少します。 スタックに要素が残っていない状態でポップが実行されると、STACK UNDERFLOW状態になり、スタックが空になります。 POP操作 - Cの機能：
スタックを考慮すると、次のように宣言されます。int stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
キューに対する操作
キューで実行できる基本操作は以下のとおりです。
- Enqueue ：キューに要素を挿入します。C言語でオペレーション関数をエンキューします。
キューは次のように宣言されていますint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - デキュー ： キューから要素を削除します。C言語でオペレーション関数をエンキューします。
キューは次のように宣言されていますint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Stackの応用
- コンパイラで解析します。
- Java仮想マシン
- ワープロで元に戻します。
- Webブラウザの「戻る」ボタン
- プリンタ用のPostScript言語。
- コンパイラで関数呼び出しを実装する
キューの用途
- データバッファ
- 非同期データ転送（ファイルIO、パイプ、ソケット）
- 共有リソース（プリンタ、プロセッサ）に対する要求を割り当てます。
- 交通分析
- スーパーマーケットに持っているレジ係の数を決定します。
結論
スタックとキューは線形データ構造であり、動作メカニズム、構造、実装、バリアントなどの特定の点で異なりますが、両方ともリストへの要素の格納と要素の追加や削除などのリストに対する操作の実行に使用されます。 他のタイプのキューを使用することによって取り戻される単純なキューにはいくつかの制限がありますが。
