Struktur Data JavaScript dan Algoritma Timbunan dan Queues

Punca pembelajaran

Saya pernah terjumpa siaran sebegitu semasa saya melayari V2EX.
Matematik diserahkan sepenuhnya kepada guru Saya ingin mempelajari beberapa matematik asas, mungkin di peringkat sekolah menengah Apakah buku yang anda cadangkan?
Poster yang menyiarkan mesej itu tidak mempunyai kursus matematik lanjutan di universiti dan telah terlibat dalam kerja hadapan apabila dia keluar bekerja. Saya rasa ilmu matematik saya kurang, jadi saya ingin mengejar matematik.
Selepas membaca jawatan itu, saya merasakan bahawa ia sangat serupa dengan saya, kerana jurusan saya tidak memerlukan matematik lanjutan, dan saya juga belajar front-end. Saya juga merasai kesukaran yang disebabkan oleh kekurangan pengetahuan matematik. Pada masa yang sama, kerana pemikiran matematik saya tidak begitu baik, saya memutuskan untuk bekerja keras untuk mempelajari asas matematik dan pengetahuan komputer.
Pada masa itu, beberapa orang juga berkata: "Apakah struktur dan algoritma data yang diperlukan untuk bahagian hadapan tetapi saya mempunyai pandangan saya sendiri mengenai perkara ini?"
Saya tidak fikir bahagian hadapan tidak memerlukan pengetahuan seperti algoritma Pada pendapat saya, bahagian hadapan mempunyai asas komputer yang kukuh, yang sangat bermanfaat untuk pembangunannya sendiri. Saya mahu menjadi seorang pengaturcara. Daripada menjadi front-end dan pengekod junior seumur hidup.
Ia boleh dianggap sebagai dorongan kepada diri saya sendiri. Lagipun, asas menentukan had atas, dan saya sangat berminat dengan komputer, jadi walaupun penat belajar, ia juga sangat gembira. Jadi saya pergi ke dalam talian dan membeli buku "Mempelajari Struktur dan Algoritma Data JavaScript", dan bersama-sama dengan buku "Struktur Data Dahua" yang saya pinjam dari perpustakaan, saya memulakan kajian awal saya tentang struktur dan algoritma data.

Operasi tatasusunan dalam JavaScipt

Langkah seterusnya ialah bahagian pertama struktur data, tindanan.
Tindanan ialah koleksi tersusun yang mengikut prinsip masuk-dahulu-keluar (LIFO, nama penuh: Terakhir Masuk Dahulu Keluar). Bahagian atas timbunan sentiasa merupakan elemen terbaharu.
Sebagai contoh: timbunan adalah seperti timbunan buku yang diletakkan di dalam kotak Jika anda ingin mengambil buku bahagian bawah, anda mesti mengeluarkan buku atas terlebih dahulu. (Sudah tentu, anda tidak boleh mengambil buku di bawah dahulu.)

Pelaksanaan tindanan dalam JavaScipt
Pertama, buat pembina.

/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

Salin selepas log masuk

Timbunan perlu mempunyai kaedah berikut:
push(element(s)): Tambahkan beberapa elemen pada bahagian atas tindanan
pop(): keluarkan dan kembalikan elemen atas timbunan
peek(): Mengembalikan elemen teratas timbunan
isAmpty: Semak sama ada tindanan kosong, jika kosong, kembalikan benar
jelas: keluarkan semua elemen daripada tindanan
saiz: Mengembalikan bilangan elemen dalam timbunan.
cetakan: Paparkan semua kandungan tindanan sebagai rentetan
Pelaksanaan kaedah tolak
Penjelasan: Elemen baharu perlu ditambahkan pada timbunan dan kedudukan elemen berada di hujung baris gilir. Dalam erti kata lain, kita boleh menggunakan kaedah tolak tatasusunan untuk mensimulasikan pelaksanaan.

Pelaksanaan:

/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

Salin selepas log masuk

Pelaksanaan kaedah pop

Penjelasan: Elemen teratas tindanan perlu dimunculkan dan mengembalikan nilai yang muncul pada masa yang sama. Anda boleh menggunakan kaedah pop tatasusunan untuk mensimulasikan pelaksanaan.
Pelaksanaan:

/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

Salin selepas log masuk

Pelaksanaan kaedah peek
Nota: Melihat elemen atas timbunan boleh dicapai dengan menggunakan panjang tatasusunan.
Pelaksanaan:

/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

Salin selepas log masuk

Pelaksanaan kaedah lain
Nota: Tiga yang pertama adalah teras kaedah tindanan, dan kaedah yang selebihnya disenaraikan di sini sekaligus. Kerana baris gilir yang akan dibincangkan di bawah akan sangat bertindih dengan bahagian ini.
Pelaksanaan:

/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

Salin selepas log masuk

Aplikasi Praktikal

Terdapat banyak aplikasi praktikal tindanan Terdapat fungsi dalam buku yang menukar perpuluhan kepada binari. (Jika anda tidak tahu cara mengira dalam binari, anda boleh menggunakan Baidu.) Berikut ialah kod sumber fungsi tersebut.
Prinsipnya ialah memasukkan nombor yang hendak ditukar, terus bahagi dua dan bulatkan. Dan akhirnya gunakan gelung sementara untuk menggabungkan semua nombor dalam tindanan menjadi rentetan untuk output.

/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

Salin selepas log masuk

Pada ketika ini, kajian tindanan akan berakhir. Kerana terdapat banyak komen dalam kod sumber, kandungan kod sumber tidak akan disiarkan di sini.

Baris Beratur

Baris gilir dan tindanan adalah struktur data yang hampir sama Perbezaannya ialah baris gilir keluar dahulu (FIFO: Mula-mula Masuk Dahulu).
Contohnya: Semasa beratur untuk membeli tiket di stesen kereta api, dahulukan dahulu. (Mereka yang melompat dalam barisan tidak dikira).

Pelaksanaan baris gilir dalam JavaScipt

Pelaksanaan baris gilir sangat serupa dengan tindanan. Yang pertama masih pembina:

/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

Salin selepas log masuk

Baris gilir perlu mempunyai kaedah berikut:

enqueue(element(s)): Tambahkan beberapa item pada penghujung baris gilir
dequeue(): Alih keluar item pertama baris gilir (iaitu, item teratas)
front(): Mengembalikan elemen pertama baris gilir, iaitu yang terbaharu ditambah
Kaedah selebihnya adalah sama seperti baris gilir

Pelaksanaan kaedah enqueue

Penerangan: Tambahkan beberapa item pada penghujung baris gilir.

Pelaksanaan:

/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

Salin selepas log masuk

Pelaksanaan kaedah dequeue

Penerangan: Alih keluar item pertama daripada baris gilir.

Pelaksanaan:

/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

Salin selepas log masuk

Pelaksanaan kaedah hadapan

Penerangan: Mengembalikan elemen pertama baris gilir, iaitu elemen terbaharu yang ditambahkan.

Pelaksanaan:

/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

Salin selepas log masuk

以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:

/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

 for (var i = 0; i < nameList.length; i++) {
  queue.enqueue(nameList[i]);
 }

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

Salin selepas log masuk

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。