アルゴリズムスタックとキュー【剣指Offer 09は2つのスタックで1つのキューを実現する】

一、テーマの説明
2つのスタックで1つのキューを実現します.キューの宣言は以下のとおりです.2つの関数appendTailとdeleteHeadを実装し、キューの末尾に整数を挿入し、キューの先頭に整数を削除する機能をそれぞれ完了してください.(キューに要素がない場合はdeleteHead操作は-1を返します)
 
二、考え方
スタックのプロパティ:後進先出
キューのプロパティ:先進的な前提条件
この特性を利用して,2つのスタックをそれぞれ異なる役割を果たすことができる.
最初のスタックに要素を挿入するたびに、最初のスタックの下部要素は最後に挿入された要素であり、最初のスタックの上部要素は次の削除する要素です.
キューの先進的な先出し特性を維持するために、2番目のスタックを導入し、2番目のスタックで削除する要素を維持し、削除操作を実行するときに2番目のスタックが空であるかどうかを最初に見ます.
空の場合、最初のスタックの要素を2番目のスタックにポップアップして挿入します.このように、2番目のスタックの要素の順序は削除する要素の順序であり、削除操作を実行するときは、2番目のスタックの要素を直接ポップアップして返します.
図示:LeetCodeから
 
三、コード

class CQueue {
public:
    stack s1;
    stack s2;
    CQueue() {
    

    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if(s1.empty() && s2.empty())
        {
            return -1;
        }
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int deleteNumber = s2.top();
        s2.pop();
        return deleteNumber;

    }
};