栈 - My Blog

一：栈数据结构

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同

一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

二：基于数组的栈

2.1：创建基于数组的栈

创建一个类来表示数组

class Stack {
    constructor(){	//构造函数
        this.items = []
    }
}

数组允许我们在任何位置进行添加和删除元素，但由于栈遵循先进后出原则，要对元素的删除和插入进行限制

声明一些方法

push(element(s))：添加一个（或几个）新元素到栈顶。

pop()：移除栈顶的元素，同时返回被移除的元素。

peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。

isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。

clear()：移除栈里的所有元素。

size()：返回栈里的元素个数。该方法和数组的 length 属性很类似。

2.2：向栈添加元素

添加元素到栈顶，即栈的末尾

由于是基于数组实现栈数据结构，所以我们可以使用数组的push方法

1
2
3

push(element){
    this.items.push(element)
}

2.3：从栈中移除元素

由于遵循后进先出的原则，因此移除的是最后加入的元素，所以可以使用数组的pop方法来实现

并且返回删除的元素

1
2
3

pop(){
	return this.items.pop()
}

2.4：查看栈顶元素

由于类的元素是由数组进行保存的，所以访问数组的最后一个元素可以用length - 1

1
2
3

peek(){
	return this.items[this.items.length - 1]
}

2.5：检查栈是否为空

如果栈为空返回true , 不为空返回false

1
2
3

isEmpty(){
	return this.items.length === 0
}

2.6：清空栈元素

1
2
3

clear() { 
 this.items = []
}

2.7：Stack类

class Stack {
    constructor(){	//构造函数
        this.items = []
    }
    push(element){	//添加
    	this.items.push(element)
	}
	pop(){			//删除
		return this.items.pop()
	}
	peek(){			//返回栈顶元素
		return this.items[this.items.length - 1]
	}
	isEmpty(){		//检查是否为空
		return this.items.length === 0
	}
	clear() { 		//清空栈元素
 		this.items = []
	}
}

三：基于JS对象的栈

创建一个 Stack 类最简单的方式是使用一个数组来存储其元素。在使用数组时，大部分方法的时间复杂度是 O(n)。O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的 n 代表数组的长度。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。

如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，那不是更好吗？对于使用 JavaScript 语言实现栈数据结构的场景，我们也可以使用一个JavaScript 对象来存储所有的栈元素，保证它们的顺序并且遵循 LIFO 原则。

3.1：创建基于对象的栈

使用一个count属性来帮助我们记录栈的大小小（也能帮助我们从数据结构中添加和删除元素）。

class Stack{	
	constructor() { 	//构造
 		this.count = 0; 
 		this.items = {}; 
 	}  
}

3.2：向栈中插入元素

JavaScript 中，对象是一系列键值对的集合。要向栈中添加元素，我们将使用 count 变量，作为 items 对象的键名，插入的元素则是它的值。在向栈插入元素后，我们递增 count 变量。

push(element){
	this.items[this.count] = element
	this.count++
}

3.3：检查栈是否为空和它的大小

count 属性也表示栈的大小。因此，我们可以简单地返回 count 属性的值来实现 size 方法。

1
2
3

size() { 
 	return this.count
}

要验证栈是否为空，可以像下面这样判断 count 的值是否为 0。

1
2
3

isEmpty() { 
 	return this.count === 0
}

3.4：从栈中弹出元素

pop() { 
 	 if(this.isEmpty()) { // 检查栈是否为空，为空返回undefined
	 return undefined; 
 } 
 	 this.count--; 
	 const result = this.items[this.count]; // 保存栈顶元素值，以便返回
 	 delete this.items[this.count]; //delete关键字，从对象中删除特定的值
 	 return result; // 
}

3.5：查看栈顶元素和清空栈

查看栈顶元素

peek(){
	if(this.isEmpty()){
		return undefined
	}
	return this.items[this.count - 1]
}

清空栈

clear() { 
 	this.items = {}
 	this.count = 0
}

3.6：创建toString方法

如果栈是空的，我们只需返回一个空字符串即可。如果它不是空的，就需要用它底部的第一个元素作为字符串的初始值，然后迭代整个栈的键，一直到栈顶，添加一个逗号（,）以及下一个元素。

toString() { 
	 if (this.isEmpty()) { 
 	 return ''; 
 } 
 let objString = `${this.items[0]}`
 for (let i = 1; i < this.count; i++) { 
 	 objString = `${objString},${this.items[i]}`
 } 
 return objString; 
}