C++ 標準テンプレート ライブラリ (STL) のキュー
キューは、先入れ先出し (FIFO) タイプの配置で動作するコンテナ アダプタの一種です。要素は後ろ（最後）に挿入され、前から削除されます。キューは deque のカプセル化されたオブジェクトを使用するか、 リスト (シーケンシャル コンテナ クラス) を基礎となるコンテナとして使用し、その要素にアクセスするための特定のメンバー関数のセットを提供します。
以下は、キューとそのさまざまなメソッドを示す例です。
CPP
// CPP code to illustrate Queue in> // Standard Template Library (STL)> #include> #include> using> namespace> std;> // Print the queue> void> showq(queue <> int> >gq)>> {> > queue <> int> >g = gq;>> < < g.front();> > g.pop();> > }> > cout < <> '
'> ;> }> // Driver Code> int> main()> {> > queue <> int> >クイズ;>> ;> > showq(gquiz);> > cout < <> '
gquiz.size() : '> < < gquiz.size();> > cout < <> '
gquiz.front() : '> < < gquiz.front();> > cout < <> '
gquiz.back() : '> < < gquiz.back();> > cout < <> '
gquiz.pop() : '> ;> > gquiz.pop();> > showq(gquiz);> > return> 0;> }> |
出力
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
キューのメソッドは次のとおりです。
次の関数の時間計算量と定義は次のとおりです。
| キュー::空() | ○(1) |
| キュー::サイズ() | ○(1) |
| キュー::プレイス() | ○(1) |
| キュー::フロント() | ○(1) |
| キュー::バック() | ○(1) |
| キュー::プッシュ(g) | ○(1) |
| キュー::ポップ() | ○(1) |
| 方法 | 意味 |
|---|---|
| キュー::空() | キューが空かどうかを返します。キューが空の場合は true を返し、それ以外の場合は false を返します。 |
| キュー::サイズ() | キューのサイズを返します。 |
| キュー::スワップ() | 2 つのキューの内容を交換します。ただし、サイズは異なっていてもキューのデータ型は同じである必要があります。 |
| キュー::プレイス() | 新しい要素をキュー コンテナに挿入すると、新しい要素はキューの最後に追加されます。 |
| キュー::フロント() | キューの最初の要素への参照を返します。 |
| キュー::バック() | キューの最後の要素への参照を返します。 |
| キュー::プッシュ(g) | 要素「g」をキューの最後に追加します。 |
| キュー::ポップ() | キューの最初の要素を削除します。 |
その他のメソッド用の C++ プログラム
C++
// CPP code to illustrate Queue operations in STL> // Divyansh Mishra -->divyanshmishra101010>> #include> #include> using> namespace> std;> // Print the queue> void> print_queue(queue <> int> >q)> {> > queue <> int> >温度 = q;>> ;> > temp.pop();> > }> > cout < <> '
'> ;> }> // Driver Code> int> main()> {> > queue <> int> >q1;>> ;> > print_queue(q1);> > > queue <> int> >q2;>> ;> > print_queue(q2);> > > > q1.swap(q2);> > > cout < <> 'After swapping, the first queue is : '> ;> > print_queue(q1);> > cout < <> 'After swapping the second queue is : '> ;> > print_queue(q2);> > > cout |
出力
The first queue is : 1 2 3 The second queue is : 4 5 6 After swapping, the first queue is : 4 5 6 After swapping the second queue is : 1 2 3 0
このコードの操作の時間と空間の複雑さは次のとおりです。
プリントキュー関数:
時間計算量: O(n)、n はキュー内の要素の数です。
空間複雑度: O(n)、n はキュー内の要素の数です。
q1.push(1)、q1.push(2)、q1.push(3)、q2.push(4)、q2.push(5)、q2.push(6):
時間計算量: プッシュ操作ごとに O(1)。
空間複雑度: O(n)、n は両方のキュー内の要素の合計数です。
q1.swap(q2):
時間計算量: スワップ操作ごとに O(1)。
スペース複雑さ: O(1)、この操作は 2 つのキューの内部ポインターを交換するだけであるため。
q1.empty():
時間計算量: O(1)、この操作はキューが空かどうかを単にチェックするだけであるため。
スペースの複雑さ: O(1)。この操作には余分なスペースが使用されません。
全体として、このコードの時間と空間の複雑さは、一般的な使用例では妥当で効率的です。
C++ キューに関する最近の記事
