スタック（Stack）

スタックはLIFO（Last In First Out）のデータ構造であり、コンテナアダプタとして実装されます。標準ライブラリではstd::stackが提供されており、主な操作は以下の通りです。

最小スタックの実装

定数時間で最小値を取得できるスタックです。2つのスタックを用意し、片方にデータを、もう片方に現在の最小値を管理します。

class MinStack {
private:
    std::stack<int> dataStack;
    std::stack<int> minStack;

public:
    void push(int val) {
        dataStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (dataStack.top() == minStack.top()) {
            minStack.pop();
        }
        dataStack.pop();
    }

    int top() { return dataStack.top(); }
    int getMin() { return minStack.top(); }
};

スタックを用いたキューのシミュレーション

2つのスタック（入力用・出力用）を組み合わせることで、キュー（FIFO）の動作を実現できます。出力用スタックが空のときに入力用スタックの要素をすべて移すことで、順序が反転しキューの先頭要素が取得可能になります。

class MyQueue {
private:
    std::stack<int> inputSt;
    std::stack<int> outputSt;

    void transfer() {
        if (outputSt.empty()) {
            while (!inputSt.empty()) {
                outputSt.push(inputSt.top());
                inputSt.pop();
            }
        }
    }

public:
    void push(int x) { inputSt.push(x); }
    
    int pop() {
        transfer();
        int val = outputSt.top();
        outputSt.pop();
        return val;
    }

    int peek() {
        transfer();
        return outputSt.top();
    }

    bool empty() { return inputSt.empty() && outputSt.empty(); }
};

コンテナアダプタとしての実装

スタックは特定のコンテナ（vectorやlistなど）のインターフェースを制限・変換して提供する「アダプタ」パターンです。デフォルトではdequeが使用されますが、テンプレート引数で変更可能です。

template<class T, class Container = std::deque<T>>
class Stack {
private:
    Container c;
public:
    void push(const T& val) { c.push_back(val); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

キュー（Queue）

キューはFIFO（First In First Out）のデータ構造です。std::queueはpush（末尾へ追加）、pop（先頭から削除）、front（先頭へアクセス）、back（末尾へアクセス）などの操作を提供します。ランダムアクセスが不要なため、vectorよりもlistやdequeが適しています。

template<class T, class Container = std::deque<T>>
class Queue {
private:
    Container c;
public:
    void push(const T& val) { c.push_back(val); }
    void pop() { c.pop_front(); }
    T& front() { return c.front(); }
    T& back() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

双方向キュー（Deque）

std::deque（Double-Ended Queue）は、先頭および末尾での要素の挿入・削除がO(1)で行えるデータ構造です。vectorのような連続メモリ空間のように振る舞いますが、内部的には複数の固定サイズバッファ（チャンク）をポインタ配列（マップ）で管理する構造になっています。

• 構造: 中央制御配列が各バッファへのポインタを保持します。これにより、先頭への追加時は新しいバッファを確保するだけでよく、既存の要素の移動が不要です。
• 特徴: vectorに比べて先頭への挿入が高速で、listに比べてメモリの局所性が高くキャッシュ効率が良いです。ただし、中間への挿入・削除はO(n)となり、vectorほど高速なランダムアクセスではありません。

優先度付きキュー（Priority Queue）

std::priority_queueは、要素が優先度順に並べられるキューです。内部的にはヒープ構造が使用され、最大値（または最小値）の取得が高速に行えます。デフォルトではvectorをコンテナとして使用し、降順（大トップヒープ）でソートされます。

関数オブジェクト（ファンクタ）と比較

順序を制御するために、テンプレート引数に関数オブジェクト（ファンクタ）を渡します。例えば、昇順（小トップヒープ）にするにはstd::greaterを使用します。

// 降順（デフォルト）
std::priority_queue<int> pq_desc;
pq_desc.push(3); pq_desc.push(1); pq_desc.push(4);
// 出力: 4, 3, 1

// 昇順
std::priority_queue pq_asc;
pq_asc.push(3); pq_asc.push(1); pq_asc.push(4);
// 出力: 1, 3, 4

シミュレーション実装

優先度付きキューを実装する際は、ヒープの性質を維持するために要素の追加時には「上方修正」、削除時には「下方修正」を行います。

template<class T, class Container = std::vector<T>, class Compare = std::less<T>>
class MyPriorityQueue {
private:
    Container cont;
    Compare comp;

    void siftUp(size_t idx) {
        while (idx > 0) {
            size_t parent = (idx - 1) / 2;
            if (comp(cont[parent], cont[idx])) {
                std::swap(cont[parent], cont[idx]);
                idx = parent;
            } else {
                break;
            }
        }
    }

    void siftDown(size_t idx) {
        size_t n = cont.size();
        while (true) {
            size_t left = 2 * idx + 1;
            size_t right = 2 * idx + 2;
            size_t target = idx;

            if (left < n && comp(cont[target], cont[left])) target = left;
            if (right < n && comp(cont[target], cont[right])) target = right;

            if (target != idx) {
                std::swap(cont[idx], cont[target]);
                idx = target;
            } else {
                break;
            }
        }
    }

public:
    void push(const T& val) {
        cont.push_back(val);
        siftUp(cont.size() - 1);
    }

    void pop() {
        if (cont.empty()) return;
        std::swap(cont.front(), cont.back());
        cont.pop_back();
        siftDown(0);
    }

    const T& top() const { return cont.front(); }
    bool empty() const { return cont.empty(); }
};

カスタムクラスでの利用

自作クラスを優先度付きキューで扱う場合、比較演算子のオーバーロードが必要です。ポインタを格納する場合は、ポインタのアドレス比較を避けるためにカスタムの比較ファンクタを定義します。

struct Task {
    int priority;
    std::string name;
    // タスクの優先度が高い方を「小さい」と定義する場合など
    bool operator>(const Task& other) const {
        return priority > other.priority;
    }
};

// ポインタ用ファンクタ
struct TaskPtrCompare {
    bool operator()(const Task* a, const Task* b) const {
        return a->priority > b->priority; // 優先度が高い順
    }
};

反復子アダプタ（Reverse Iterator）

コンテナの反復処理方向を逆にするのが反復子アダプタです。rbegin()は最後尾の要素を指し、rend()は先頭の前（理論上の位置）を指します。実装においては、既存の正向イテレータをラップし、進行方向（++と--）を逆転させる設計が一般的です。

template<class Iterator, class Ref, class Ptr>
class ReverseIterator {
private:
    Iterator current;
public:
    using Self = ReverseIterator;

    ReverseIterator(Iterator it) : current(it) {}

    Ref operator*() const {
        Iterator tmp = current;
        --tmp;
        return *tmp; // 一つ手前の要素を返す
    }

    Self& operator++() {
        --current;
        return *this;
    }

    Self operator++(int) {
        Self tmp = *this;
        --current;
        return tmp;
    }

    bool operator!=(const Self& other) const {
        return current != other.current;
    }
};

このアダプタをリストなどのコンテナクラスに組み込むことで、rbegin()やrend()が使用可能になります。例えば、rbegin()はend()を、rend()はbegin()をそれぞれ反復子アダプタに渡して生成します。