Detailed explanation of stacks and queues of js data structures and algorithms

1. Definition

The stack is an important linear structure. The stack is a last in first out (Last in first out, LIFO) linear table, which requires deletion and insertion operations only at the end of the table. For a stack, this tail is called the top of the stack, and the corresponding header is called the bottom of the stack.

Stack operations can only be performed at the end of this linear table:
The insertion operation (Push) of the stack is called pushing, also called pushing or pushing.

The stack deletion operation (Pop) is called stack popping.

2. The sequential storage structure of the stack

Because the essence of the stack is a linear table, and the linear table has two storage forms, the stack is also divided into The stack's sequential storage structure and the stack's chained storage structure.

Sequential storage structure: data elements are stored in storage units with consecutive addresses, and the logical and physical relationships between the data are consistent.

For example, the array structure of our programming language is like this.

Chained storage structure: stores data elements in any storage unit. This group of storage units can be continuous or discontinuous. .

Obviously, in this way, the storage relationship of data elements in the chain storage structure does not reflect its logical relationship, so a pointer needs to be used to store the address of the data element, so that the relevant information can be found through the address. The location of the associated data element.

The initial stack does not contain any data, which is called an empty stack. At this time, the top of the stack is the bottom of the stack. Then data enters from the top of the stack, the top of the stack and the bottom of the stack are separated, and the current capacity of the entire stack becomes larger. When data is popped from the stack, the top of the stack moves down, and the current capacity of the entire stack becomes smaller.

3. Stack operation

(1).Basic operation

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

Related recommendations:

PHP array-based stack and queue function example sharing

The above is the detailed content of Detailed explanation of stacks and queues of js data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!