スタックとキューの実装：データ構造の変換問題

基礎知識

スタックとキューの内部実装メカニズム

キューは先入れ先出し（FIFO）、スタックは後入れ先出し（LIFO）です。

スタックに関する4つの基本質問

  1. C++におけるstackはコンテナですか？

    スタックとキューはSTL（C++標準ライブラリ）の2つのデータ構造です。STLでは、スタックはコンテナとして分類されるのではなく、container adapter（コンテナアダプタ）として分類されます。同様に、STLのキューもコンテナではなくコンテナアダプタです。

  2. 私たちが使用しているstackはどのバージョンのSTLに属していますか？

    スタックとキューはSGI STLに含まれるデータ構造です。

    3つの主要なSTLバージョン：

    • HP STL - 他のC++ STLバージョンの多くはHP STLを基に実装されています。HP STLは最初のC++ STL実装バージョンであり、オープンソースです。
    • P.J.Plauger STL - P.J.PlaugerがHP STLを参考に実装され、Visual C++コンパイラで採用されていますが、オープンソースではありません。
    • SGI STL - Silicon Graphics Computer Systems社がHP STLを参考に実装し、LinuxのC++コンパイラGCCで採用されています。SGI STLはオープンソースで、ソースコードの可読性が非常に高いです。
  3. 私たちが使用しているSTLでstackはどのように実装されていますか？

    スタックの内部構造は、ベクター、デック、リストのいずれかで実装できます。主に配列とリンクドリストの底層実装です。

    スタックは底層コンテナによってそのすべての作業が行われ、外部に統一されたインターフェースを提供します。底層コンテナはプラグ可能です（つまり、どのコンテナを使用してスタック機能を実装するかを制御できます）。

    SGI STLでは、底層実装が指定されていない場合、デフォルトでデックがスタックの底層構造として使用されます。

    デックは双方向キューであり、片端を封印し、もう片端のみを開放することでスタックのロジックを実現できます。

    SGI STLでは、キューの底層実装もデフォルトでデックを使用して実装されます。

    ベクターをスタックの底層実装として指定できます：

    std::stack third;  // ベクターを底層コンテナとするスタック

    リストをキューの底層実装として指定できます：

    std::queue third; // リストを底層コンテナとするキュー
  4. stackはスタック空間を走査するためのイテレータを提供しますか？

    スタックはpushやpopなどのインターフェースを提供しますが、すべての要素は後入れ先出しルールに適合する必要があるため、スタックは走査機能を提供せず、イテレータも提供しません。setやmapのように、すべての要素を走査するためのイテレータを提供するわけではありません。

問題解決

232. スタックを使用してキューを実装する

解決方針

2つのスタックを使用してキューを実装します。1つはプッシュ操作をシミュレートし、もう1つはポップ操作をシミュレートします。

コード実装


// stack.top(): 最後にプッシュされた要素を返し、スタックの最上位（最後に挿入された要素）にある要素
class MyQueue {
private:
    // 2つのスタックでキューを実装：1つは入力用、もう1つは出力用
    stack<int> input_stack;
    stack<int> output_stack;
public:
    MyQueue() {}
    
    // 要素xをキューの末尾に追加
    void push(int x) {
        input_stack.push(x);
    }
    
    // キューの先頭から要素を削除して返す
    int pop() {
        // 注意点：output_stackが空の場合のみ、input_stackからデータをすべて転送する
        if (output_stack.empty()) {
            while (!input_stack.empty()) {
                // input_stackの最上位要素をoutput_stackに移動
                output_stack.push(input_stack.top());
                input_stack.pop();
            }
        }
        // 最後にプッシュされた要素が先頭
        int result = output_stack.top();
        output_stack.pop();
        return result;
    }
    
    // キューの先頭要素を返す（最初にキューに追加された要素）
    int peek() {
        // 既存のpop関数を使用
        int result = this->pop();
        // 元の状態に復元
        output_stack.push(result);
        return result;
    }
    
    // キューが空の場合はtrueを返す、それ以外はfalseを返す
    bool empty() {
        return input_stack.empty() && output_stack.empty();
    }
};

225. キューを使用してスタックを実装する

解決方針

方法1: 2つのキュー（que1とque2）を使用してスタック機能を実装します。que2は実質的にバックアップとして機能します。que1の最後尾の要素以外をすべてque2にバックアップし、最後尾の要素をポップしてから、他の要素をque2からque1に戻します。

方法2: 1つのキューを使用してスタック機能を実装します。スタックの要素をシミュレートする際に、キューの先頭要素（最後尾の要素を除く）をキューの末尾に再度追加するだけです。これにより、要素をポップする際にスタックの順序になります。

コード実装


// que.front(): キューの最初の要素を返す
// que.back(): キューの最後の要素を返す
class MyStack {
private:
    // 1つのキューを使用してスタック機能を実装
    queue<int> q;
public:
    MyStack() {}
    
    // 要素xをスタックのトップにプッシュ
    void push(int x) {
        q.push(x);
    }
    
    // スタックのトップ要素を削除して返す
    int pop() {
        int size = q.size() - 1;
        // 最後の要素はそのまま保持
        while(size--) {
            // キューの先頭要素（最後尾の要素を除く）をキューの末尾に再度追加
            q.push(q.front());
            q.pop();
        }
        // 値を取得し、ポップして返す
        int result = q.front();
        q.pop();
        return result;
    }
    
    // スタックのトップ要素を返す
    int top() {
        return q.back();
    }
    
    // スタックが空の場合はtrueを返す、それ以外はfalseを返す
    bool empty() {
        return q.empty();
    }
};

20. 有効な括弧

解決方針

スタックを使用して括弧の有効性を確認します。開き括弧をスタックにプッシュし、対応する閉じ括弧が現れたらスタックからポップします。最終的にスタックが空であれば、すべての括弧が正しく対応していることになります。

コード実装


#include 

class Solution {
public:
    bool isValid(string s) {
        // 空の文字列は有効
        if (s.empty()) return true;
        
        // 対応する括弧のマッピング
        unordered_map bracket_pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        
        stack<char> char_stack;
        
        for (char c : s) {
            // 閉じ括の場合
            if (bracket_pairs.find(c) != bracket_pairs.end()) {
                // スタックが空か、最上位要素が対応する開き括でない場合
                if (char_stack.empty() || char_stack.top() != bracket_pairs[c]) {
                    return false;
                }
                // 対応する開き括をポップ
                char_stack.pop();
            } 
            // 開き括の場合
            else {
                char_stack.push(c);
            }
        }
        
        // スタックが空ならすべての括弧が対応
        return char_stack.empty();
    }
};

1047. 文字列内のすべての隣接する重複項を削除する

解決方針

スタックを使用して文字列内の隣接する重複項を削除します。文字列を1文字ずつ処理し、現在の文字がスタックの最上位文字と同じ場合は両方とも削除（ポップ）します。異なる場合は現在の文字をスタックにプッシュします。最終的にスタックに残っている文字列が結果になります。

コード実装


class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> char_stack;
        
        for (char c : s) {
            // スタックが空でなく、最上位文字が現在の文字と同じ場合
            if (!char_stack.empty() && char_stack.top() == c) {
                // 両方の文字を削除
                char_stack.pop();
            } else {
                // 現在の文字をスタックに追加
                char_stack.push(c);
            }
        }
        
        // スタックの内容を結果文字列に変換
        string result;
        while (!char_stack.empty()) {
            result = char_stack.top() + result;
            char_stack.pop();
        }
        
        return result;
    }
};

タグ: スタック キュー C++ データ構造 アルゴリズム

5月19日 20:09 投稿

ホットタグ

©2026 異端開発室