Dalam artikel sebelum ini blog memperkenalkan senarai berikut ialah struktur yang paling mudah, tetapi jika anda ingin menangani beberapa struktur yang lebih kompleks, senarai itu terlalu mudah, jadi kami memerlukan beberapa jenis. daripada dan Senarai adalah serupa tetapi struktur data yang lebih kompleks - tindanan. Tindanan ialah struktur data yang cekap kerana data hanya boleh ditambah atau dipadamkan di bahagian atas tindanan, jadi operasi ini pantas dan mudah dilaksanakan.
1: Operasi pada tindanan.
Timbunan ialah jenis senarai khas Elemen dalam tindanan hanya boleh diakses melalui satu hujung senarai, iaitu bahagian atas tindanan. Sebagai contoh, semasa membasuh pinggan di restoran, anda hanya boleh mencuci pinggan atas dahulu Selepas pinggan dicuci, ia hanya boleh diskrukan ke bahagian atas timbunan pinggan. Tindanan ialah struktur data yang dipanggil "masuk terakhir, keluar dahulu" (LIFO).
Memandangkan tindanan mempunyai ciri keluar-masuk-dahulu, mana-mana elemen yang tidak berada di bahagian atas tindanan tidak boleh diakses Untuk mendapatkan elemen di bahagian bawah tindanan, elemen di atas mestilah dikeluarkan dahulu. Dua operasi utama yang boleh kita lakukan pada timbunan ialah menolak elemen ke dalam timbunan dan mengeluarkan elemen dari timbunan. Kita boleh menggunakan kaedah push() untuk menolak ke dalam tindanan, dan kaedah pop() untuk keluar dari tindanan. Walaupun kaedah pop() boleh mengakses elemen di bahagian atas tindanan, selepas memanggil kaedah ini, elemen di bahagian atas tindanan dipadamkan secara kekal daripada tindanan. Kaedah lain yang biasa digunakan ialah peek(), yang hanya mengembalikan elemen teratas timbunan tanpa memadamkannya.
Rajah sebenar menolak dan meletus pada tindanan adalah seperti berikut:
push(), pop() dan peek() ialah tiga kaedah utama tindanan, tetapi tindanan mempunyai kaedah dan sifat lain. Seperti berikut:
clear(): Kosongkan semua elemen dalam tindanan.
length(): Rekod bilangan elemen dalam tindanan.
2: Pelaksanaan tindanan adalah seperti berikut:
Kita boleh mulakan dengan melaksanakan kaedah kelas tindanan seperti berikut:
Seperti di atas: dataStore menyimpan semua elemen dalam tindanan. Bahagian atas pembolehubah merekodkan kedudukan bahagian atas tindanan dan dimulakan kepada 0. Ini bermakna kedudukan permulaan tatasusunan yang sepadan dengan bahagian atas tindanan ialah 0, jika elemen ditolak ke tindanan. Nilai pembolehubah akan berubah dengan sewajarnya.
Kami juga mempunyai kaedah berikut: push(), pop(), peek(), clear(), length();
1. Kaedah Push(); apabila menolak elemen baharu ke dalam timbunan, ia perlu disimpan dalam kedudukan yang sepadan dengan bahagian atas pembolehubah dalam tatasusunan, dan kemudian nilai teratas dinaikkan sebanyak 1 untuk menunjuk ke seterusnya kedudukan dalam tatasusunan. Kod berikut:
this.top = 0;
}
Stack.prototype = {
//Tolak elemen baharu ke dalam tindanan
Tekan: fungsi(elemen) {
This.dataStore[this.top] = elemen;
},
// Akses elemen atas tindanan, elemen atas tindanan dipadamkan secara kekal
pop: function(){
kembalikan this.dataStore[--this.top];
},
// Kembalikan elemen pada kedudukan teratas-1 dalam tatasusunan, iaitu elemen atas tindanan
intip: function(){
kembalikan this.dataStore[this.top - 1];
},
//Berapa banyak elemen yang disimpan dalam tindanan
panjang: fungsi(){
kembalikan ini. atas;
},
//Kosongkan timbunan
; jelas: function(){
This.top = 0;
}
};
Contoh demo adalah seperti berikut:
Timbunan var = Timbunan baharu();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c
var muncul = 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()); // undefined
Di bawah ini kita boleh melaksanakan definisi rekursif bagi fungsi faktorial seperti 5! Faktorial bagi 5! = 5 * 4 * 3 * 2 * 1;
Kod berikut: