2 つのスタックを持つキューを実装するにはどうすればよいですか?

# #Java ベースの教程 # 2 つのメソッドを使用して 1 つのリストを実行する方法。

# #队列と栈はコンピューター内の 2 つの非常に重要なデータ構造であり、前の学习 (《队列》、《栈》) 我们知道了它们各自的特点、队列は先先出 (FIFO) のもの、そして栈は先先です後 (FILO) で、どのようにしてマークを使用してこの列を実現するのでしょうか？

サンプル（スタック）の通常のメソッドには以下が含まれます：

push(): メソッドに入る、元素を追加する;

pop(): メソッドを取り出し、要素を削除して要素を返します。

• peek(): 要素を削除しません。

队列（キュー）の一般的なメソッドには以下が含まれます：

offer()：入力メソッド、方向队尾追加元素；

poll(): メソッドを取り出し、要素を削除して要素を返します。

• peek(): 要素を削除せず、要素を削除します。
#これらの事前の知識はありますが、次に今日のトピックを見てみましょう。関数 appendTail と deleteHead はそれぞれ、列の尾部で整数を入力し、列の先頭で整数を削除する機能を実行します。列に要素がない場合、deleteHead 操作は -1 を返します。 ##输入：
• ["CQueue","appendTail","deleteHead","deleteHead"]
• [[],[3],[],[]]

出力：[null,null,3,-1]

例 2：

入力：

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[ ],[]]

出力: [null,-1,null,null,5,2]

プロンプト:

1

appendTail および deleteHead への呼び出しが最大 10000 回行われます

leetcode: leetcode-cn.com/problems/yo…

解決策の質問のアイデア

この質問の意味は実際には理解しやすく、先入れ後出しスタックを先入れ先出しキューに変更するというものです。質問には、「キューを実装するには 2 つのスタックを使用する」というヒントも示されています。 この質問の核心的な考え方は、「マイナスがプラスになる」です。最初にスタックを使用して要素を格納し (最初に入力する要素はスタックの一番下にあります)、次に要素を追加します最初のスタック内 新しいスタックに移動します。このとき、最初に入力された要素はスタックの先頭にあります。その後、2 番目のスタックを使用して要素が取り出されるとき、全体の実行順序は先入れ先出しになります。 。

次に、プロセス全体をグラフィカルに実装しましょう。

ステップ 1

次の図に示すように、最初に要素を最初のスタックにプッシュします。

ステップ 2

要素をプッシュします。最初のスタックに次の図に示すように、1 つのスタック内の要素が 2 番目のスタックに移動されます。

ステップ 3

すべての要素が 2 番目のスタックからポップされます。次の図に示す 表示:

概要

上の図からわかるように、要素を追加する順序は 1、2、3 であり、最後にポップする順序になります。 2 つのスタックを通過した後のスタックの out も 1, 2 , 3 であるため、2 つのスタックを介してキュー (先入れ先出し) を実装します。

実装コード

次に、コードを使用して上記のアイデアを実装します。

class CQueue {
    Stack<integer> inputStack; // 入栈的容器（添加时操作)
    Stack<integer> outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码</integer></integer>

上記のテスト コードを LeetCode に送信します。実行結果は次のとおりです。次のとおりです:

注意事項

実装プロセス全体で特別な注意が必要な 2 つの詳細があります:

1. 最初のスタックはプッシュのみを担当します。スタックに追加する (データを一時的に保存する) 場合、2 番目のスタックはポップ (最後のキュー実行シーケンス) のみを担当します;
2. スタック 2 がポップされるたびに、スタック 1 から追加する前にすべての要素をポップアウトする必要があります (新しいデータを追加します。スタック 2 のすべてのデータがスタックからプッシュされていない場合、スタック 1 の要素をスタック 2 にプッシュできません。これにより、要素の実行順序が混乱します。

概要

この記事では、2 つの先入れ後出しスタックを使用し、次の考え方を通じてキューの先入れ先出し機能を実装します。 「ネガティブはポジティブになる」ですが、特別な注意が必要です。ポップアップ コンテナーである 2 番目のスタックが空 (スタック) でない場合、最初のスタックの要素を 2 番目のスタックに追加することはできません。プログラムの実行順序を混乱させる。

関連する無料学習の推奨事項: Java 基本チュートリアル

以上が2 つのスタックを持つキューを実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。