メニュー

イラスト付きのC ++でのデータ構造のキュー

queue data structure c with illustration

イラスト付きのC ++でのキューの簡単な紹介。

キューは、スタックと同じように基本的なデータ構造です。 LIFOアプローチを使用するスタックとは対照的に、キューはFIFO（先入れ先出し）アプローチを使用します。このアプローチでは、キューに追加される最初のアイテムが、キューから削除される最初のアイテムになります。 Stackと同様に、キューも線形データ構造です。

現実の例えでは、乗客が列または列でバスを待つバス列を想像することができます。その乗客がたまたま最初に来た人であるため、列の最初の乗客が最初にバスに乗ります。

ビジネスアナリストへのインタビューの質問

=> ここで人気のあるC ++トレーニングシリーズを読んでください。

C ++でキューに入れる

学習内容：

C ++でキューに入れる

ソフトウェア用語では、キューは、以下に示すように、要素のセットまたはコレクションとして表示できます。要素は直線的に配置されます。

キュー

キューの「前」と「後」の2つの端があります。キューが空の場合、両方のポインターが-1に設定されます。

「リア」エンドポインタは、要素がキューに挿入される場所です。キューに要素を追加/挿入する操作は「エンキュー」と呼ばれます。

「フロント」エンドポインタは、要素がキューから削除される場所です。キューから要素を削除/削除する操作は、「デキュー」と呼ばれます。

リアポインタの値がsize-1の場合、キューがいっぱいであると言います。フロントがnullの場合、キューは空です。

基本操作

キューのデータ構造には、次の操作が含まれます。

  • エンキュー： アイテムをキューに追加します。キューへのアイテムの追加は、常にキューの後ろで行われます。
  • デキュー： キューからアイテムを削除します。アイテムは常にキューの先頭から削除またはキューから取り出されます。
  • isEmpty： キューが空かどうかを確認します。
  • 一杯： キューがいっぱいかどうかを確認します。
  • ピーク： キューの先頭にある要素を削除せずに取得します。

エンキュー

このプロセスでは、次の手順が実行されます。

  • キューがいっぱいかどうかを確認します。
  • いっぱいの場合、オーバーフローエラーを生成して終了します。
  • それ以外の場合は、「リア」をインクリメントします。
  • 「rear」が指す場所に要素を追加します。
  • 成功を返します。

デキュー

デキュー操作は、次の手順で構成されます。

  • キューが空かどうかを確認します。
  • 空の場合は、アンダーフローエラーを表示して終了します。
  • それ以外の場合、アクセス要素は「フロント」によって示されます。
  • 「フロント」をインクリメントして、次にアクセス可能なデータをポイントします。
  • 成功を返します。

次に、キュー内の挿入および削除操作の詳細な図を示します。

図

キューへの挿入と削除の図

これは空のキューであるため、rearとemptyを-1に設定します。

次に、キューに1を追加します。その結果、リアポインタが1つ先に移動します。

エンキュー操作

次の図では、後部ポインターをさらに1つずつ前方に移動して、要素2をキューに追加しています。

要素2をキューに追加します

次の図では、要素3を追加し、後部ポインターを1だけ移動します。

要素3を追加

この時点で、フロントポインタが0にある間、リアポインタの値は2になります。thロケーション。

次に、フロントポインタが指す要素を削除します。フロントポインタが0にあるため、削除される要素は1です。

デキュー操作

したがって、キューに入力された最初の要素、つまり1は、キューから削除された最初の要素です。その結果、最初のデキューの後、フロントポインタは次の場所である1のt0より先に移動します。

キューの配列実装

C ++を使用してキューデータ構造を実装しましょう。

#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue[MAX_SIZE], front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue[rear] = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue[i] << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }

出力：

キューが空です!!
作成されたキュー：
10 20 30 40 50
キューがいっぱいです！
フロント= 0
キュー要素：10 20 30 40 50
リア= 4

削除済み=> myqueueから10
フロント= 1
キュー要素：20 30 40 50
リア= 4

上記の実装は、配列として表されたキューを示しています。配列のmax_sizeを指定します。また、エンキュー操作とデキュー操作、およびisFull操作とisEmpty操作も定義します。

以下に示すのは、キューデータ構造のJava実装です。

// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue[]; public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int[this.max_size]; } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue[this.rear] = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue[this.front]; this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue[this.front]; } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue[this.rear]; } } // main class class Main { public static void main(String[] args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(' Element ' + queue.dequeue() + ' dequeued from queue '); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }

出力：

作成されたキュー：
10 20 30 40
エレメント10がキューからデキューされました

フロントアイテムは20です
リアアイテムは40です

上記の実装は、C ++の実装に似ています。

次に、リンクリストを使用してC ++でキューを実装しましょう。

キューのリンクリストの実装：

#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : '

出力：

作成されたキュー：
10 20 30 40 50
キューから削除された要素は次のとおりです：10
1回の削除後のキュー：
20 30 40 50

スタック対キュー

スタックとキューは、データの格納に使用できる2次データ構造です。それらは、配列やリンクリストなどの主要なデータ構造を使用してプログラムできます。両方のデータ構造について詳しく説明したので、次に、これら2つのデータ構造の主な違いについて説明します。

Wi-Fiのネットワークキーは何ですか
スタックキュー
LIFO（後入れ先出し）アプローチを使用します。FIFO（先入れ先出し）アプローチを使用します。
アイテムは、スタックの「トップ」と呼ばれる一方の端からのみ追加または削除されます。アイテムはキューの「後」の端から追加され、キューの「前」から削除されます。
スタックの基本的な操作は「プッシュ」と「ポップ」です。キューの基本的な操作は、「エンキュー」と「デキュー」です。
スタックの最上位にアクセスするためのポインターを1つだけ維持することで、スタック上のすべての操作を実行できます。キューでは、2つのポインターを維持する必要があります。1つはキューの前部にアクセスし、もう1つはキューの後部にアクセスします。
スタックは主に再帰的な問題を解決するために使用されます。キューは、順序付けられた処理に関連する問題を解決するために使用されます。

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

以下では、キューデータ構造のさまざまなアプリケーションについて説明します。

  • キューのデータ構造は、さまざまなCPUおよびディスクのスケジューリングで使用されます。ここでは、CPUまたはディスクを同時に必要とする複数のタスクがあります。 CPUまたはディスクの時間は、キューを使用してタスクごとにスケジュールされます。
  • キューは、印刷ジョブの数がキューに配置される印刷スプーリングにも使用できます。
  • リアルタイムシステムでの割り込みの処理は、キューデータ構造を使用して行われます。割り込みは、到着した順に処理されます。
  • 次のレベルに移動する前にツリーの隣接ノードがトラバースされる幅優先探索では、実装にキューが使用されます。
  • コールセンターの電話システムは、キューを使用して、サービス担当者が応答するまで通話を保留します。

一般に、キューデータ構造は、リソースまたはアイテムを到着順に処理する必要がある場合、つまり先入れ先出し法で使用されると言えます。

結論

キューはFIFO（先入れ先出し）データ構造であり、主にスケジューリングが必要なリソースで使用されます。両端に前後に2つのポインタがあり、これらはそれぞれ要素を挿入したり、要素をキューに出し入れしたりするために使用されます。

次のチュートリアルでは、優先キューや循環キューなど、キューの拡張機能について学習します。

=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。

推奨読書

^