. Pekeliling Reka Bentuk Deque

641. Design Pekeliling Deque

Kesukaran: Sederhana

Topik: Tatasusunan, Senarai Terpaut, Reka Bentuk, Baris Beratur

Reka bentuk pelaksanaan anda bagi baris gilir dua hujung bulat (deque).

Melaksanakan kelas MyCircularDeque:

• MyCircularDeque(int k) Memulakan deque dengan saiz maksimum k.
• boolean insertFront() Menambah item di hadapan Deque. Mengembalikan benar jika operasi berjaya, atau palsu sebaliknya.
• boolean insertLast() Menambah item di belakang Deque. Mengembalikan benar jika operasi berjaya, atau palsu sebaliknya.
• boolean deleteFront() Memadam item dari hadapan Deque. Mengembalikan benar jika operasi berjaya, atau palsu sebaliknya.
• boolean deleteLast() Memadam item dari belakang Deque. Mengembalikan benar jika operasi berjaya, atau palsu sebaliknya.
• int getFront() Mengembalikan item hadapan daripada Deque. Mengembalikan -1 jika deque kosong.
• int getRear() Mengembalikan item terakhir daripada Deque. Mengembalikan -1 jika deque kosong.
• boolean isEmpty() Mengembalikan benar jika deque kosong, atau false sebaliknya.
• boolean isFull() Mengembalikan benar jika deque penuh, atau false sebaliknya.

Contoh 1:

• Input:

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

• Output:

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

• Penjelasan:

  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

Kekangan:

• 1
• 0
• Paling banyak 2000 panggilan akan dibuat untuk memasukkanFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

Penyelesaian:

Kita boleh menggunakan tatasusunan untuk mewakili struktur deque. Kami akan mengekalkan penunjuk kepala dan ekor yang akan membantu kami menjejaki bahagian hadapan dan belakang deque, melilit apabila perlu untuk mencapai gelagat bulat.

Mari laksanakan penyelesaian ini dalam PHP: 641. Deque Pekeliling Reka Bentuk

Berikut ialah penyelesaian langkah demi langkah untuk kelas 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();
 */

?>

Penjelasan:

1. Permulaan:

   • Kami memulakan deque menggunakan tatasusunan saiz k dan menetapkan semua nilai kepada -1 pada mulanya.
   • Penunjuk hadapan dan belakang dimulakan kepada 0.
   • saiz menjejaki bilangan elemen semasa dalam deque.

2. insertFront($value):

   • Periksa sama ada deque penuh menggunakan isFull().
   • Jika tidak, kurangkan penuding hadapan (dengan lilitan bulat menggunakan modulo).
   • Letakkan nilai di hadapan baharu dan naikkan saiz.

3. insertLast($value):

   • Periksa sama ada deque penuh.
   • Jika tidak, letakkan nilai di bahagian belakang dan gerakkan penuding belakang ke hadapan (sekali lagi menggunakan modulo untuk membalut sekeliling).
   • Naikkan saiz.

4. deleteFront():

   • Semak sama ada deque kosong menggunakan isEmpty().
   • Jika tidak, naikkan penunjuk hadapan (lilitan bulat) dan kurangkan saiznya.

5. deleteLast():

   • Periksa sama ada deque kosong.
   • Jika tidak, kurangkan penunjuk belakang dan kecilkan saiznya.

6. getFront():

   • Jika deque kosong, kembalikan -1.
   • Jika tidak, kembalikan elemen pada penuding hadapan.

7. getRear():

   • Jika deque kosong, kembalikan -1.
   • Jika tidak, kembalikan elemen sebelum penuding belakang semasa (memandangkan belakang menghala ke kedudukan tersedia seterusnya).

8. isKosong():

   • Kembalikan benar jika deque kosong (saiz ialah 0).

9. adalahPenuh():

   • Kembalikan benar jika deque penuh (saiz sama dengan maxSize).

Contoh Panduan

$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

Kerumitan Masa:

• Setiap operasi (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) berjalan dalam masa O(1) kerana semuanya melibatkan operasi tatasusunan masa tetap dan manipulasi penunjuk.

Kerumitan Ruang:

• Kerumitan ruang ialah O(k), dengan k ialah saiz deque. Kami memperuntukkan ruang untuk elemen k dalam tatasusunan deque.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• 領英
• GitHub

Atas ialah kandungan terperinci . Pekeliling Reka Bentuk Deque. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!