JS实现数据结构系列（一）栈和队列

数组

普通数组

优点：通过下标取元素效率非常高。
缺点：常见语言数组不能存放不同类型的数据，所以一般都先封装一个Object类型

底层数组

扩容方法：新建一个大的数组，把原有数组写进去，再添加新元素。
特点：插入和删除性能（效率）都很低

栈

  1. 栈是一种受限的线性结构 后进先出（LIFO）
  2. 栈结构只能在栈顶进行插入和删除操作
  3. 向一个栈插入新元素又称作进栈、入栈和压栈
  4. 删除元素又称作出栈或退栈

程序中栈的应用：

  • 函数调用栈

函数调用栈

栈溢出：无限次数递归

栈的相关操作

  • push(element):添加一个新元素到栈顶位置
  • pop():移除栈顶的元素，同时返回被移除的元素
  • peek():返回栈顶的元素 不对栈做任何修改
  • isEmpty():如果栈里没有任何元素旧返回true 否则返回false
  • size():返回栈里的元素个数 这个方法和数组的length属性很类似
  • toString():将栈结构的内容以字符形式返回