。設計循環雙端佇列-php教程-PHP中文網

. Design Circular Deque

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() 傳回雙端佇列中最前面的項目。如果雙端佇列為空，則傳回 -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
最多將呼叫 2000 次 insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull。

解：

我們可以使用陣列來表示雙端隊列結構。我們將維護一個頭指針和尾指針，幫助我們追蹤雙端隊列的前部和後部，並在必要時環繞以實現循環行為。

讓我們用 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();
 */

?>

登入後複製

解釋：

初始化:
- 我們使用大小為 k 的陣列初始化雙端佇列，並將所有值最初設為 -1。
- 前後指標初始化為0。
- size 追蹤雙端佇列中目前元素的數量。
insertFront($value):
- 使用 isFull() 檢查雙端佇列是否已滿。
- 如果不是，則遞減前指標（使用模進行循環環繞）。
- 將值放在新的前面並增加大小。
insertLast($value):
- 檢查雙端佇列是否已滿。
- 如果沒有，則將值放在後面並將後指針向前移動（再次使用模進行環繞）。
- 增加大小。
deleteFront():
- 使用 isEmpty() 檢查雙端佇列是否為空。
- 如果不是，則增加前指針（循環環繞）並減少大小。
deleteLast():
- 檢查雙端佇列是否為空。
- 如果不是，則遞減後指針並減小尺寸。
getFront():
- 如果雙端隊列為空，則回傳-1。
- 否則，傳回前指標處的元素。
getRear():
- 如果雙端隊列為空，則回傳-1。
- 否則，傳回目前後指標之前的元素（因為後指標指向下一個可用位置）。
isEmpty():
- 如果雙端佇列為空（大小為 0），則傳回 true。
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

登入後複製