『剣指offer』Java学習録:スタックとキュー(面接問題7:2つのスタックで1つのキューを実現)

文書ディレクトリ

スタックおよびキュー

面接問題7:2つのスタックが1つのキュー

を実現

題

分析

解:Java

解:C++

スタックとキュー

スタック:スタックは非常に一般的なデータ構造であり、先機後出が特徴である.すなわち、最初にスタックに押し込まれた要素は最初にポップアップされます.コンピュータで広く使用されています.たとえば、オペレーティングシステムは、関数呼び出し時の各関数のパラメータを格納するスタックをスレッドごとに作成します.通常、スタックはソートを考慮しないデータ構造であり、O(n)O_{(n)}O(n)の時間こそスタックの要素を見つけることができ、TODO:削除するかどうかを考えて、この不動は

を誤解しないでください.

キュー:スタックと同様に、キューも非常に重要なデータ構造です.その特徴は先進的な先発、すなわち最初の入隊要素が最初に出ることです.

スタックとキューキューは、特徴的な対立する2つのデータ構造ですが、興味深いことに、面接問題を見てみましょう.
面接問題7:2つのスタックで1つのキューを実現
タイトル
2つのスタックで1つのキューを実現します.キューは、以下のように明記されており、2つの関数appendTailおよびdeleteHeadを実装し、キューの末尾にノードを挿入し、キューのヘッダにノードを削除する機能をそれぞれ完了してください.

template
class Queue {
public:
    Queue(void);

    ~Queue(void);

    void appendTail(const T &node);

    T deleteHead();

private:
    stack stack1;
    stack stack2;
};

ぶんせき
2つのスタックでキューの機能を実現するには,粗く見るとその方法が見えず,ゆっくり分析するしかない.
まずエンキューをシミュレートし、エンキュー時にデータ構造を格納する必要があるので、とりあえずstack 1を選びましょう.もし私たちが1、2、3を順番にチームに入れば、1、2、3を順番にstack 1に押し込むことになります.このときstack 1のスタックの順序は3,2,1であり,この場合にキューを出すと,順序も必然的に3,2,1とキューが先に出る特性が一致しない.
もう1つのスタックstack 2が使用されていないことを考慮すると、スタックの特性は先に入ってから出ることであり、ちょうど圧入順序を反転させ、負を正にし、デキュー時にはstack 1の要素を順次stack 2にコピーするだけである.stack 2のスタック順序は、デキュー順序に合致します.
この問題の重要な解題構想は,スタックの圧入順序とポップアップ順序が逆である.2つのスタックを使用すると、圧入順序とポップアップ順序を一致させることができます.
解:Java

import java.util.Stack;

public class Queue<T> {
    private Stack<T> mStackAppend;
    private Stack<T> mStackDelete;

    public Queue() {
        mStackAppend = new Stack<>();
        mStackDelete = new Stack<>();
    }

    public void appendTail(T node) {
        mStackAppend.push(node);
    }

    public T deleteHead() {
        if (mStackDelete.empty()) {
            while (!mStackAppend.empty()) {
                mStackDelete.push(mStackAppend.pop());
            }
        }
        if (mStackDelete.empty()) {
            return null;
        }
        return mStackDelete.pop();
    }
}

テストコード:

public static void main(String args[]) {
    Queue<Integer> queue = new Queue<>();
    queue.appendTail(1);
    queue.appendTail(2);
    queue.appendTail(3);

    System.out.println(queue.deleteHead());
    System.out.println(queue.deleteHead());
    System.out.println(queue.deleteHead());
}

解:C++

template
class Queue {
public:
    Queue(void){}

    ~Queue(void){}

    void appendTail(const T &node) {
        stack1.push(node);
    }

    T deleteHead() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                T &data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        if (stack2.empty()) {
            throw std::exception();
        }
        T head = stack2.top();
        stack2.pop();
        return head;
    }

private:
    stack stack1;
    stack stack2;
};

int main() {
    Queue queue;
    queue.appendTail(1);
    queue.appendTail(2);
    queue.appendTail(3);

    cout << queue.deleteHead()
         << queue.deleteHead()
         << queue.deleteHead() << endl;
    return 0;
}