Di blog sebelumnya, saya memperkenalkan daftar berikut. Daftar adalah struktur paling sederhana, tetapi jika Anda ingin berurusan dengan beberapa struktur yang lebih kompleks, daftarnya terlihat terlalu sederhana, jadi kami membutuhkan beberapa struktur data yang mirip dengan daftar tetapi lebih kompleks - tumpukan. Tumpukan adalah struktur data yang efisien, karena data hanya dapat ditambahkan atau dihapus di bagian atas tumpukan, sehingga operasi ini sangat cepat dan mudah diimplementasikan.
1: Operasi di tumpukan.
Tumpukan adalah daftar khusus. Elemen -elemen dalam tumpukan hanya dapat diakses melalui salah satu ujung daftar, dan ujung ini adalah bagian atas tumpukan. Misalnya, saat mencuci piring di restoran, Anda hanya bisa mencuci piring atas terlebih dahulu. Setelah mencuci piring, Anda hanya bisa berbulu di bagian atas tumpukan hidangan. Tumpukan ini disebut struktur data "akhir-dalam-pertama" (LIFO).
Karena tumpukan memiliki karakteristik back-in, pertama-keluar, tidak ada elemen yang tidak ada di bagian atas tumpukan tidak dapat diakses. Untuk mendapatkan elemen dengan tumpukan rendah, elemen di atas harus dihapus terlebih dahulu. Dua operasi utama yang dapat kita lakukan dengan tumpukan adalah untuk mendorong elemen ke tumpukan dan memasukkan elemen ke tumpukan. Saat memasuki tumpukan, kita dapat menggunakan metode metode push (), dan ketika kita memakainya, kita dapat menggunakan metode pop (). Meskipun metode pop () dapat mengakses elemen di bagian atas tumpukan, setelah memanggil metode, elemen di bagian atas tumpukan secara permanen dihapus dari tumpukan. Metode lain yang kami gunakan adalah Peek (), yang hanya mengembalikan elemen teratas dari tumpukan tanpa menghapusnya.
Diagram kolom aktual dari tumpukan entri dan keluar tumpukan adalah sebagai berikut:
push (), pop () dan peek () adalah tiga metode utama tumpukan, tetapi tumpukan memiliki metode dan sifat lain. sebagai berikut:
clear (): Hapus semua elemen di tumpukan.
Length (): Catat jumlah elemen dalam tumpukan.
Dua: Implementasi tumpukan adalah sebagai berikut:
Kita dapat mulai dengan mengimplementasikan metode kelas tumpukan terlebih dahulu; sebagai berikut:
Salinan kode adalah sebagai berikut:
function stack () {
this.datastore = [];
this.top = 0;
}
Seperti di atas: Datastore menyimpan semua elemen di tumpukan. Top variabel mencatat posisi di bagian atas tumpukan dan diinisialisasi ke 0. Ini berarti bahwa posisi awal dari array yang sesuai di bagian atas tumpukan adalah 0, jika ada elemen yang didorong ke dalam tumpukan. Nilai variabel ini akan berubah sesuai.
Kami juga memiliki metode berikut: push (), pop (), peek (), clear (), length ();
1. Metode push (); Saat mendorong elemen baru ke dalam tumpukan, itu perlu disimpan dalam array yang sesuai dengan variabel atas, dan kemudian nilai teratas meningkat sebesar 1, sehingga menunjuk ke posisi berikutnya dalam array. Kode berikut:
Salinan kode adalah sebagai berikut:
fungsi push (elemen) {
this.datastore [this.top ++] = elemen;
}
2. Metode POP () berlawanan dengan metode push () - ia mengembalikan elemen teratas dan mengurangi nilai teratas dengan 1. Kode berikut:
Salinan kode adalah sebagai berikut:
fungsi pop () {
kembalikan this.datastore [-this.top];
}
3. Metode Peek () mengembalikan elemen pada posisi teratas array, yaitu elemen teratas dari tumpukan;
Salinan kode adalah sebagai berikut:
fungsi peek () {
kembalikan this.datastore [this.top - 1];
}
Metode 4. Panjang () Terkadang kita perlu tahu berapa banyak elemen yang ada di tumpukan. Kita dapat mengembalikan jumlah elemen dalam tumpukan dengan mengembalikan nilai teratas variabel, seperti yang ditunjukkan pada kode berikut:
Salinan kode adalah sebagai berikut:
panjang fungsi () {
kembalikan this.top;
}
5. clear (); Terkadang kami ingin menghapus tumpukan, dan kami menetapkan nilai teratas dari variabel ke 0; kode berikut:
Salinan kode adalah sebagai berikut:
function clear () {
this.top = 0;
}
Semua kode di bawah ini:
Salinan kode adalah sebagai berikut:
function stack () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// tekan elemen baru ke dalam tumpukan
push: function (elemen) {
this.datastore [this.top ++] = elemen;
},
// Akses elemen atas tumpukan, elemen teratas tumpukan dihapus secara permanen
pop: function () {
kembalikan this.datastore [-this.top];
},
// Mengembalikan elemen pada posisi top-1 di array, yaitu elemen teratas dari tumpukan
Peek: function () {
kembalikan this.datastore [this.top - 1];
},
// Berapa banyak elemen yang disimpan di tumpukan
panjang: function () {
kembalikan this.top;
},
// Bersihkan tumpukannya
CLEAR: function () {
this.top = 0;
}
};
Contoh demo adalah sebagai berikut:
var stack = stack baru ();
stack.push ("a");
stack.push ("b");
stack.push ("c");
console.log (stack.length ()); // 3
console.log (stack.peek ()); // C
var pop = stack.pop ();
console.log (muncul); // C
console.log (stack.peek ()); // B
stack.push ("d");
console.log (stack.peek ()); // D
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.peek ()); // belum diartikan
Di bawah ini kami dapat menerapkan definisi rekursif fungsi faktorial; Misalnya, 5! Faktorial 5! = 5 * 4 * 3 * 2 * 1;
Kode berikut:
Salinan kode adalah sebagai berikut:
fact fact (n) {
var s = stack baru ();
while (n> 1) {
S.Push (n--);
}
produk var = 1;
while (s.length ()> 0) {
Produk *= s.pop ();
}
produk pengembalian;
}
console.log (fakta (5));
Kode di atas berarti: Pertama lewati angka 5 ke dalam fungsi, gunakan loop sementara, dan sebelum mengurangi 1 setiap kali, push () dari fungsi yang Anda gunakan ke tumpukan hingga variabel n kurang dari 1. Kemudian tentukan produk variabel; Tentukan apakah lebih besar dari 0 dengan panjang () metode tumpukan, dan setiap kali produk* = s.pop () dieksekusi, metode POP () mengembalikan elemen atas tumpukan dan menghapus elemen dari tumpukan. Jadi setiap kali Anda mengeksekusi, hapus elemen sampai s.length () <= 0. jadi produk = 5*4*3*2*1. dll.