LeetCode 641: Desain Circular Deque

Question

Saya memposting solusi untuk "Design Circular Deque" LeetCode. Jika Anda ingin meninjau, lakukanlah. Terima kasih!

Masalah

Rancang implementasi Anda dari antrian berujung ganda melingkar (deque).

Penerapan Anda harus mendukung operasi berikut:

• MyCircularDeque(k): Konstruktor, atur ukuran deque menjadi k.
• insertFront(): Menambahkan item di depan Deque. Kembalikan nilai true jika operasi berhasil.
• insertLast(): Menambahkan item di belakang Deque. Kembalikan nilai true jika operasi berhasil.
• deleteFront(): Menghapus item dari depan Deque. Kembalikan nilai true jika operasi berhasil.
• deleteLast(): Menghapus item dari belakang Deque. Kembalikan nilai true jika operasi berhasil.
• getFront(): Mendapat item depan dari Deque. Jika deque kosong, kembalikan -1.
• getRear(): Mendapatkan item terakhir dari Deque. Jika deque kosong, kembalikan -1.
• isEmpty(): Memeriksa apakah Deque kosong atau tidak.
• isFull(): Memeriksa apakah Deque penuh atau tidak.

Contoh:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);            // return true
circularDeque.insertLast(2);            // return true
circularDeque.insertFront(3);           // return true
circularDeque.insertFront(4);           // return false, the queue is full
circularDeque.getRear();            // return 2
circularDeque.isFull();             // return true
circularDeque.deleteLast();         // return true
circularDeque.insertFront(4);           // return true
circularDeque.getFront();           // return 4

catatan:

• Semua nilai akan berada dalam kisaran [0, 1000].
• Jumlah operasi akan berada dalam kisaran [1, 1000].
• Harap jangan gunakan perpustakaan Deque bawaan.

Kode:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

struct MyCircularDeque {
        MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}

        const bool insertFront(
            const int value
        ) {
            if (isFull()) {
                return false;
            }

            stream[head] = value;
            --head;
            head += k;
            head %= k;
            ++counts;

            return true;
        }

        const bool insertLast(const int value) {
            if (isFull()) {
                return false;
            }

            stream[tail] = value;
            ++tail;
            tail %= k;
            ++counts;

            return true;
        }

        const bool deleteFront() {
            if (isEmpty()) {
                return false;
            }

            ++head;
            head %= k;
            --counts;

            return true;
        }

        const bool deleteLast() {
            if (isEmpty()) {
                return false;
            }

            --tail;
            tail += k;
            tail %= k;
            --counts;

            return true;
        }

        const int getFront() {
            return isEmpty() ? -1 : stream[(head + 1) % k];
        }

        const int getRear() {
            return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
        }

        const bool isEmpty() {
            return !counts;
        }

        const bool isFull() {
            return counts == k;
        }

    private:
        using ValueType = std::uint_fast16_t;
        std::vector<ValueType> stream;
        ValueType counts;
        ValueType k;
        ValueType head;
        ValueType tail;
}; 

Answer 1

• Menggunakan jenis yang sama untuk konten deque dan ukuran / indeks ( k, count, head, tail) terasa salah. Setidaknya, kdan countseharusnya std::vector::size_type.

• Karena Anda back up deque dengan std::vector, membuat headdan tailyang std::vector::iteratorterlihat lebih idiomatik.

• kbukanlah nama yang paling deskriptif. Pertimbangkan capacity.

• Saya tidak yakin itu std::vectoradalah wadah terbaik untuk mendukung deque ukuran tetap. Bagaimanapun, intinya std::vectoradalah memiliki ukuran yang dinamis. std::array, atau bahkan array C-style lama yang polos, terlihat lebih alami.

Answer 2

Anda dapat memanggil stream.reserve(k)konstruktor untuk meningkatkan efisiensi vektor karena Anda tahu bahwa Anda hanya akan memiliki kelemen, jadi .reserve()akan mengalokasikan memori sebelumnya.

Lebih suka menggunakan std::size_tlebih dariint
int k akanstd::size_t k

Anda belum mendeklarasikan konstruktor salinan atau operator penugasan salinan . Ini dapat menyebabkan masalah jika Anda ingin menugaskan satu Dequesama lain.

Inlining beberapa fungsi anggota Anda structseperti isEmpty(), getRear(), getFront() dapat meningkatkan kinerja wadah Anda, tetapi akan menjadi perdagangan untuk ruang.

Jika Anda melakukan ini hanya untuk menyelesaikan tantangan, Anda dapat mengabaikan bagian selanjutnya

Template

Saat ini, Anda dequepasti akan menggunakannya std::uint_fast16_t. Tapi bagaimana jika saya ingin membuat dequenama? Atau dequenilai desimal yang berbeda? Saya tidak bisa hanya membuat 15 kelas untuk masing-masing tipe data.

Oleh karena itu, saya akan menggunakan template dalam C ++ sehingga saya dapat membuat file generik deque .

Sintaksnya sederhana

template < typename T >
struct deque
{
    public:
        // public member functions
    private:
        std::vector< T > stream;
};

Nah saat ingin membuat deque baru, bisa dilakukan deque<any_data_type> my_deque.

Di mana pun Anda akan menggunakan ValueType, Anda menggantinya dengan T.

Apa yang dilakukan C ++ adalah ia mengambil any_data_typedan mengganti Tdengan tipe data tersebut selama waktu kompilasi . Menerapkan ini dalam program Anda akan mengajari Anda banyak hal tentang cara kerja template di C ++ yang akan membantu proyek Anda di masa mendatang.

Template di C ++

Answer 3

Saya pikir ini adalah tema untuk kode Anda:, di constmana Anda meletakkannya, tidak ada manfaatnya; dan hilang dari tempat lain yang seharusnya ada di sana. Setiap fungsi di dalam MyCircularDequeharus dibuang di constdepan, karena nilai kembalian itu skalar sehingga menandainya constsecara harfiah tidak berpengaruh. insertLast(const int value)memiliki efek yang sedikit lebih banyak tetapi sebenarnya tidak penting.

Tempat terpenting untuk meletakkannya constadalah mengubah keteguhan metode dan thisAnda . Mereka harus menambahkan setelah tanda kurung. Ini mendaftarkan janji bahwa metode tidak mengubah anggota apa pun.getisconst