。设计循环双端队列

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();
 */

?>

解释：

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是双端队列的大小。我们为双端队列数组中的 k 个元素分配空间。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。设计循环双端队列的详细内容。更多信息请关注PHP中文网其他相关文章！