キューに似ているのは、データを保存するために操作が実行される特定の順序に従う線形データ構造です。順序は先入れ先出しです (先入れ先出し) 。キューとは、列の先頭から順番に何かを受け取るのを待っている人々の列として想像できます。これは順序付きリストであり、挿入は後部と呼ばれる一方の端で行われ、削除は前部と呼ばれるもう一方の端で行われます。キューの良い例は、最初に来たコンシューマが最初に処理されるリソースのコンシューマのキューです。
スタックとキューの違いは削除にあります。スタックでは、最後に追加された項目を削除します。キューでは、最も最近追加された項目を削除します。
キューのデータ構造
キューの基本操作:
- enqueue(): キューの最後、つまり後端に要素を挿入します。 dequeue(): この操作は、キューのフロントエンドにある要素を削除して返します。 front(): この操作は、フロントエンドの要素を削除せずに返します。 Rear(): この操作は後端の要素を削除せずに返します。 isEmpty(): この操作は、キューが空かどうかを示します。 isFull(): この操作は、キューがいっぱいかどうかを示します。 size(): この操作はキューのサイズ、つまりキューに含まれる要素の合計数を返します。
キューの種類:
- シンプル キュー: リニア キューとも呼ばれるシンプル キューは、キューの最も基本的なバージョンです。ここで、要素の挿入、つまりエンキュー操作はリアエンドで行われ、要素の削除、つまりデキュー操作はフロントエンドで行われます。ここでの問題は、前からアイテムをポップし、後ろがキューの容量に達した場合、前に空のスペースがあるにもかかわらず、キューがいっぱいではないことを意味しますが、 isFull() 関数の条件に従って、その場合、キューはいっぱいです。この問題を解決するために、循環キューを使用します。
- 循環キュー : 循環キューでは、キューの要素は循環リングとして機能します。循環キューの動作は、最後の要素が最初の要素に接続されることを除いて、線形キューと似ています。その利点は、メモリがより適切に利用されることです。これは、空のスペースがある場合、つまりキュー内の特定の位置に要素が存在しない場合、モジュロ容量を使用してその位置に要素を簡単に追加できるためです( %n ）。
- 優先キュー : このキューは特殊なタイプのキューです。その特徴は、何らかの優先順位に基づいて要素をキューに配置することです。優先順位は、最も高い値を持つ要素が優先されるため、値の降順でキューが作成されます。優先順位は、最も低い値を持つ要素が最も高い優先順位を取得するようにすることもでき、その結果、値の昇順でキューが作成されます。事前定義優先キューでは、C++ では最も高い値が優先されますが、Java では最も低い値が優先されます。
- それに応じて : デキューはダブルエンドキューとも呼ばれます。名前が両端を示唆しているように、要素はキューの両端から挿入または削除できることを意味します。これは、一方の端からのみ実行できる他のキューとは異なります。この性質のため、先入れ先出しの性質に従わない場合があります。
キューの用途:
キューは、すぐに処理する必要はないが、後で処理する必要がある場合に使用されます。 F 最初に 私 n F 最初に ○ 注文してください 幅優先検索 。 Queue のこのプロパティは、次のようなシナリオでも役立ちます。
- リソースが複数のコンシューマー間で共有される場合。例には、CPU スケジューリング、ディスク スケジューリングが含まれます。 2 つのプロセス間でデータが非同期に転送される場合 (データは送信速度と同じ速度で受信される必要はない)。例には、IO バッファ、パイプ、ファイル IO などが含まれます。キューは、他のさまざまなデータ構造の必須コンポーネントとして使用できます。
Queue の配列実装:
キューを実装するには、フロントとリアの 2 つのインデックスを追跡する必要があります。項目を後方にエンキューし、項目を前方からデキューします。単純に前後のインデックスをインクリメントすると、問題が発生する可能性があり、前が配列の最後に到達する可能性があります。この問題の解決策は、前後を円形に増やすことです。
エンキューの手順:
- キューがいっぱいかどうかを確認してください
- いっぱいの場合は、オーバーフローを印刷して終了します
- キューがいっぱいでない場合は、末尾をインクリメントして要素を追加します
デキューの手順:
- キューが空かどうかを確認してください
- 空の場合、アンダーフローを出力して終了します
- 空でない場合は、要素を先頭に印刷し、先頭をインクリメントします
上記の操作をキューに実装するプログラムは次のとおりです。
C++
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->容量 = 容量;>>' >// This is important, see the enqueue> >queue->リア = 容量 - 1;>>' new> int>[queue->容量];>> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->サイズ == キュー -> 容量);>> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->サイズ == 0);>>' // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->リア = (キュー -> リア + 1)>> >% queue->容量;>> >queue->サイズ = キュー->サイズ + 1;>> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->配列[キュー->フロント];>> >queue->フロント = (キュー->フロント + 1)>> >% queue->容量;>> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->配列[キュー->フロント];>> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->配列[キュー->後];>> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->容量 = 容量;>>' >// This is important, see the enqueue> >queue->リア = 容量 - 1;>>' int>*)>malloc>(> >queue->容量 *>>'int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->サイズ == キュー->容量);>> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->サイズ == 0);>>' // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->リア = (キュー -> リア + 1)>> >% queue->容量;>> >queue->サイズ = キュー->サイズ + 1;>> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->配列[キュー->フロント];>> >queue->フロント = (キュー->フロント + 1)>> >% queue->容量;>> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->配列[キュー->フロント];>> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->配列[キュー->後部];>> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
>
ジャワ
postgresのシリアル
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
>
JavaScript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
ベッドページのようなサイト
>出力
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
複雑さの分析:
- 時間計算量
| オペレーション | 複雑 |
|---|---|
| エンキュー(挿入) | ○(1) |
| デキュー(削除) | ○(1) |
| フロント(前に出る) | ○(1) |
| リア(リアを取得) | ○(1) |
| IsFull(キューがいっぱいかどうかを確認します) | ○(1) |
| IsEmpty(キューが空かどうかチェック) | ○(1) |
- 補助スペース:
O(N) ここで、N は要素を格納するための配列のサイズです。
配列実装の利点:
- 実装が簡単。
- 大量のデータを簡単に効率的に管理できます。
- 先入れ先出しルールに従うため、挿入や削除などの操作が簡単に実行できます。
配列実装の欠点:
- 静的データ構造、固定サイズ。
- キューに多数のエンキュー操作とデキュー操作がある場合、ある時点で (フロント インデックスとリア インデックスが線形に増加する場合)、キューが空であってもキューに要素を挿入できなくなる可能性があります (この問題は回避されます)循環キューを使用する)。
- キューの最大サイズは事前に定義する必要があります。