Penggunaan fungsi ENQUE pada PHP

Indonesian (Bahasa Indonesia) translation by Fajar Bahri (you can also view the original English article)

Dua dari struktur data yang paling umum digunakan dalam pengembangan web adalah stack dan queue. Banyak pengguna internet, termasuk web developer, tidak menyadari fakta menakjubkan ini. Jika Anda adalah salah satu pengembang ini, kemudian mempersiapkan diri untuk mencerahkan dua contoh: operasi 'undo' editor teks menggunakan setumpuk untuk mengatur data; event-loop dari browser web, yang menangani event (klik, hoovers, dll), menggunakan antrian untuk mengolah data.

Sekarang berhenti sejenak dan bayangkan berapa kali kami, pengguna dan pengembang, mengunakan stack dan queue. Itu menakjubkan, kan? Karena mereka ubiquity dan kesamaan dalam desain, saya telah memutuskan untuk menggunakan mereka untuk memperkenalkan Anda struktur data.

Stack

Dalam ilmu komputer, stack adalah struktur data linier. Jika pernyataan ini memegang nilai marjinal untuk Anda, seperti aslinya dengan saya, pertimbangkan ini alternatif: stack mengatur data ke berurutan.

Berurutan ini sering digambarkan sebagai tumpukan hidangan di kafetaria. Ketika piring ditambahkan ke tumpukan piring, piring mempertahankan urutan ketika ditambahkan; Selain itu, ketika piring ditambahkan, itu mendorong menuju bagian bawah tumpukan. Setiap kali kita menambahkan piring baru, piring mendorong menuju bagian bawah tumpukan, tapi ini juga merupakan bagian atas tumpukan piring.

Proses ini menambahkan piring akan mempertahankan urutan ketika setiap piring ditambahkan ke dalam tumpukan. Mengurangi piring dari tumpukan juga akan mempertahankan urutan semua piring. Jika piring dihapus dari atas tumpukan, setiap piring lain di tumpukan akan tetap mempertahankan urutan yang benar dalam tumpukan. Apa yang saya jelaskan, mungkin terlalu banyak kata, adalah bagaimana piring ditambahkan dan dikurangi dibanyak kafetaria!

Untuk memberikan contoh yang lebih teknis dari tumpukan, mari kita ingat 'undo' pengoperasian sebuah editor teks. Setiap kali teks ditambahkan ke editor teks, teks ini didorong ke dalam tumpukan. tambahan pertama untuk editor teks yang mewakili bagian bawah tumpukan; perubahan terbaru mewakili bagian atas tumpukan. Jika pengguna ingin membatalkan perubahan, bagian atas tumpukan akan dihapus. Proses ini dapat diulang sampai ada penambahan tumpukan, yang merupakan sebuah file kosong tidak lebih!

Operasi Stack

Karena kita sekarang memiliki model konseptual dari tumpukan, mari kita menetapkan dua operasi tumpukan:

• push(data) menambahkan data.
• pop() menghapus data paling baru yang ditambahkan.

Implementasi Stack

Sekarang mari kita menulis kode untuk tumpukan!

Properti dari Stack

Untuk implementasi kita, kami akan membuat constructor yang bernama Stack. Setiap instnace Stack akan memiliki dua properti: _size dan _storage.

function Stack() {
    this._size = 0;
    this._storage = {};
}

this._storage  memungkinkan setiap instace Stack untuk memiliki sendiri wadah untuk menyimpan data; this._size ini mencerminkan jumlah berapa kali data terdorong ke versi terbaru dari Stack. Jika sebuah instance baru dari Stack dibuat dan data didorong ke dalam penyimpanan, kemudian this._size ini akan meningkat 1. Jika data didorong, sekali lagi, ke dalam tumpukan, this._size ini akan meningkat ke 2. Jika data yang dihapus dari tumpukan, kemudian this._size ini akan mengurangi ke 1.

Metode stack

Kita perlu menentukan metode yang dapat menambah (push) dan menghapus (pop) data dari tumpukan. Mari kita mulai dengan mendorong data.

Metode 1 dari 2: push(data)

(Metode ini dapat dibagi di antara semua contoh dari Stack, sehingga kami akan menambahkannya ke prototype dari Stack.)

Kami memiliki dua persyaratan untuk metode ini:

1. Setiap kali kita menambahkan data, kami ingin menaikan ukuran stack kami.
2. Setiap kali kita menambahkan data, kami ingin mempertahankan urutan di mana itu ditambahkan.

Stack.prototype.push = function(data) {
    // increases the size of our storage
    var size = this._size++;

    // assigns size as a key of storage
    // assigns data as the value of this key
    this._storage[size] = data;
};

Implementasi push(data) kami mencakup logika berikut. Mendeklarasikan variabel bernama size dan menetapkan nilai ini this._size++. Menetapkan size sebagai kunci dari this._storage ini. Dan menetapkan data sebagai nilai dari sebuah kunci yang sesuai.

Jika stack kami memanggil push(data) lima kali, maka ukuran stack kami menjadi 5. Push pertama ke tumpukan akan menetapkan bahwa data tombol 1 di this._storage . menjalankan lima kali push(data) akan menetapkan bahwa data kunci 5 di this.._storage. Kami baru saja memberikan urutan kepada data kami!

Metode 2 2: pop()

Kita sekarang bisa mendorong data ke tumpukan; langkah logis berikutnya adalah popping (menghapus) data dari tumpukan. Popping data dari tumpukan tidak hanya menghapus data; itu adalah menghapus hanya data yang paling baru dari tumpukan.

Berikut adalah tujuan kami untuk metode ini:

1. Menggunakan ukuran tumpukan saat ini untuk mendapatkan data yang paling baru ditambahkan.
2. Menghapus data paling baru ditambahkan.
3. Pengurangan _this._size oleh satu.
4. Kembalikan data yang baru saja dihapus.

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    deletedData = this._storage[size];

    delete this._storage[size];
    this.size--;

    return deletedData;
};

pop() bertemu 4 tujuan kami. Pertama, kita mendeklarasikan dua variabel: size diinisialisasi ke ukuran tumpukan; deletedData di assign untuk data baru yang ditambahkan ke tumpukan. Kedua, kami menghapus key-value pair data yang paling baru ditambahkan. Ketiga, kita mengurangi ukuran tumpukan oleh 1. Keempat, kita kembalikan data yang dihapus dari tumpukan.

Jika kita menguji implementasi pop() kami saat ini, kita menemukan bahwa ia bekerja sesuai dengan kasus penggunaan. Jika kita push(data) data ke tumpukan, ukuran tumpukan akan menambahkan satu. Jika kita pop() data dari tumpukan kami, ukuran dai tumpukan dikurangi oleh satu.

Masalah muncul, namun, ketika kita membalik urutan pemanggilan. Pertimbangkan skenario berikut: kita memanggil pop() dan kemudian push(data). Ukuran tumpukan perubahan ke -1 dan kemudian ke 0. Tapi ukuran yang benar dari tumpukan kami adalah 1!

Menangani kasus penggunaan ini, kita akan menambahkan jika if ke pop().

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    if (size) {
        deletedData = this._storage[size];

        delete this._storage[size];
        this._size--;

        return deletedData;
    }
}; 

Dengan penambahan if statement, body kode kita hanya dijalankan ketika ada data di storage kami.

Implementasi lengkap Stack

 Implementasi lengkap Stack. Terlepas dari urutan di mana kita memanggil salah satu metode kami, kode kita bekerja! Berikut ini adalah versi akhir kode kami:

function Stack() {
    this._size = 0;
    this._storage = {};
}

Stack.prototype.push = function(data) {
    var size = ++this._size;
    this._storage[size] = data;
};

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    if (size) {
        deletedData = this._storage[size];

        delete this._storage[size];
        this._size--;

        return deletedData;
    }
}; 

Dari tumpukan untuk antrian

Tumpukan berguna ketika kami ingin menambahkan data secara berurutan dan menghapus data. Berdasarkan definisi, tumpukan hanya menghapus data yang paling baru ditambahkan. Apa yang terjadi jika kita ingin menghapus data paling lama? Kami ingin menggunakan struktur data yang bernama antrian.

Antrian

Mirip dengan tumpukan, antrian adalah struktur data linier. Tidak seperti tumpukan, antrian menghapus hanya data paling dulu dimasukan.

Untuk membantu Anda konsep bagaimana ini bekerja, mari kita luangkan waktu untuk menggunakan analogi. Bayangkan antrian yang sangat mirip dengan sistem tiket Deli. Setiap pelanggan mengambil tiket dan dilayani ketika nomor mereka disebut. Pelanggan yang membutuhkan tiket pertama harus dilayani pertama.

Bayangkan lebih lanjut bahwa tiket ini memiliki nomor "satu" ditampilkan di atasnya. Tiket berikutnya memiliki nomor "dua" ditampilkan di atasnya. Pelanggan yang membutuhkan tiket kedua akan dilayani kedua. (Jika sistem tiket kami beroperasi seperti tumpukan, pelanggan yang memasuki tumpukan pertama akan menjadi yang terakhir untuk dilayani!)

Sebuah contoh yang lebih praktis dari antrian adalah event-loop dari web browser. Seperti event berbeda yang dipicu, seperti klik tombol, mereka ditambahkan ke event-loop antrian dan ditangani dalam urutan mereka memasuki antrian.

Operasi antrian

Karena kita sekarang memiliki model konseptual dari suatu antrian, mari kita mendefinisikan operasi. Ketika Anda akan melihat, operasi antrian sangat mirip dengan tumpukan. Perbedaannya terletak di mana data dihapus.

• enqueue(data) menambahkan data untuk antrian.
• dequeue menghilangkan data paling dulu ditambahkan ke antrian.

Penerapan antrian

Sekarang mari kita menulis kode untuk antrian!

Properti antrian

Untuk implementasi kami, kami akan membuat constructor yang bernama Queue. Kita kemudian akan menambahkan tiga properti: _oldestIndex, _newestIndex, dan _storage. Kebutuhan untuk _oldestIndex dan _newestIndex akan menjadi jelas di bagian berikutnya.

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Metode antrian

Sekarang kita akan menciptakan tiga metode bersama antara semua contoh dari antrian: size(), enqueue(data) dan dequeue(data). Saya akan menjelaskan tujuan untuk setiap metode, mengungkapkan kode untuk setiap metode, dan kemudian menjelaskan kode untuk setiap metode.

Metode 1 3: size()

Kami memiliki dua tujuan untuk metode ini:

1. Mengembalikan ukuran yang benar untuk antrian.
2. Mempertahankan berbagai barisan kunci untuk antrian.

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

Menerapkan size() mungkin tampak sepele, tetapi Anda akan segera menemukan bahwa itu tidak benar. Untuk memahami mengapa, kita harus cepat kembali melihat bagaimana size dilaksanakan untuk tumpukan.

Menggunakan model konseptual tumpukan, mari kita bayangkan bahwa kami mendorong lima piring ke tumpukan. Ukuran stack kami adalah lima dan setiap piring memiliki nomor yang terkait dengan itu dari satu (pertama ditambahkan piring) hinggi lima (piring terakhir yang ditambahkan). Jika kami menghapus tiga piring, maka kita memiliki dua piring. Kita hanya dapat mengurangi tiga dari lima untuk mendapatkan ukuran yang benar, yang merupakan dua. Berikut adalah titik paling penting tentang ukuran tumpukan: ukuran saat ini mewakili kunci yang bena yang terkait dengan piring di atas tumpukan (2) dan piring lain dalam tumpukan (1). Dengan kata lain, jarak kunci adalah selalu dari ukuran saat ini 1.

Sekarang, mari kita menerapkan pelaksanaan susunan size ke antrian kami. Bayangkan bahwa lima pelanggan mengambil tiket dari sistem tiket kami. Pelanggan pertama memiliki tiket menampilkan nomor 1 dan pelanggan kelima memiliki tiket menampilkan angka 5. Dengan antrian, pelanggan dengan tiket pertama dilayani pertama.

Sekarang bayangkan bahwa pelanggan pertama dilayani dan bahwa tiket ini akan dihapus dari antrian. Mirip dengan tumpukan, kita bisa mendapatkan ukuran yang benar dari antrian kami dengan mengurangi 1 dari 5. Antrian kami saat ini memiliki empat tiket yang belum terlayani. Sekarang, ini adalah mana masalah muncul: ukuran tidak lagi mewakili nomor tiket yang benar. Jika kita hanya mengungi satu dari lima, kita akan memiliki ukuran 4. Kami tidak dapat menggunakan 4 untuk menentukan rentang saat ini tiket tersisa dalam antrian. Apakah kita memiliki tiket dalam antrian dengan angka-angka dari 1 sampai 4 atau dari 2 sampai 5? Jawabannya tidak jelas.

Ini adalah manfaat dari memiliki dua properti berikut dalam antrian: _oldestIndex dan _newestIndex. Semua ini mungkin tampak membingungkan-aku masih kadang-kadang bingung. Apa yang membantu saya merasionalisasi semuanya adalah contoh berikut yang telah saya kembangkan.

Bayangkan bahwa deli kami memiliki dua sistem tiket:

1. _newestIndex merupakan sebuah tiket dari pelanggan ticketing sistem.
2. _oldestIndex merupakan sebuah tiket dari karyawan ticketing sistem.

Inilah konsep yang paling sulit untuk dipahami dalam hal memiliki dua sistem tiket: ketika angka-angka dalam kedua sistem identik, setiap pelanggan dalam antrian telah ditangani dan antrian kosong. Kita akan menggunakan skenario berikut untuk memperkuat logika ini:

1. Pelanggan mengambil tiket. Nomor tiket pelanggan, yang Diperoleh dari _newestIndex, adalah 1. Tiket tersedia dalam sistem tiket pelanggan berikutnya adalah 2.
2. Karyawan tidak mengambil Tiket, dan tiket dalam sistem tiket karyawan adalah 1.
3. Kami mengambil nomor tiket yang saat ini dalam sistem pelanggan (2) dan mengurangi jumlah dalam sistem karyawan (1) untuk mendapatkan nomor 1. Nomor 1 mewakili jumlah tiket masih dalam antrian yang belum dihapus.
4. Karyawan mengambil tiket dari sistem tiket mereka. Tiket ini mewakili tiket Pelanggan yang dilayani. Tiket yang dilayani dan Diperoleh dari _oldestIndex, yang menampilkan nomor 1.
5. Kami ulangi langkah 4, dan sekarang perbedaan adalah nol-tidak ada lagi tiket dalam antrian!

Kami sekarang memiliki properti (_newestIndex) yang dapat memberitahu kami jumlah terbesar (kunci) yang di assign di antrian dan properti (_oldestIndex) yang dapat memberitahu kami nomor index paling lama (kunci) dalam antrian.

Kami telah cukup mengeksplorasi size(), jadi mari kita sekarang pindah ke enqueue(data).

Metode 2 3: enqueue(data)

Untuk enqueue, kami memiliki dua tujuan:

1. Menggunakan _newestIndex sebagai kunci dari this._storage ini dan data apapun untuk ditambahkan sebagai nilai kunci itu.
2. Peningkatan nilai _newestIndex oleh 1.

Berdasarkan kedua tujuan, kita akan membuat pelaksanaan enqueue(data) berikut:

Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};

body metode ini mengandung dua baris kode. Pada baris pertama, kami menggunakan this._newestIndex ini untuk membuat kunci baru untuk this._storage dan menetapkan data untuk itu. this._newestIndex  selalu dimulai di 1. Pada baris kode yang kedua, kita menaikan this._newestIndex oleh 1, yang update nilai ke 2.

Itu adalah semua kode yang kita butuhkan untuk enqueue(data). Mari kita sekarang menerapkan dequeue().

Metode 3 3: dequeue()

Berikut adalah tujuan untuk metode ini:

1. Menghapus data terlama dalam antrian.
2. Menaikan _oldestIndex oleh satu.

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        deletedData = this._storage[oldestIndex];

    delete this._storage[oldestIndex];
    this._oldestIndex++;

    return deletedData;
};

Di dalam body dari dequeue(), kita mendeklarasikan dua variabel. Variabel pertama, oldestIndex, ditetapkan antrian nilai saat ini untuk this._oldestIndex. variable kedua, deletedData, diberi nilai yang terkandung dalam this._storage[oldestIndex].

Selanjutnya, kami menghapus index tertua dalam antrian. Setelah itu dihapus, kami menaikan this._oldestIndex oleh 1. Akhirnya, kita mengembalikan data yang bariu saja dihapus.

Mirip dengan masalah dalam pelaksanaan pop() kami pertama dengan tumpukan, pelaksanaan dequeue() kami tidak menangani situasi dimana data akan dihapus sebelum data apapun ditambahkan. Kita perlu menciptakan conditional untuk menangani kasus yang digunakan.

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};

Setiap kali nilai oldestIndex dan newestIndex tidak sama, maka kita mengeksekusi logika kita sebelumnya.

Implementasi lengkap Queue

Implementasi lengkap antrian kami. Mari kita lihat seluruh kode.

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};

Kesimpulan

Dalam artikel ini, kami sudah menjelajahi dua struktur data linier: tumpukan dan antrian. Tumpukan menyimpan data secara berurutan dan menghapus data paling baru-baru ini ditambahkan; antrian menyimpan data secara berurutan tetapi menghapus data yang ditambahkan paling lama.

Jika pelaksanaan struktur data ini tampaknya sepele, mengingatkan diri sendiri tentang tujuan dari struktur data. Mereka tidak dirancang untuk menjadi terlalu rumit; mereka dirancang untuk membantu kami mengatur data. Dalam konteks ini, jika Anda menemukan diri Anda dengan data yang perlu diatur secara berurutan, mempertimbangkan menggunakan stack atau antrian.