線形データ構造の特性とC++標準ライブラリ設計

スタック（Stack）は「後入れ先出し（LIFO）」を原則とするデータアクセス機構であり、キュー（Queue）は「先入れ先出し（FIFO）」を採用する。C++標準ライブラリにおいて、std::stackおよびstd::queueはそれ自体がメモリ管理を行うコンテナではなく、既存のシーケンスコンテナ（既定ではstd::deque）を内部に保持するコンテナアダプタとして実装されている。これにより、開発者は要件に応じてstd::vectorやstd::listなどを底層コンテナとして差し替えることが可能である。

std::dequeは双方向キューとして設計されており、両端における要素の挿入・削除が定数時間で実行可能である。std::priority_queueは内部にヒープ構造を構築し、比較演算子に基づいて常に最大値（または最小値）へのO(1)アクセスを実現する。これらは競合プログラミングやシステム設計において頻繁に活用される基盤となる。

スタック・キューを用いた典型アルゴリズム

二つのスタックによるキュー動作の模倣

入力用スタックに要素を蓄積し、出力時には補助用スタックへ要素を移送することで順序を反転させる。出力用スタックが空の状況でのみ移送処理を行うため、均し計算量はO(1)を維持できる。

#include <stack>

class MyQueue {
private:
    std::stack<int> ingress_stack;
    std::stack<int> egress_stack;

    void transfer() {
        if (egress_stack.empty()) {
            while (!ingress_stack.empty()) {
                egress_stack.push(ingress_stack.top());
                ingress_stack.pop();
            }
        }
    }
public:
    MyQueue() = default;
    
    void push(int value) {
        ingress_stack.push(value);
    }
    
    int pop() {
        transfer();
        int front = egress_stack.top();
        egress_stack.pop();
        return front;
    }
    
    int peek() {
        transfer();
        return egress_stack.top();
    }
    
    bool empty() const {
        return ingress_stack.empty() && egress_stack.empty();
    }
};

キューを利用したスタック構造の実装

単一のキューを用い、push操作時に既存要素を回転させることで、キューの先頭が常に最新の要素と一致するように制御する。

#include <queue>

class MyStack {
private:
    std::queue<int> primary_q;
public:
    MyStack() = default;
    
    void push(int value) {
        primary_q.push(value);
        int rotate_count = primary_q.size() - 1;
        while (rotate_count--) {
            primary_q.push(primary_q.front());
            primary_q.pop();
        }
    }
    
    int pop() {
        int top_element = primary_q.front();
        primary_q.pop();
        return top_element;
    }
    
    int top() const {
        return primary_q.front();
    }
    
    bool empty() const {
        return primary_q.empty();
    }
};

括弧列の整合性検証

開き括弧をスタックに記録し、閉じ括弧が出現した時点で対応関係を照合する。スタックの空状態判定と末尾要素の検証を組み合わせることで、ネスト構造を含む有効性チェックを実現する。

#include <string>
#include <stack>
#include <unordered_map>

class Solution {
public:
    bool isValid(std::string sequence) {
        if (sequence.empty()) return true;
        const std::unordered_map<char, char> pair_map = {
            {')', '('}, {']', '['}, {'}', '{'}
        };
        std::stack<char> tracker;
        
        for (char current : sequence) {
            if (current == '(' || current == '[' || current == '{') {
                tracker.push(current);
            } else {
                if (tracker.empty() || tracker.top() != pair_map.at(current)) {
                    return false;
                }
                tracker.pop();
            }
        }
        return tracker.empty();
    }
};

隣接する重複文字の除去処理

文字を逐次スタックに投入し、最上位要素と一致した場合は相殺（ポップ）を行う。最終的にスタックに残った要素を逆順に連結することで、重複が除去された文字列を復元する。

#include <string>
#include <stack>
#include <algorithm>

class Solution {
public:
    std::string removeDuplicates(std::string input) {
        std::stack<char> buffer;
        for (char ch : input) {
            if (!buffer.empty() && buffer.top() == ch) {
                buffer.pop();
            } else {
                buffer.push(ch);
            }
        }
        std::string cleaned;
        while (!buffer.empty()) {
            cleaned += buffer.top();
            buffer.pop();
        }
        std::reverse(cleaned.begin(), cleaned.end());
        return cleaned;
    }
};

逆ポーランド記法の数式評価

トークンを走査し、数値であればスタックへ積む。演算子が現れた場合はスタックから2要素を取り出し、計算結果を再度格納する。演算順序はスタックの取り出し順序に依存するため、第二オペランドが先にポップされる点に注意する。

#include <vector>
#include <string>
#include <stack>
#include <unordered_set>

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> eval_stack;
        const std::unordered_set<std::string> operators = {"+", "-", "*", "/"};
        
        for (const auto& token : tokens) {
            if (operators.count(token) == 0) {
                eval_stack.push(std::stoi(token));
            } else {
                int rhs = eval_stack.top(); eval_stack.pop();
                int lhs = eval_stack.top(); eval_stack.pop();
                int computed = 0;
                if (token == "+") computed = lhs + rhs;
                else if (token == "-") computed = lhs - rhs;
                else if (token == "*") computed = lhs * rhs;
                else if (token == "/") computed = lhs / rhs;
                eval_stack.push(computed);
            }
        }
        return eval_stack.top();
    }
};

スライドウィンドウにおける最大値探索

双方向キューを用いて単調減少列を維持する。ウィンドウ範囲外の要素は先頭から除去し、新たな要素より小さい値は末尾から削除することで、常に先頭に現在の区間最大値が配置される。

#include <vector>
#include <deque>

class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        if (nums.empty() || k <= 0) return {};
        std::deque<int> mono_deque;
        std::vector<int> results;
        results.reserve(nums.size() - k + 1);
        
        for (int right = 0; right < nums.size(); ++right) {
            int left = right - k + 1;
            // ウィンドウ外要素の除去
            if (left > 0 && !mono_deque.empty() && mono_deque.front() <= nums[right - k]) {
                mono_deque.pop_front();
            }
            // 単調性の維持
            while (!mono_deque.empty() && mono_deque.back() < nums[right]) {
                mono_deque.pop_back();
            }
            mono_deque.push_back(nums[right]);
            
            if (left >= 0) {
                results.push_back(mono_deque.front());
            }
        }
        return results;
    }
};

出現頻度上位K要素の抽出

ハッシュマップで各要素の出現回数をカウント後、優先度キューに{頻度, 値}のペアを投入する。優先度キューの順序付け機能により、上位要素を効率的に取得可能である。

#include <vector>
#include <unordered_map>
#include <queue>

class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> freq_table;
        for (int val : nums) freq_table[val]++;
        
        // 頻度を基準に降順ソートする優先度キュー
        std::priority_queue<std::pair<int, int>> max_heap;
        for (const auto& [value, count] : freq_table) {
            max_heap.emplace(count, value);
        }
        
        std::vector<int> top_elements;
        while (k-- > 0) {
            top_elements.push_back(max_heap.top().second);
            max_heap.pop();
        }
        return top_elements;
    }
};