. Conception Circulaire Deque-tutoriel php-php.cn

. Design Circular Deque

641. Conception Circulaire Deque

Difficulté :Moyen

Sujets : Tableau, liste chaînée, conception, file d'attente

Concevez votre implémentation de la file d'attente circulaire à double extrémité (deque).

Implémentez la classe MyCircularDeque :

MyCircularDeque(int k) Initialise le deque avec une taille maximale de k.
boolean insertFront() Ajoute un élément au début de Deque. Renvoie vrai si l'opération réussit, ou faux dans le cas contraire.
boolean insertLast() Ajoute un élément à l'arrière de Deque. Renvoie vrai si l'opération réussit, ou faux dans le cas contraire.
boolean deleteFront() Supprime un élément du devant de Deque. Renvoie vrai si l'opération réussit, ou faux dans le cas contraire.
boolean deleteLast() Supprime un élément à l'arrière de Deque. Renvoie vrai si l'opération réussit, ou faux dans le cas contraire.
int getFront() Renvoie l'élément frontal du Deque. Renvoie -1 si le deque est vide.
int getRear() Renvoie le dernier élément de Deque. Renvoie -1 si le deque est vide.
boolean isEmpty() Renvoie true si le deque est vide, ou false sinon.
boolean isFull() Renvoie vrai si le deque est plein, ou faux sinon.

Exemple 1 :

Entrée :

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

Copier après la connexion

Sortie :

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

Copier après la connexion

Explication :

  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

Copier après la connexion

Contraintes :

1 <= k <= 1000
0 <= valeur <= 1000
Au maximum 2 000 appels seront effectués vers insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

Solution :

Nous pouvons utiliser un tableau pour représenter la structure deque. Nous conserverons un pointeur de tête et de queue qui nous aidera à suivre l'avant et l'arrière du deque, en l'enroulant si nécessaire pour obtenir le comportement circulaire.

Implémentons cette solution en PHP : 641. Conception Circulaire Deque

Voici une solution étape par étape pour la classe 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();
 */

?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Initialisation</strong> :</p>

<ul>
<li>Nous initialisons le deque en utilisant un tableau de taille k et définissons initialement toutes les valeurs sur -1.</li>
<li>Les pointeurs avant et arrière sont initialisés à 0.</li>
<li>
size garde une trace du nombre actuel d'éléments dans le deque.</li>
</ul>
</li>
<li>
<p><strong>insertFront($value)</strong> :</p>

<ul>
<li>Vérifiez si le deque est plein en utilisant isFull().</li>
<li>Sinon, décrémentez le pointeur avant (avec enroulement circulaire en utilisant modulo).</li>
<li>Placez la valeur au nouveau devant et incrémentez la taille.</li>
</ul>
</li>
<li>
<p><strong>insertLast($value)</strong> :</p>

<ul>
<li>Vérifiez si le deque est plein.</li>
<li>Sinon, placez la valeur à l'arrière et déplacez le pointeur arrière vers l'avant (en utilisant encore une fois modulo pour le bouclage).</li>
<li>Incrémentez la taille.</li>
</ul>
</li>
<li>
<p><strong>deleteFront()</strong> :</p>

<ul>
<li>Vérifiez si le deque est vide en utilisant isEmpty().</li>
<li>Sinon, incrémentez le pointeur avant (enveloppement circulaire) et décrémentez la taille.</li>
</ul>
</li>
<li>
<p><strong>deleteLast()</strong> :</p>

<ul>
<li>Vérifiez si le deque est vide.</li>
<li>Sinon, décrémentez le pointeur arrière et réduisez la taille.</li>
</ul>
</li>
<li>
<p><strong>getFront()</strong> :</p>

<ul>
<li>Si le deque est vide, renvoie -1.</li>
<li>Sinon, renvoyez l'élément au pointeur avant.</li>
</ul>
</li>
<li>
<p><strong>getRear()</strong> :</p>

<ul>
<li>Si le deque est vide, renvoie -1.</li>
<li>Sinon, renvoyez l'élément avant le pointeur arrière actuel (puisque l'arrière pointe vers la prochaine position disponible).</li>
</ul>
</li>
<li>
<p><strong>isEmpty()</strong> :</p>

<ul>
<li>Renvoie vrai si le deque est vide (la taille est 0).</li>
</ul>
</li>
<li>
<p><strong>isFull()</strong> :</p>

<ul>
<li>Renvoie vrai si le deque est plein (la taille est égale à maxSize).</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple de procédure pas à pas
</h3>



<pre class="brush:php;toolbar:false">$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

Copier après la connexion

Complexité temporelle :

Chaque opération (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) s'exécute en O(1) temps car elles impliquent toutes des opérations de tableau à temps constant et des manipulations de pointeurs.

Complexité spatiale :

La complexité spatiale est O(k), où k est la taille du deque. Nous allouons de l'espace pour k éléments dans le tableau deque.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :