. Conception Circulaire 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], []]

• Sortie :

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

• 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

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

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 :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!