Structures de données et algorithmes JavaScript, piles et files d'attente_Connaissances de base

Cause de l'apprentissage

Je suis tombé une fois sur un tel article alors que je parcourais V2EX.
Les mathématiques sont entièrement laissées à l'appréciation de l'enseignant. Je souhaite apprendre quelques mathématiques de base, probablement au niveau secondaire. Quels livres recommandez-vous ?
L'affiche qui a publié le message n'avait pas suivi de cours avancés de mathématiques à l'université et avait été engagé dans un travail de première ligne lorsqu'il se rendait au travail. J'ai l'impression que mes connaissances en mathématiques font défaut, je souhaite donc rattraper mon retard en mathématiques.
Après avoir lu l'article, j'ai l'impression qu'il me ressemble beaucoup, car ma spécialisation ne nécessite pas de mathématiques avancées et j'étudie également le front-end. J'ai aussi ressenti les difficultés causées par le manque de connaissances mathématiques. En même temps, parce que ma pensée mathématique n'est vraiment pas très bonne, j'ai décidé de travailler dur pour apprendre les bases des mathématiques et de l'informatique.
À cette époque, certaines personnes ont également dit : « Quelles structures de données et quels algorithmes sont nécessaires pour le front-end ? Mais j'ai mon propre point de vue sur cette question.
Je ne pense pas que le front-end n'ait pas besoin de connaissances telles que les algorithmes. À mon avis, le front-end dispose d'une base informatique solide, ce qui est extrêmement bénéfique pour son propre développement. Je veux être programmeur. Plutôt que d'être un front-end et un codeur junior à vie.
Cela peut être considéré comme un encouragement pour moi-même. Après tout, les bases déterminent la limite supérieure, et je m'intéresse beaucoup aux ordinateurs, donc même si c'est fatiguant d'apprendre, c'est aussi très heureux. Je suis donc allé en ligne et j'ai acheté le livre "Apprendre les structures et algorithmes de données JavaScript", et avec le livre "Structures de données Dahua" que j'ai emprunté à la bibliothèque, j'ai commencé mon étude préliminaire des structures de données et des algorithmes.

Opérations sur les tableaux dans JavaScipt

L'étape suivante est la première partie de la structure des données, la pile.
La pile est une collection ordonnée qui suit le principe du dernier entré, premier sorti (LIFO, nom complet : Last In First Out). Le haut de la pile est toujours l’élément le plus récent.
Par exemple : une pile est comme une pile de livres placée dans une boîte. Si vous souhaitez prendre le livre du bas, vous devez d'abord retirer le livre du haut. (Bien sûr, vous ne pouvez pas prendre le livre ci-dessous en premier.)

Implémentation de la stack en JavaScipt
Tout d’abord, créez un constructeur.

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

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

La pile doit avoir les méthodes suivantes :
push(element(s)) : Ajouter plusieurs éléments en haut de la pile
pop() : supprime et renvoie l'élément supérieur de la pile
peek() : renvoie l'élément supérieur de la pile
isAmpty : Vérifiez si la pile est vide, si elle est vide, retournez true
clear : supprime tous les éléments de la pile
size : renvoie le nombre d'éléments dans la pile.
print : Afficher tout le contenu de la pile sous forme de chaîne
Mise en place de la méthode push
Explication : Un nouvel élément doit être ajouté à la pile et la position de l'élément est à la fin de la file d'attente. En d’autres termes, nous pouvons utiliser la méthode push du tableau pour simuler l’implémentation.

Mise en œuvre :

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

Mise en place de la méthode pop

Explication : Il est nécessaire de faire apparaître l'élément supérieur de la pile et de renvoyer la valeur sautée en même temps. Vous pouvez utiliser la méthode pop du tableau pour simuler l'implémentation.
Mise en œuvre :

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

Mise en place de la méthode peek
Remarque : L'affichage de l'élément supérieur de la pile peut être obtenu en utilisant la longueur du tableau.
Mise en œuvre :

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

Mise en œuvre d'autres méthodes
Remarque : Les trois premières constituent le cœur de la méthode stack et les méthodes restantes sont répertoriées ici en même temps. Parce que la file d’attente dont il sera question ci-dessous chevauchera grandement cette partie.
Mise en œuvre :

/**
 * 确定栈是否为空
 * @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());
};

Application pratique

Il existe de nombreuses applications pratiques de la pile. Il existe une fonction dans le livre qui convertit le nombre décimal en binaire. (Si vous ne savez pas comment calculer en binaire, vous pouvez utiliser Baidu.) Voici le code source de la fonction.
Le principe est de saisir le nombre à convertir, de diviser par deux en continu et d'arrondir. Et enfin, utilisez une boucle while pour concaténer tous les nombres de la pile en une chaîne pour la sortie.

/**
 * 将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;
};

À ce stade, l'étude de la pile touche à sa fin. Comme le code source contient de nombreux commentaires, le contenu du code source ne sera pas publié ici.

File d'attente

La file d'attente et la pile sont des structures de données très similaires. La différence est que la file d'attente est premier entré, premier sorti (FIFO : First In First Out).
Par exemple : lorsque vous faites la queue pour acheter des billets à la gare, le premier arrivé est le premier. (Ceux qui font la queue ne sont pas comptés). N'est-ce pas facile à comprendre~

Implémentation de la file d'attente dans JavaScipt

L'implémentation de la file d'attente est très similaire à celle de la pile. Le premier est toujours le constructeur :

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

La file d'attente doit avoir les méthodes suivantes :
enqueue(element(s)) : Ajouter plusieurs éléments à la fin de la file d'attente
dequeue() : Supprime le premier élément de la file d'attente (c'est-à-dire l'élément le plus haut)
front() : renvoie le premier élément de la file d'attente, qui est le dernier
ajouté Le reste des méthodes est le même que la file d'attente

Mise en œuvre de la méthode de mise en file d'attente

Description : Ajoutez plusieurs éléments à la fin de la file d'attente.
Mise en œuvre :

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

Mise en œuvre de la méthode dequeue

Description : Supprimez le premier élément de la file d'attente.
Mise en œuvre :

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

Mise en œuvre de la méthode front

Description : Renvoie le premier élément de la file d'attente, qui est le dernier ajouté.
Mise en œuvre :

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

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

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

/**
 * 击鼓传花的小游戏
 * @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()
}

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

感想

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