C++容器の使い方紹介——stack

C++容器の使い方紹介——stack
cplusplusから翻訳
テキストリンク
一、紹介
stackはコンテナアダプタ(STLのコンテナはシーケンスコンテナと関連コンテナに分けられ、コンテナアダプタは、これら2種類のコンテナを包装して得られるより強い拘束力を持つコンテナ)であり、先進的な後出(FILO)構造を操作するシナリオに用いられるように設計されており、この場合、要素の挿入と削除はいずれも容器の末尾でしか行われない.
stackはコンテナアダプタによって実現され、特定のコンテナクラスをその最下層のコンテナとするクラスであり、特定のメンバー関数を提供して自分の要素にアクセスし、要素はこの特定のコンテナの後ろ、すなわちスタックの上部でのみ、スタックの出入りとスタックの進入操作を行うことができる.
最下層のコンテナは、任意の標準的なコンテナテンプレートクラス、または明確な目的を持つコンテナクラスであり、以下の操作をサポートする必要があります.

empty(空か否か判断)

size(戻りスタックの要素数)

back(スタックトップ要素を返す)

push_back

pop_back

標準的なコンテナクラス、たとえば
vector,deque,list,以上のニーズを満たす.使用するコンテナが明示的に指定されていない場合は、デフォルトで使用されます.
deque.
二、関数の使い方の例
1、構造と分析(C++11バージョン)

initialize (1)          explicit stack (const container_type& ctnr);

move-initialize (2)     explicit stack (container_type&& ctnr = container_type());

allocator (3)           template  explicit stack (const Alloc& alloc);

init + allocator (4)    template  stack (const container_type& ctnr, const Alloc& alloc);

move-init + allocator (5)  template  stack (container_type&& ctnr, const Alloc& alloc);

copy + allocator (6)    template  stack (const stack& x, const Alloc& alloc);

move + allocator (7)    template  stack (stack&& x, const Alloc& alloc);

(1)初期化構造方式
内部要素がctnrのコピーであるコンテナアダプタを構築する
(2)move-initialization constructor
内部要素を構築するにはctnrの値を移動で取得するコンテナアダプタ
あといくつかの分配器付きの私はまだ理解していないので、でたらめを言わないでください.
cplusplusの例:

// constructing stacks
#include        // std::cout
#include           // std::stack
#include          // std::vector
#include           // std::deque

int main ()
{
  std::deque mydeque (3,100);          // deque with 3 elements
  std::vector myvector (2,200);        // vector with 2 elements

  std::stack first;                    // empty stack
  std::stack second (mydeque);         // stack initialized to copy of deque

  std::stack > third;  // empty stack using vector
  std::stack > fourth (myvector);

  std::cout << "size of first: " << first.size() << '
';
  std::cout << "size of second: " << second.size() << '
';
  std::cout << "size of third: " << third.size() << '
';
  std::cout << "size of fourth: " << fourth.size() << '
';

  return 0;
}

2、empty()
現在のスタックが空であるかどうかを返します(サイズが0の場合)、empty()関数はスタックを空にすることはできません.bool型のconst関数を返します.

    stacks;
    s.push(1);
    s.push(2);
    cout << s.empty() << endl;   //  0

3、size()
コンテナ内の要素の数、時間複雑度O(1)を返し、戻り値タイプはsize_type、すなわちunsigned intです.size()関数ではスタックのサイズを変更できません
例えば上のコードセグメントは2を出力すべきである.
4、top()
スタックトップ要素の参照を返します.
スタックは先進的な後出構造であるため、最上部の要素は最後にスタックに挿入された要素である.
(
C++11では、要素タイプに応じてreferenceまたはconst_が自動的に返されます.referenceは、空のスタックに対してtop関数を呼び出すと異常に終了するので、empty()関数を使用して事前にチェックする必要があります.

    stacks;
    s.push(1);
    s.push(2);
    cout << s.top() << endl;    //  2
    s.top() += 3;               //        
    cout << s.top() << endl;    //  5

5、push()とemplace()(C++11)
push()関数と
Emplace()は、スタックというコンテナの上部に新しい要素を挿入します.
push()は、実際に呼び出された下位コンテナの
push_back()関数、新しい要素の値は
push関数パラメータのコピー.
Emplace()は、実際に呼び出された下位コンテナの
emplace_back()関数では、新しい要素の値はコンテナ内部でその場で構築され、移動やコピーは必要ありません.
stack
Emplaceは通常の基本タイプでも使用できます.

struct Node
{
    Node(int x)
        :x(x){}
    int x;
};

int main()
{
    stacks1;
    s1.emplace(1);
    s1.push(Node(2));

    stacks2;
    s2.emplace(1);   //OK
    return 0;
}

6、pop()
最上部の要素を削除し、スタックのサイズを小さくします.
この削除された要素は、スタックに挿入されたばかりの要素で、top関数の戻り値と一致しています.この関数はオブジェクトの構造関数(もしあれば)を呼び出し、pop()は実際には下位コンテナのpop_を使用しています.back()関数で実現されます.
(空のスタックにpop()を行うと、プログラムが異常に終了し、emptyを使用して事前にチェックする必要があります)

    stacks;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.top() << endl;   //3
    s.pop();
    cout << s.top() << endl;   //2

スタックにはclearまたはerase関数はありません.スタックを空にするには、スタック関数をループ的に呼び出す必要があります.

    stacks;
    //s.erase(); //error
    //s.clear(); //error
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.size() << endl;   //3
    while(!s.empty())
        s.pop();
    cout << s.size() << endl;    //0

7、swap()
2つのスタックの内容(すべての要素)を交換し,この関数は非メンバー関数swap()によって下位コンテナを交換し,時間複雑度O(1)
cplusplusの例

// stack::swap
#include        // std::cout
#include           // std::stack

int main ()
{
  std::stack foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() << '
';
  std::cout << "size of bar: " << bar.size() << '
';

  return 0;
}

8、演算子の再ロード

(1)==           ，          ，     operator ==          ，              

template 
  bool operator== (const stack& lhs, const stack& rhs);
(2)!=  ==    。                        
	

	template 

	  bool operator!= (const stack& lhs, const stack& rhs);

	

	(3)                     ，             ，      。   

	

	template 

	  bool operator& lhs, const stack& rhs);

	

	(4)    

	

	template 

	  bool operator<= (const stack& lhs, const stack& rhs);

	

	(5)    

	

	template 

	  bool operator>  (const stack& lhs, const stack& rhs);

	

	(6)    

	

	template 

	  bool operator>= (const stack& lhs, const stack& rhs);

	

    stackl1;
    l1.emplace(1);
    l1.emplace(2);
    l1.emplace(3);
    stackl2;
    l2.emplace(1);
    l2.emplace(2);
    cout << boolalpha << (l1 > l2) << endl;   //T
    cout << boolalpha << (l1 == l2) << endl;   //F
    cout << boolalpha << (l1 != l2) << endl;   //T

四、結びの言葉
スタックは特によく使われるデータ構造であり、様々なプログラミング言語やオペレーティングシステムの内部で見られる.一般的なDFSアルゴリズム、再帰アルゴリズム;コンテキスト切替、プロセススケジューリング、レジスタ自体.