栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器的返回按钮）
创建一个基于数组的栈
// 我们将创建一个类来表示栈
// 我们需要一种数据结构来保存栈里的元素。可以选择数组。数组允许我们在任何
// 位置添加或删除元素。由于栈遵循 LIFO 原则，需要对元素的插入和删除功能进行限制。接下来，
// 要为栈声明一些方法。
//push(el(s))：添加一个（或几个）新元素到栈顶。
//pop()：移除栈顶的元素，同时返回被移除的元素。
//peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）
//isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
//clear()：移除栈里的所有元素。
//size()：返回栈里的元素个数。该方法和数组的 length 属性很类似。
class Stack{
constructor(){
this.items=[]
}
push(el){
this.items.push(el)
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}
//使用 Stack 类
const stack = new Stack()
console.log(stack.isEmpty())//true
stack.push(5)
stack.push(8)
console.log(stack.peek()); // 8 因为它是往栈里添加的最后一个元素。
stack.push(11);
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(15)
stack.pop()
stack.pop()
console.log(stack.size())//2
创建一个 Stack 类最简单的方式是使用一个数组来存储其元素。类似上方的代码，无需太多的代码，就可以做到一些小需求。比如获取用户在网页中的跳转记录，或者是用户一天的上线情况，亦或是直播中用户的进入进出，其他用户的进入进出等等。然而在处理大量数据的时候（这在现实生活中的项目里很常见），我们同样需要评估如何操作数据是最高效的。
数组大家都知道，是有序的集合，为了保证元素排列有序，它会占用更多的内存空间。在使用数组时，大部分方法的时间复杂度是 O(n)。O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位
置，其中的 n 代表数组的长度。如果数组有更多元素的话，所需的时间会更长。
因此在实际开发中总是使用对象来封装stack类
class Stack{
constructor(){
this.count = 0;
this.items={}
}
push(el){
this.items[this.count] = el;
this.count++
}
pop() {
if (this.isEmpty()) {//如果此时为空返回
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count]; //删除
return result;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1]; //push之后count已经++ 存储的key是count-1
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
clear() {
this.items = {};
this.count = 0;
//我们也可以遵循 LIFO 原则，使用下面的逻辑来移除栈中所有的元素。
// while (!this.isEmpty()) {
// this.pop();
// }
}
// 在数组版本中，我们不需要关心 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;
}
}
//使用 Stack 类
const stack = new Stack()
console.log(stack.isEmpty())//true
stack.push(5)
stack.push(8)
console.log(stack.peek()); // 8 因为它是往栈里添加的最后一个元素。
stack.push(11);
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(15)
stack.pop()
stack.pop()
console.log(stack.size())//2
console.log(stack.toString())//5,8
此时有个问题，就是Stack 类中声明的 items 和 count是完全暴露的，并没有得到保护
const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack)) //["count", "items"]
console.log(Object.keys(stack));//["count", "items"]
console.log(stack.items)//{}
不过这里就不编写如何去处理了，即使处理了也有不好的地方。可能在不久的将来可以通过在属性前添加井号（#）作为前缀来声明私有属性
class Stack {
#count = 0;
#items = 0;
// 栈的方法
}
如何用栈解决进制转换的问题
function decimalToBinary(decNumber){
const remStack = new Stack();
let number = decNumber;
let rem;
let binaryString = '';
while (number > 0){ //当除法的结果不为 0 时
rem = Math.floor(number % 2); //获得一个余数，并放到栈里
remStack.push(rem);
number = Math.floor(number / 2);//然后让结果继续除以 2 JavaScript 有数值类型，但是它不会区分整数和浮点数。因此，要使用 Math.floor 函数仅返回除法运算结果的整数部分。
}
while (!remStack.isEmpty()){ //用 pop 方法把栈中的元素都移除，把出栈的元素连接成字符串
binaryString += remStack.pop().toString();
}
return binaryString;
}
console.log(decimalToBinary(233)) //11101001
console.log(decimalToBinary(10)) //1010
console.log(decimalToBinary(1000))//1111101000
如果看不懂就把数字传进去，凑一下就懂了。比如你传4，都知道4的二进制是100吧，先传4，4%2余0,0进入栈中，然后number=2重新走，2%2余0,0进入栈中，此时number=1，再走一遍，1%2=0 余 1,1进入栈中，此时number=0了，结束循环，然后pop后进先出，输出1-0-0==>100
我们可以修改之前的算法，使之能把十进制转换成基数为 2～36 的任意进制
function baseConverter(decNumber,base){
const remStack = new Stack();
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
let number = decNumber;
let rem;
let baseString = '';
if (!(base >= 2 && base <= 36)){
return ''
}
while (number > 0){
rem = Math.floor(number % base);//几进制就除几
remStack.push(rem);
number = Math.floor(number / base);
}
while (!remStack.isEmpty()){
baseString += digits[remStack.pop()];
}
return baseString;
}
console.log(baseConverter(100345, 2)); // 11000011111111001
console.log(baseConverter(100345, 8)); // 303771
console.log(baseConverter(100345, 16)); // 187F9
console.log(baseConverter(100345, 35)); // 2BW0