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:
Beispiel 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
Einschränkungen:
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
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:
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!
