Penjelasan terperinci tentang struktur data JavaScript dan kemahiran stack_javascript algoritma

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:

Salin kod Kod adalah seperti berikut:

function Stack() {
This.dataStore = [];
This.top = 0;
}

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:

Salin kod Kod adalah seperti berikut:

tolak fungsi(elemen) {
This.dataStore[this.top] = elemen;
}

2. Kaedah pop() adalah bertentangan dengan kaedah push()---ia mengembalikan elemen teratas tindanan dan mengurangkan nilai teratas sebanyak 1. Kod berikut:

Salin kod Kod adalah seperti berikut:

fungsi pop(){
         kembalikan this.dataStore[--this.top];
}

3. Kaedah peek() mengembalikan elemen pada kedudukan 1 teratas tatasusunan, iaitu elemen teratas timbunan;

Salin kod Kod adalah seperti berikut:

Fungsi mengintip(){
          kembalikan this.dataStore[this.top - 1];
}

4. kaedah length() Kadangkala kita perlu tahu berapa banyak elemen yang terdapat dalam timbunan Kita boleh mengembalikan bilangan elemen dalam timbunan dengan mengembalikan nilai bahagian atas pembolehubah, seperti yang ditunjukkan dalam kod berikut:

Salin kod Kod adalah seperti berikut:

Panjang fungsi(){
           kembalikan ini. atas;
}

5. clear(); Kadangkala kita ingin mengosongkan timbunan, kita tetapkan nilai atas pembolehubah kepada kod berikut:

Salin kod Kod adalah seperti berikut:

fungsi clear() {

this.top = 0;

}

Semua kod di bawah:

Salin kod Kod adalah seperti berikut:

function Stack() {
This.dataStore = [];
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:

Salin kod Kod adalah seperti berikut:

fakta fungsi(n) {
var s = Timbunan baharu();
; sambil(n > 1) {
s.push(n--);
}
var produk = 1;
Manakala(s.length() > 0) {
Produk *= s.pop();
}
Kembalikan produk;
}
console.log(fakta(5));

Maksud kod di atas ialah: mula-mula masukkan nombor 5 ke dalam fungsi, gunakan gelung sementara, dan tolak fungsi push() menggunakan tindanan ke dalam tindanan sebelum mengurangkannya sebanyak 1 setiap kali sehingga pembolehubah n adalah kurang daripada 1. Kemudian tentukan produk pembolehubah; gunakan kaedah panjang() timbunan untuk menentukan sama ada ia lebih besar daripada 0 dan laksanakan produk* = s.pop() setiap kali kaedah pop() mengembalikan elemen atas timbunan dan memadam elemen daripada timbunan. Jadi setiap kali ia dilaksanakan, satu elemen dipadamkan sehingga s.length() <= 0. Jadi produk = 5*4*3*2*1 dan operasi lain.