logo

TechCodeview

C++ STL でのスタック

スタックは、LIFO (Last In First Out) タイプの動作を持つコンテナー アダプターの一種であり、新しい要素が一方の端 (最上部) に追加され、要素はその端からのみ削除されます。スタックは、次のいずれかのカプセル化されたオブジェクトを使用します。 ベクター または deque (デフォルト) または リスト (シーケンシャル コンテナ クラス) を基礎となるコンテナとして使用し、その要素にアクセスするための特定のメンバー関数のセットを提供します。

カジャル・アガルワル

スタックとキューの基本的な違いを覚えるのが混乱している場合は、この区別について実際の例を考えてください。スタック、本の積み重ねの場合は一番上の本を簡単に取ることができ、キューの場合は列の先頭に並ばなければならないときを思い出してください。現金を取り出すためにATMの近くにいる最初の人は、ATMからお金を引き出す最初の機会を持ちます。つまり、キューは FIFO (First In First Out) タイプで動作します。



スタック構文:-

スタックを作成するには、コードにヘッダー ファイルを含める必要があります。次に、この構文を使用して std::stack を定義します。

テンプレートクラススタック。

タイプ – は、std::stack に含まれる要素の Type です。任意の有効な C++ 型またはユーザー定義型を使用できます。



容器 – は、基礎となるコンテナ オブジェクトのタイプです。

メンバーの種類:-

value_type - 最初のテンプレート パラメータ T。要素のタイプを示します。



container_type - 2 番目のテンプレート パラメーター、コンテナー。これは、基礎となるコンテナのタイプを示します。

size_type - 符号なし整数型。

スタックに関連付けられた関数は次のとおりです。
empty() – スタックが空かどうかを返します – 時間計算量 : O(1)
size() – スタックのサイズを返す – 時間計算量 : O(1)
top() – スタックの最上位要素への参照を返します – 時間計算量 : O(1)
Push(g) – スタックの先頭に要素「g」を追加 – 時間計算量 : O(1)
Pop() – スタックの最後に入力された要素を削除します – 時間計算量 : O(1)

C++




#include> #include> using> namespace> std;> int> main() {> >stack<>int>>スタック;>>' stack.push(21);>// The values pushed in the stack should be of the same data which is written during declaration of stack> >stack.push(22);> >stack.push(24);> >stack.push(25);> >int> num=0;> >stack.push(num);> >stack.pop();> >stack.pop();> >stack.pop();> > >while> (!stack.empty()) {> >cout << stack.top() <<>' '>;> >stack.pop();> >}> }> 

>

>

出力

22 21>

時間計算量: このプログラムの時間計算量は O(N) です。ここで、N はスタック内の要素の総数です。 while ループは N 回繰り返し、スタックから要素をポップして出力します。

空間の複雑さ: このプログラムの空間複雑さは O(N) です。ここで、N はスタック内の要素の総数です。スタック データ構造は、そこに格納されている要素の数に比例したスペースを使用します。この場合、スタックの最大サイズは 5 であるため、空間複雑度は一定であり、同様に O(1) と考えることができます。

Javaにおける文字列の等価性

コードの説明:

  1. iostream ヘッダー ファイルをインクルードするか、その関数を使用するコードにインクルードします。
  2. スタック ヘッダー ファイルをコードに組み込み、その関数を使用します。すでに組み込まれている場合は、すでに関数が組み込まれているため、スタック ヘッダー ファイルは必要ありません。
  3. std 名前空間をコードに含めると、そのクラスを呼び出さずに使用できます。
  4. main() 関数を呼び出します。プログラム ロジックはこの関数内に追加する必要があります。
  5. 整数値を格納するスタックを作成します。
  6. Push() 関数を使用して、値 21 をスタックに挿入します。
  7. Push() 関数を使用して、値 22 をスタックに挿入します。
  8. Push() 関数を使用して、値 24 をスタックに挿入します。
  9. Push() 関数を使用して、値 25 をスタックに挿入します。
  10. 変数値を入力するには、整変数 num を使用します。ここでは値は 0 ですが、cin>> num を使用して任意の整数値を割り当てることができます。
  11. Push() 関数を使用して、num 変数の値を挿入します。
  12. Pop() 関数を使用して、スタックから最上位の要素、つまり 25 を削除します。最上位の要素は 24 になります。
  13. Pop() 関数を使用して、スタックから最上位の要素、つまり 24 を削除します。最上位の要素は 22 になります。
  14. while ループと empty() 関数を使用して、スタックが空でないかどうかを確認します。 ！は NOT 演算子です。したがって、スタックが空でない場合、empty() 関数は false を返し、NOT 演算子はそれを true に変換し、while ループが実行され続けます。ただし、スタックが空になると、empty() 関数は true を返し、NOT 演算子はそれを false にし、ループは終了します。
  15. スタックの現在の内容をコンソールに出力します。
  16. スタック上で Pop() 関数を呼び出します。
  17. while ループの本体の終わり。
  18. main() 関数本体の終わり。

スタックの機能一覧：

  • C++ STL の stack::top()
  • C++ STL の stack::empty() および stack::size()
  • C++ STL の stack::push() および stack::pop()
  • C++ STL の stack::swap()
  • C++ STL の stack::emplace()
  • C++ スタックに関する最近の記事