栈

链式数据结构很重要-实现背包-队列-栈

许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是：添加，删除，访问集合中的对象。

链式数据结构很重要，借助数据结构链表，能高效实现背包，队列，栈。理解链表是学习各种算法和数据结构中最关键的第一步。三种数据类型：

• 队列
• 栈
• 背包: 一种不支持从中删除元素的集合数据类型。用来帮助用例收集元素并迭代 所有收集到的元素。

栈和队列的区别

栈和队列都是线性表。区别在于:

• 栈的插入和删除操作只允许在表的尾端进行，
• 队列只允许在表尾插入数据元素，在表头删除数据元素。

其他不同点：

• 1.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。
• 2.顺序栈能够实现多栈空间共享，而顺序队列不能。

其他相同点：

1. 都是线性结构。
2. 都可以通过顺序结构和链式结构实现。
3. 插入与删除的时间复杂度都是O(1)，空间复杂度相同。
4. 多链栈和多链队列的管理模式可以相同。

1.应用:10进制--->2进制

把十进制转化成二进制，我们可以将该十进制数除以2（二进制是满二进一）并对商取整，直到结果是0为止。

2.应用2:点击超链接，浏览器会把它压入栈。回退访问前页面，就是从栈弹出。

队列:先进先出,foreach栈

const arr = [1,2,3,4]
arr.forEach(item =>{
  console.log('item',item)
})
/*
item 1
item 2
item 3
item 4
*/

基于数组的栈

/*
栈是一种线性数据结构，可以想象成一列盘子，只能在顶部放置或者取出盘子。
栈的基本操作包括:
push一个元素到栈顶
pop栈顶的元素
peek 查看栈顶元素
*/
class StackArray {
  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;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  toArray() {
    return this.items;
  }

  toString() {
    return this.items.toString();
  }
}

const stack = new StackArray();
stack.push(5)
stack.push(8)
console.log(stack.peek()) // 8

基于对象的栈

/**
在处理大量数据的时候（这在现实生活中的项目里很常见），我们同样需要评估如何操作数据是最高效的。
在使用数组时，大部分方法的时间复杂度是O(n)。

另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
所以可以尝试使用一个JavaScript对象来存储所有的栈元素

基于对象的栈：
* 推入(push)操作的时间复杂度是O(1)；
* 弹出(pop)操作的时间复杂度是O(1)；
* 查看栈顶元素(peek)操作的时间复杂度是O(1)。

基于对象的栈的空间复杂度也是O(n)，其中n是栈的大小，因为需要为每个元素创建一个对象

基于数组的栈：
* 推入(push)操作的时间复杂度是O(1)或O(n)，取决于数组是否已经分配了足够的空间；
* 弹出(pop)操作的时间复杂度是O(1)；
* 查看栈顶元素(peek)操作的时间复杂度是O(1)。

基于数组的栈的空间复杂度也是O(n)，其中n是栈的大小，因为需要一个数组来存储元素。
*/
class Stack {
  constructor() {
    /*
    * 要向栈中添加元素，我们将使用count变量作为items对象的键名，插入的元素则是它的值。
    * 在向栈插入元素后，我们递增count变量。
    * */
    this.count = 0;
    this.items = {};
  }

  push(element) {
    this.items[this.count] = element;
    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];
  }

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

  size() {
    return this.count;
  }

  clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {};
    this.count = 0;
  }

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

const stack = new Stack();
stack.push(5);
stack.push({ key: 'test' });
console.log(stack.peek()) // {key: 'test'}
console.log(stack.toString())
/*
* 在内部，items包含的值和count属性如下所示。
{
    "0": 5,
    "1": {
        "key": "test"
    }
}
* */