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

アルゴリズム図: 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:

  1. 入力:
  2. [ "CQueue" "appendTail" "deleteHead" "deleteHead" ]
  3. [[],[3],[],[]]
  4. 出力: [ null , null ,3,-1]

例2:

  1. 入力:
  2. [ "CQueue" "deleteHead" "appendTail" "appendTail" "deleteHead" "deleteHead" ]
  3. [[],[],[5],[2],[],[]]
  4. 出力: [ null ,-1, null , null ,5,2]

ヒント:

  1. 1 <=<= 10000
  2. appendTailとdeleteHeadの呼び出しは最大10,000回行われます。
  3. リートコード: 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 つのスタックを介したキュー (先入れ先出し) を実装しました。

実装コード

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

  1. クラスCQueue {
  2. Stack< Integer > inputStack; // スタックにプッシュされるコンテナ(追加時の操作)
  3. Stack< Integer > outputStack; // ポップとクエリのためのスタックコンテナ
  4.  
  5. パブリックCQueue() {
  6. 入力Stack = 新しいStack();
  7. 出力スタック = 新しいスタック();
  8. }
  9.  
  10. // 操作を追加
  11. パブリックvoid appendTail( int値) {
  12. inputStack.push(値);
  13. }
  14.  
  15. // 削除操作
  16. 公共  int削除ヘッド() {
  17. 出力スタックが空の場合(!出力スタックが空の場合){
  18. // ポップスタックコンテナは空ではありません
  19. outputStack.pop()を返します
  20. }それ以外の場合は (!inputStack.isEmpty()) {
  21. // スタック全体がスタックに転送されます
  22. (!inputStack.isEmpty()) の間 {
  23. 出力スタックをプッシュします(入力スタックをポップします)。
  24. }
  25. }
  26. outputStack.isEmpty()を返します? -1 : outputStack.pop();
  27. }
  28. }

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

予防

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

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

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

要約する

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

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

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

>>:  ああはは、それだ!人気の機械学習アルゴリズムの 4 つの「なるほど!」という瞬間

ブログ    
ブログ    
ブログ    
ブログ    

推薦する

MITはレーザー彫刻機にAIを搭載し、材料を自動的に識別し、98%の精度で彫刻の強度を判定した。

この記事はAI新メディアQuantum Bit(公開アカウントID:QbitAI)より許可を得て転載...

...

人工知能がスマートホームに加わり、未来が現実になる

[[262824]]スマートシティ建設が国家戦略となり、ハイテクが急速に発展するにつれて、スマートシ...

会話型AIが重要なサービスに与える影響

コミュニケーションツールが進化するにつれ、電話や携帯電話は人々が情報を素早く共有する能力に大きな影響...

顔認識の応用シナリオは拡大し続けています。顔スキャンは便利で安全である必要があります。

[[341456]]顔スキャンでロック解除、顔スキャンで支払い、顔スキャンでキャンパスに入る......

ファーウェイ、データインフラを再定義するAIネイティブデータベースを世界規模で展開

[中国、北京、2019年5月15日] ファーウェイは、2018年にAI戦略とフルスタックの全シナリオ...

知湖橋プラットフォームにおける大型モデルの応用と実践

1. 事業の状況及び背景まずはブリッジプラットフォームを紹介します。 Bridge は、Zhihu ...

ディープラーニングとディープクローニング: チャットボットにとってより優れたソリューションはどちらでしょうか?

[[200112]]編集者注: チャットボットは目新しいものではありません。Facebook や ...

ニュースローン賞受賞者 宋 樹蘭: 視覚の観点からロボットの「目」を構築する

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式...

機械学習でデータを実用的な洞察に変換する

ビジネスが今やデータ主導型になっていることは誰もが知っています。データ収集の増加に伴い、分析はビジネ...

USPTO レポート: 人工知能を使わないと取り残される!

米国特許商標庁(USPTO)が10月27日に発表した新しい報告書によると、2018年のすべての新しい...

調査によると、AIツールは企業の従業員が年間約400時間を節約するのに役立つことがわかった

7月10日、人材分析・計画会社Visierは、英国、米国、カナダ、ドイツの250社以上の企業の従業員...

...

...