利用JS实现栈

栈是一种遵从先进后出原则的有序集合。

新添加或者待删除的元素都保存在栈顶，另一端就叫做栈底。

在栈里，新元素都靠近栈顶，旧元素都接近栈底

我们先来利用JS实现一个基于数组的栈

由于数组允许我们在任何位置添加和删除元素，但是栈由于有先进后出的原则，所以我们需要对元素的插入和删除功能进行一些限制。

接下来我们需要为栈声明一些方法

push(element(s)):添加一个（或多个）新元素到栈顶

pop():移除栈顶的元素，并且返回被移除的元素

peek():返回栈顶的元素，不对栈做任何修改

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

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

size():返回栈里的元素个数

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 = [];
	}

	// 返回栈里的元素个数
	size() {
		return this.items.length;
	}
}

基于数组的栈我们已经实现了

但是在处理大量数据的时候，我们需要评估如何操作数据是最高效的。

在使用数组的时候，大部分方法的时间复杂度是O(n),O(n)的意思是我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的n代表数组的长度

如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有的元素按照我们的需要排列，那不是更好吗？

所以我们可以使用JS对象来存储所有的栈元素，保证他们的顺序并且遵循先进后出的原则

class Stack {
	constructor() {
		this.items = {};
		this.count = 0; //用来记录对象中栈的长度,帮助我们实现添加和删除元素
	}

	// 往对象中添加元素
	push(element) {
		this.items[this.count] = element;
		this.count++;
	}

	// 往对象中删除元素
	pop() {
		this.count--;
		const result = this.items[this.count];
		delete this.items[this.count];
		return result;
	}

	// 返回栈顶的元素
	peek() {
		return this.items[this.count - 1];
	}

	// 判断栈里面还有没有元素
	isEmpty() {
		return this.count === 0;
	}

	// 移除栈里的所有元素
	clear() {
		this.items = {};
		this.count = 0;
	}

	// 返回栈里的元素个数
	size() {
		return this.count;
	}

	// 在数组版本,不需要关心toString方法的实现,因为数据结构可以直接使用数组提供的toString方法
	// 对于对象,我们需要自己封装一个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;
	}
}