。设计循环双端队列-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

登录后复制