Detaillierte Erläuterung der Stapel und Warteschlangen von js-Datenstrukturen und -Algorithmen

1. Definition

Stapel ist eine wichtige lineare Struktur. Stack ist eine last in first out (Last in first out, LIFO) lineare Liste, die Lösch- und Einfügevorgänge nur am Ende der Tabelle erfordert. Bei einem Stapel wird dieser Schwanz als oberer Teil des Stapels bezeichnet, und der entsprechende Kopf wird als unterer Teil des Stapels bezeichnet.

Stapeloperationen können nur am Ende dieser linearen Tabelle ausgeführt werden:
Die Stapeleinfügungsoperation (Push) wird Push genannt, auch Push oder Push genannt.

Der Stapellöschvorgang (Pop) wird als Stack-Popping bezeichnet.

2. Die sequentielle Speicherstruktur des Stapels

Da das Wesen des Stapels eine lineare Tabelle ist und die lineare Tabelle zwei Speicherformen hat, dann der Stapel ist außerdem unterteilt in Die sequentielle Speicherstruktur des Stapels und die Kettenspeicherstruktur des Stapels .

Sequentielle Speicherstruktur: Datenelemente werden in Speichereinheiten mit aufeinanderfolgenden Adressen gespeichert, und die logischen und physischen Beziehungen zwischen den Daten sind konsistent.

Zum Beispiel sieht die Array-Struktur unserer Programmiersprache so aus.

Kettenspeicherstruktur: Speichert Datenelemente in jeder Speichereinheit. Diese Gruppe von Speichereinheiten kann kontinuierlich oder diskontinuierlich sein.

Offensichtlich spiegelt die Speicherbeziehung der Datenelemente der Kettenspeicherstruktur nicht ihre logische Beziehung wider, daher muss ein Zeiger verwendet werden, um die Adresse des Datenelements zu speichern, damit die relevante Informationen können über die Adresse gefunden werden. Der Speicherort des zugehörigen Datenelements.

Der anfängliche Stapel enthält keine Daten, was als leerer Stapel bezeichnet wird. Zu diesem Zeitpunkt ist die Oberseite des Stapels die Unterseite des Stapels. Dann werden Daten von der Oberseite des Stapels eingegeben, die Ober- und Unterseite des Stapels werden getrennt und die aktuelle Kapazität des gesamten Stapels wird größer. Wenn Daten aus dem Stapel entnommen werden, bewegt sich die Oberseite des Stapels nach unten und die aktuelle Kapazität des gesamten Stapels wird kleiner.

3. Stapeloperationen

(1) Verwandte Empfehlungen:

/** * 
 * 栈的构造函数 
 * */ 
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

Beispielfreigabe für PHP-Array-basierte Stack- und Warteschlangenfunktionen

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Stapel und Warteschlangen von js-Datenstrukturen und -Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!