コンテナアダプタは、シーケンスコンテナをカプセル化し、特定のデータ構造の規則に従う異なるインターフェースを提供します。 この記事では、C++標準ライブラリに含まれている3つのコンテナアダプタ、スタック、キュー、優先度付きキューについて説明します。

スタック

スタックは、要素が後入れ先出し (LIFO)の原則に従うデータ構造で、最後にプッシュされた要素が最初にポップされます。 メモリ空間としてのスタックも、このLIFOの性質から名付けられています。スタックは、再帰的なアルゴリズムや、最新の要素へのアクセスが必要なやり直しや取り消し機能などにおいて便利なデータ構造です。

#include <stack>
 
using namespace std;
 
int main () {
 
    stack<int> st;
 
    st.push(3);
    st.push(5);
    st.push(6);
 
    cout << "top: " << st.top() << endl; // => top: 6
 
    st.pop();
    cout << "top: " << st.top() << endl; // => top: 5
 
 
    return 0;
}

上記のコードは、どのようにスタックを利用できるかを示しています。デフォルトでは、スタックはdeque上に実装されていますが、 stack<Type, Container<Type>>を使って、vectorやlistなど他の動的シーケンスコンテナに適用することもできます。 push操作は要素をトップに追加し、pop操作は要素をトップから削除し、LIFOの原則を強制します。

キュー

キューは、要素が先入れ先出し (FIFO)の原則に従うデータ構造で、最初にプッシュされた要素が最初にポップされます。 これは、店舗の前に最も長く待っていた顧客が最初に入店できる、顧客の列と同じように機能します。このデータ構造は、 タスクが到着した順序で順次処理する必要がある場合に便利で、プリンターキューの設定やオペレーティングシステムのタスクキュー、 ウェブサーバーがリクエストを順番に処理する場面などで使用されます。

#include <queue>
 
using namespace std;
 
int main () {
 
    queue<int> q;
 
    q.push(3);
    q.push(5);
    q.push(6);
 
    cout << "front: " << q.front() << endl; // => front: 3
 
    q.pop();
    cout << "front: " << q.front() << endl; // => front: 5
 
 
    return 0;
}

上記のコードは、どのようにキューを利用できるかを示しています。デフォルトでは、キューはdeque上に実装されていますが、 queue<Type, Container<Type>>を使用して他の動的シーケンスコンテナにも適用できます。インターフェースはスタックと非常に似ていますが、 用語が「トップ」や「ボトム」ではなく、「フロント」と「バック」として表現されている点が異なります。push操作は要素をキューのバックに追加し、 pop操作は要素をフロントから削除し、FIFOを実現します。

優先度付きキュー

優先度付きキューは、要素がその優先度に基づいて順序付けられるキューで、最も高い優先度の要素が最初にポップされます。 優先度付きキューは、タスクの優先順位が異なるタスクスケジューリングアルゴリズムを作成する場合などに最も便利です。

#using namespace std;
 
int main () {
 
    priority_queue<int> pq;
 
    pq.push(3);
    pq.push(5);
    pq.push(6);
 
    cout << "top: " << pq.top() << endl;
 
    pq.pop();
    cout << "top: " << pq.top() << endl;
 
    return 0;
}

上記のコードは、どのように優先度付きキューを利用できるかを示しています。デフォルトでは、優先度付きキューは昇順で要素を並べ替え、要素の順序を維持するためにヒープ上に実装されています（ヒープについては今後扱います）。 ヒープ自体は、最も高い優先度の要素にすぐに($O(1)$で)アクセスできるようにvector上に実装されています。

ただし、priority_queue<Type, Container<Type>, Order<Type>>を使用して他のコンテナや順序に切り替えることもできます。 例えば、priority_queue<int, deque<int>, greater<int>>を使うことで、int、deque、降順の使用を指定できます。 優先度付きキューは二分探索木上に構築されているため、挿入には$O(\log(n))$の時間がかかります。 同様に、最も高い優先度の要素の削除もツリーの再編成が必要な場合があるため、$O(\log(n))$の時間がかかります。

結論

この記事では、スタック、キュー、優先度付きキューがどのように機能するか、それらがどのように実装されているか、そしてどのように利用できるかについて説明しました。 この記事では操作の時間計算量についてはあまり詳しく説明しませんでしたが、将来の記事では、他のデータ構造やアルゴリズムと共により詳細に取り上げます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• Portfolio Courses. 2023. Stack Data Structure In STL | C++ Tutorial. YouTube.
• Portfolio Courses. 2023. Queue Data Structure In STL | C++ Tutorial. YouTube.
• GeeksforGeeks. 2024. Priority Queue in C++ Standard Template Library (STL). GeeksforGeeks.