Struktur data dan algoritma dalam JavaScript (1): kemahiran stack_javascript

Prekata

Struktur Data dan Algoritma JavaScript ialah buku yang menerangkannya dengan cara yang agak mudah Kelebihannya ialah ia menggunakan bahasa JavaScript untuk menerangkan struktur data yang biasa digunakan dalam buku itu, yang boleh dianggap mengikut peredaran masa, saya menontonnya sebagai seorang amatur dan merakamnya

muat turun kod git: https://github.com/JsAaron/data_structure.git

Struktur tindanan

Senarai khas, elemen dalam tindanan hanya boleh diakses melalui satu hujung senarai, bahagian atas tindanan

Struktur data terakhir-masuk-dahulu (LIFO, terakhir-masuk-dahulu)

Javascript menyediakan kaedah yang boleh dikendalikan, tolak dan pop, tetapi pop akan mengalih keluar data dalam tindanan

Kelas pelaksanaan yang melaksanakan tindanan

Struktur data asas menggunakan tatasusunan

Oleh kerana pop memadamkan data dalam tindanan, anda perlu melaksanakan kaedah carian mengintip

Melaksanakan kaedah pembersihan yang jelas

Cari jumlah bilangan elemen dalam panjang tindanan

Periksa sama ada masih terdapat unsur kosong

Salin kod Kod adalah seperti berikut:

fungsi Tindanan(){
This.dataStore = []
This.top = 0;
This.push = tolak
This.pop = pop
This.peek = jenguk
This.length = panjang;
}

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

fungsi intip(elemen){
Kembalikan this.dataStore[this.top-1];
}

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

fungsi clear(){
This.top = 0
}

panjang fungsi(){
Kembalikan ini. atas
}

Palindrom

Palindrom merujuk kepada perkataan, tatasusunan atau frasa yang sama dari hadapan ke belakang 12321.abcba

Idea paling mudah tentang palindrom ialah jika unsur itu diterbalikkan dan sama dengan unsur asal, ia bermakna ia adalah palindrom

Anda boleh menggunakan kelas tindanan ini untuk beroperasi di sini

Salin kod Kod adalah seperti berikut:

fungsi ialahPalindrome(perkataan) {
var s = Timbunan baharu()
untuk (var i = 0; i < word.length; i ) {
s.tolak(perkataan[i])
}
var rword = "";
manakala (s.length() > 0) {
         rword = s.pop();
}
Jika (perkataan == rword) {
        kembali benar;
} lain {
         kembali palsu;
}
}

isPalindrome("aarra") //palsu
isPalindrome("aaraa") //benar

Lihat fungsi isPalindrome ini, ia sebenarnya memanggil kelas Tindanan, dan kemudian menolak elemen perkataan yang dihantar ke setiap unit terurai ke dalam tindanan, prinsip penggunaan terakhir, keluar dahulu kaedah pop untuk membuka elemen ini, dan akhirnya membandingkan pemasangan sebelum dan selepas Jika ia adalah sama, ia adalah palindrom

Rekursi

Gunakan rekursi untuk melaksanakan algoritma faktorial

5! = 5 * 4 * 3 * 2 * 1 = 120

Gunakan rekursi

Salin kod Kod adalah seperti berikut:

fungsi faktorial(n) {
Jika (n === 0) {
Pulangan 1;
} lain {
          pulangan n * faktorial(n - 1);
}
}

Gunakan operasi tindanan

Salin kod Kod adalah seperti berikut:

fakta fungsi(n) {
var s = Timbunan baharu()
manakala (n > 1) {
              //[5,4,3,2]
s.push(n--);
}
var produk = 1;
manakala (s.length() > 0) {
Produk *= s.pop();
}
Kembalikan produk;
}

fakta(5) //120

Tolak n = 5 secara beransur-ansur ke atas tindanan melalui sambil, dan kemudian melalui gelung atau mengikut prinsip keluar-masuk-dahulu tindanan, keluarkan yang paling hadapan dan tindanan dengan produk melalui kaedah pop