。循環デックの設計

641。デザインサーキュラーデク

難易度: 中

トピック: 配列、リンク リスト、デザイン、キュー

循環両端キュー (deque) の実装を設計します。

MyCircularDeque クラスを実装します:

• MyCircularDeque(int k) 最大サイズ k で両端キューを初期化します。
• boolean insertFront() Deque の前に項目を追加します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
• boolean insertLast() Deque の後ろに項目を追加します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
• boolean deleteFront() Deque の前から項目を削除します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
• boolean deleteLast() Deque の後ろから項目を削除します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
• int getFront() Deque から先頭の項目を返します。デキューが空の場合は -1 を返します。
• int getRear() Deque から最後の項目を返します。デキューが空の場合は -1 を返します。
• boolean isEmpty()両端キューが空の場合は true を返し、それ以外の場合は false を返します。
• boolean isFull() デキューがいっぱいの場合は true を返し、それ以外の場合は false を返します。

例 1:

• 入力:

  ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
  [[3], [1], [2], [3], [4], [], [], [], [4], []]

• 出力:

  [null, true, true, true, false, 2, true, true, true, 4]

• 説明:

  MyCircularDeque myCircularDeque = new MyCircularDeque(3);
  myCircularDeque.insertLast(1);  // return True
  myCircularDeque.insertLast(2);  // return True
  myCircularDeque.insertFront(3); // return True
  myCircularDeque.insertFront(4); // return False, the queue is full.
  myCircularDeque.getRear();      // return 2
  myCircularDeque.isFull();       // return True
  myCircularDeque.deleteLast();   // return True
  myCircularDeque.insertFront(4); // return True
  myCircularDeque.getFront();     // return 4

制約:

• 1
• 0
• insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull に対して最大 2000 回の呼び出しが行われます。

解決策:

配列を使用して両端キュー構造を表すことができます。循環動作を実現するために必要に応じてラップアラウンドして、デクの前後を追跡するのに役立つヘッドとテールのポインタを維持します。

このソリューションを PHP で実装してみましょう: 641。デザイン円形デク

MyCircularDeque クラスの段階的なソリューションを次に示します。

<?php
class MyCircularDeque {
    /**
     * @var array
     */
    private $deque;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * @var int
     */
    private $front;
    /**
     * @var int
     */
    private $rear;
    /**
     * @var int
     */
    private $size;

    /**
     * Initialize your data structure here. Set the size of the deque to be k.
     *
     * @param Integer $k
     */
    function __construct($k) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Adds an item at the front of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertFront($value) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Adds an item at the rear of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertLast($value) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Deletes an item from the front of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteFront() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Deletes an item from the rear of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteLast() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Get the front item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getFront() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Get the last item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getRear() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Checks whether the deque is empty or not.
     *
     * @return Boolean
     */
    function isEmpty() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Checks whether the deque is full or not.
     * 
     * @return Boolean
     */
    function isFull() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * $obj = MyCircularDeque($k);
 * $ret_1 = $obj->insertFront($value);
 * $ret_2 = $obj->insertLast($value);
 * $ret_3 = $obj->deleteFront();
 * $ret_4 = $obj->deleteLast();
 * $ret_5 = $obj->getFront();
 * $ret_6 = $obj->getRear();
 * $ret_7 = $obj->isEmpty();
 * $ret_8 = $obj->isFull();
 */

?>

説明：

1. 初期化:

   • サイズ k の配列を使用して両端キューを初期化し、最初にすべての値を -1 に設定します。
   • 前後のポインタは 0 に初期化されます。
   • size は、両端キュー内の現在の要素数を追跡します。

2. insertFront($value):

   • isFull() を使用して両端キューがいっぱいかどうかを確認します。
   • そうでない場合は、フロント ポインターをデクリメントします (モジュロを使用した循環ラップアラウンドを使用)。
   • 新しい先頭に値を配置し、サイズを増やします。

3. insertLast($value):

   • 両端キューがいっぱいかどうかを確認します。
   • そうでない場合は、値を後ろに配置し、後ろのポインタを前に移動します (ラップアラウンドにモジュロを使用します)。
   • サイズを増やします。

4. deleteFront():

   • isEmpty() を使用して両端キューが空かどうかを確認します。
   • そうでない場合は、フロント ポインター (円形の回り込み) を増加させ、サイズを減少させます。

5. deleteLast():

   • 両端キューが空かどうかを確認します。
   • そうでない場合は、リア ポインタをデクリメントしてサイズを小さくします。

6. getFront():

   • 両端キューが空の場合は、-1 を返します。
   • それ以外の場合は、先頭ポインタの要素を返します。

7. getRear():

   • 両端キューが空の場合は、-1 を返します。
   • それ以外の場合は、現在のリア ポインタの前の要素を返します (リアは次に利用可能な位置を指すため)。

8. isEmpty():

   • 両端キューが空 (サイズが 0) の場合は true を返します。

9. isFull():

   • 両端キューがいっぱいの場合 (サイズが maxSize と等しい)、true を返します。

チュートリアルの例

$myCircularDeque = new MyCircularDeque(3);  // Initialize deque with size 3

$myCircularDeque->insertLast(1);  // return true
$myCircularDeque->insertLast(2);  // return true
$myCircularDeque->insertFront(3); // return true
$myCircularDeque->insertFront(4); // return false, deque is full
echo $myCircularDeque->getRear(); // return 2
echo $myCircularDeque->isFull();  // return true
$myCircularDeque->deleteLast();   // return true
$myCircularDeque->insertFront(4); // return true
echo $myCircularDeque->getFront(); // return 4

時間計算量:

• 各操作 (insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull) は、すべて定数時間の配列操作とポインター操作を伴うため、O(1) 時間で実行されます。

空間の複雑さ:

• 空間計算量は O(k) です。ここで、k は両端キューのサイズです。 deque 配列内の k 要素にスペースを割り当てます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。循環デックの設計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。