アルゴリズム図: 2 つのスタックを持つキューを実装するにはどうすればよいでしょうか?

[[348375]]

この記事はWeChatの公開アカウント「Java Chinese Community」から転載したもので、著者はLei Geです。この記事を転載する場合は、Java Chinese Community 公式アカウントにお問い合わせください。

この記事は、https://github.com/vipstone/algorithm の「アルゴリズムグラフィックス」シリーズに含まれています。

キューとスタックは、コンピューターの 2 つの非常に重要なデータ構造です。以前の研究 (「キュー」、「スタック」) により、それぞれの特性がわかっています。キューは先入れ先出し (FIFO) で、スタックは先入れ後出し (FILO) です。では、スタックを使用してキューを実装するにはどうすればよいでしょうか。これは面接でよく聞かれる質問なので、この記事で実装してみましょう。

正式に始める前に、スタックとキューの一般的なメソッドを確認しましょう。

スタックの一般的な方法は次のとおりです。

push(): スタックメソッド、スタックの先頭に要素を追加します。
pop(): Pop メソッド。スタックの先頭の要素を削除し、その要素を返します。
peek(): スタックの一番上の要素を照会し、要素を削除しません。

キューの一般的な方法は次のとおりです。

offer(): キューの末尾に要素を追加する Enqueue メソッド。
poll(): デキューメソッド。キューの先頭から要素を削除して返します。
peek(): キューの先頭要素を照会し、要素を削除しません。

これらの前提知識を踏まえて、今日のトピックを見てみましょう。

タイトル説明

2 つのスタックを使用してキューを実装します。キューの宣言は次のとおりです。キューの末尾に整数を挿入し、キューの先頭から整数を削除するには、appendTail と deleteHead という 2 つの関数を実装してください。キューに要素がない場合、deleteHead 操作は -1 を返します。

例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 <=値<= 10000
 appendTailとdeleteHeadの呼び出しは最大10,000回行われます。
リートコード: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

問題解決

この問題の意味は実は非常に分かりやすく、先入後出スタックを先入先出キューに変更することです。実際、この問題には「2 つのスタックを使用してキューを実装する」というヒントも示されています。この問題の核となる考え方は、「2 つの負の数は 1 つの正の数に等しい」というものです。まずスタックを使用して要素を格納し (最初に入力された要素はスタックの一番下にあります)、次に最初のスタック内の要素を新しいスタックに移動します。このとき、最初に入力された要素はスタックの一番上にあります。次に、2 番目のスタックを使用して要素をポップすると、全体の実行順序は先入れ先出しになります。

次に、グラフィカルなアプローチを使用してプロセス全体を実装します。

ステップ1

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

ステップ2

次に示すように、最初のスタック内のすべての要素を 2 番目のスタックに移動します。

ステップ3

以下に示すように、すべての要素が 2 番目のスタックからポップされます。

まとめ

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

実装コード

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

クラスCQueue {
    Stack< Integer > inputStack; // スタックにプッシュされるコンテナ（追加時の操作）
    Stack< Integer > outputStack; // ポップとクエリのためのスタックコンテナ
 
パブリックCQueue() {
        入力Stack = 新しいStack();
        出力スタック = 新しいスタック();
    } 
 
    // 操作を追加
パブリックvoid appendTail( int値) {
        inputStack.push(値);
    } 
 
    // 削除操作
公共  int削除ヘッド() {
        出力スタックが空の場合（！出力スタックが空の場合）{
            // ポップスタックコンテナは空ではありません
outputStack.pop()を返します。
        }それ以外の場合は (!inputStack.isEmpty()) {
            // スタック全体がスタックに転送されます
            (!inputStack.isEmpty()) の間 {
                出力スタックをプッシュします(入力スタックをポップします)。
            }
        }
 outputStack.isEmpty()を返します? -1 : outputStack.pop();
    }
 }

上記のテストコードをLeetCodeで送信すると、実行結果は次のようになります。

予防

実装プロセス全体において、特別な注意が必要な 2 つの小さな詳細があります。

最初のスタックはプッシュ（一時的なデータ保存）のみを担当し、2 番目のスタックはポップ（最終的なキュー実行順序）のみを担当します。

スタック 2 がポップされるたびに、スタック 1 から新しいデータを追加 (追加) する前に、すべての要素をポップする必要があります。スタック 2 のすべてのデータがポップされていない場合、スタック 1 の要素をスタック 2 にプッシュすることができず、要素の実行順序が乱れることになります。

要約する

この記事では、2 つの先入後出スタックと「負は正に等しい」という考え方を使用して、キューの先入先出機能を実装します。ただし、ポップコンテナーである 2 番目のスタックが空でない場合は、プログラムの実行順序の混乱を避けるために、最初のスタックの要素を 2 番目のスタックに追加できないことに注意してください。

オリジナルリンク: https://mp.weixin.qq.com/s/18GdYCCaaltx4ZMVkPsptg

<<: 人工知能はビッグデータの保存と管理の効率をどのように向上させるのでしょうか?