. Design Circular Deque

641. Design Circular Deque

Schwierigkeit:Mittel

Themen: Array, verknüpfte Liste, Design, Warteschlange

Entwerfen Sie Ihre Implementierung der kreisförmigen doppelendigen Warteschlange (Deque).

Implementieren Sie die MyCircularDeque-Klasse:

• MyCircularDeque(int k) Initialisiert die Deque mit einer maximalen Größe von k.
• boolean insertFront() Fügt ein Element an der Vorderseite von Deque hinzu. Gibt true zurück, wenn der Vorgang erfolgreich ist, andernfalls false.
• boolean insertLast() Fügt ein Element am Ende von Deque hinzu. Gibt true zurück, wenn der Vorgang erfolgreich ist, andernfalls false.
• boolean deleteFront() Löscht ein Element von der Vorderseite von Deque. Gibt true zurück, wenn der Vorgang erfolgreich ist, andernfalls false.
• boolean deleteLast() Löscht ein Element von der Rückseite von Deque. Gibt true zurück, wenn der Vorgang erfolgreich ist, andernfalls false.
• int getFront() Gibt das vordere Element aus der Deque zurück. Gibt -1 zurück, wenn die Deque leer ist.
• int getRear() Gibt das letzte Element von Deque zurück. Gibt -1 zurück, wenn die Deque leer ist.
• boolean isEmpty() Gibt true zurück, wenn die Deque leer ist, andernfalls false.
• boolean isFull() Gibt true zurück, wenn die Deque voll ist, andernfalls false.

Beispiel 1:

• Eingabe:

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

• Ausgabe:

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

• Erklärung:

  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

Einschränkungen:

• 1 <= k <= 1000
• 0 <= Wert <= 1000
• Es werden höchstens 2000 Aufrufe an insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull durchgeführt.

Lösung:

Wir können ein Array verwenden, um die Deque-Struktur darzustellen. Wir behalten einen Kopf- und Schwanzzeiger bei, der uns hilft, die Vorder- und Rückseite des Deques zu verfolgen und ihn bei Bedarf umzuwickeln, um das kreisförmige Verhalten zu erreichen.

Lassen Sie uns diese Lösung in PHP implementieren: 641. Design Circular Deque

Hier ist eine Schritt-für-Schritt-Lösung für die MyCircularDeque-Klasse:

<?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>
  
  
  Erläuterung:
</h3>

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

<ul>
<li>Wir initialisieren die Deque mit einem Array der Größe k und setzen zunächst alle Werte auf -1.</li>
<li>Die vorderen und hinteren Zeiger werden auf 0 initialisiert.</li>
<li>
size verfolgt die aktuelle Anzahl der Elemente in der Deque.</li>
</ul>
</li>
<li>
<p><strong>insertFront($value)</strong>:</p>

<ul>
<li>Überprüfen Sie mit isFull(), ob die Deque voll ist.</li>
<li>Wenn nicht, dekrementieren Sie den vorderen Zeiger (mit kreisförmigem Umlauf unter Verwendung von Modulo).</li>
<li>Platzieren Sie den Wert an der neuen Vorderseite und erhöhen Sie die Größe.</li>
</ul>
</li>
<li>
<p><strong>insertLast($value)</strong>:</p>

<ul>
<li>Überprüfen Sie, ob die Deque voll ist.</li>
<li>Wenn nicht, platzieren Sie den Wert hinten und bewegen Sie den hinteren Zeiger nach vorne (wiederum mit Modulo für den Umlauf).</li>
<li>Erhöhen Sie die Größe.</li>
</ul>
</li>
<li>
<p><strong>deleteFront()</strong>:</p>

<ul>
<li>Überprüfen Sie mit isEmpty(), ob die Deque leer ist.</li>
<li>Wenn nicht, erhöhen Sie den vorderen Zeiger (kreisförmiger Umlauf) und verringern Sie die Größe.</li>
</ul>
</li>
<li>
<p><strong>deleteLast()</strong>:</p>

<ul>
<li>Überprüfen Sie, ob die Deque leer ist.</li>
<li>Wenn nicht, dekrementieren Sie den hinteren Zeiger und reduzieren Sie die Größe.</li>
</ul>
</li>
<li>
<p><strong>getFront()</strong>:</p>

<ul>
<li>Wenn die Deque leer ist, geben Sie -1 zurück.</li>
<li>Andernfalls geben Sie das Element am vorderen Zeiger zurück.</li>
</ul>
</li>
<li>
<p><strong>getRear()</strong>:</p>

<ul>
<li>Wenn die Deque leer ist, geben Sie -1 zurück.</li>
<li>Andernfalls geben Sie das Element vor dem aktuellen hinteren Zeiger zurück (da hinten auf die nächste verfügbare Position zeigt).</li>
</ul>
</li>
<li>
<p><strong>isEmpty()</strong>:</p>

<ul>
<li>Gibt „true“ zurück, wenn die Deque leer ist (Größe ist 0).</li>
</ul>
</li>
<li>
<p><strong>isFull()</strong>:</p>

<ul>
<li>Gibt „true“ zurück, wenn die Deque voll ist (Größe entspricht maxSize).</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispiel-Komplettlösung
</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

Zeitkomplexität:

• Jede Operation (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) wird in O(1) Zeit ausgeführt, da sie alle zeitkonstante Array-Operationen und Zeigermanipulationen beinhalten.

Raumkomplexität:

• Die Raumkomplexität beträgt O(k), wobei k die Größe der Deque ist. Wir weisen Platz für k Elemente im Deque-Array zu.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Design Circular Deque. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!