Explication détaillée des piles et des files d'attente des structures de données et des algorithmes js

1. Définition

La pile est une structure linéaire importante. Stack est une liste linéaire dernier entré, premier sorti (Last in first out, LIFO), qui nécessite des opérations de suppression et d'insertion uniquement à la fin du tableau. Pour une pile, cette queue est appelée le haut de la pile, et l'en-tête correspondant est appelé le bas de la pile.

Les opérations de pile ne peuvent être effectuées qu'à la fin de ce tableau linéaire :
L'opération d'insertion de pile (Push) est appelée push, également appelée push ou push.

L'opération de suppression de pile (Pop) est appelée stack popping.

2. La structure de stockage séquentielle de la pile

Parce que l'essence de la pile est une table linéaire et que la table linéaire a deux formes de stockage, alors la pile est également divisé en Structure de stockage séquentielle de la pile et structure de stockage en chaîne de la pile .

Structure de stockage séquentielle : les éléments de données sont stockés dans des unités de stockage avec des adresses consécutives, et les relations logiques et physiques entre les données sont cohérentes.

Par exemple, la structure de tableau de notre langage de programmation est comme ceci.

Structure de stockage en chaîne : stocke les éléments de données dans n'importe quelle unité de stockage. Ce groupe d'unités de stockage peut être continu ou discontinu.

De toute évidence, la relation de stockage des éléments de données dans la structure de stockage en chaîne ne reflète pas sa relation logique, donc un pointeur doit être utilisé pour stocker l'adresse de l'élément de données, afin que les informations pertinentes peut être trouvé grâce à l'adresse L'emplacement de l'élément de données associé.

La pile initiale ne contient aucune donnée, ce qu'on appelle une pile vide. À ce stade, le haut de la pile est le bas de la pile. Ensuite, les données entrent par le haut de la pile, le haut et le bas de la pile sont séparés et la capacité actuelle de l'ensemble de la pile devient plus grande. Lorsque les données sont extraites de la pile, le haut de la pile descend et la capacité actuelle de l'ensemble de la pile devient plus petite.

3. Opérations de pile

(1) Opérations de base

/** * 
 * 栈的构造函数 
 * */ 
function Stack() { 
 	// 用数组来模拟栈 
	this.dataStore = []; //底层数据结构是数组
	this.top = 0; //top应该是等于数组的length的
}
//栈需要有如下的方法
Stack.prototype = {
	/**
	 * 1. push()
	 * 向栈中压入一个新元素， 需要将其保存在数组中变量 top 所对
	 * 应的位置， 然后将 top 值加 1， 让top指向数组中下一个空位置
	 * 特别注意 ++ 操作符的位置， 它放在 this.top 的后面， 这样新入栈的元素就被放在
	 * top 的当前值对应的位置， 然后再将变量 top 的值加 1， 指向下一个位置
	 * */
	push:function(element){
		this.dataStore[this.top++] = element;
	},
	/**
	 * pop() 方法恰好与 push() 方法相反——它返回栈顶元素， 同时将变量 top 的值减 1
	 * 也可以改造一下,只--this.top,不返回栈顶元素
	 * */
	pop:function(){
		return this.dataStore[--this.top];
	},
	/**
	 * peek() 方法返回数组的第 top-1 个位置的元素， 即栈顶元素
	 * */
	peek:function(){
		return this.dataStore[this.top-1];
	},
	length:function(){
		return this.top;
	},
	clear:function(){
		 this.top = 0;
	}
};
//测试 Stack 类的实现
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());//length: 3
console.log(s.peek());//Bryan
var popped = s.pop();
console.log("The popped element is: " + popped);//The popped element is: Bryan
s.push("Cynthia");
s.clear();
console.log("length: " + s.length());//length: 0

Recommandations associées : <.>

Partage d'exemples de fonctions de pile et de file d'attente basées sur un tableau PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!