基础数据结构

[lewenweijia]

基础队列
具有额外特性的队列: 循环队列, 阻塞队列, 并发队列
  -> (应用于偏底层系统, 框架, 中间件的开发中, 关键性作用)

队列可以用于任何的有限资源池中(例如: 线程池)

零生一, 一生万物的感觉的啊
内存 -> 数组/链表 -> 万物

[lewenweijia]

栈? 顺序表, 单端点操作
队列? 顺序表, 双端点操作

特定的数据结构是针对特定场景的抽象, 数组/链表暴露过多的操作接口了, 一些
场景需要被受限! 使用时容易失控

基于数组的顺序栈, 基于链表的链式栈
顺序队列, 链式队列

空间复杂度? -> 说的是算法运行时候所需要的额外空间
链式栈? -> 大小不受限的好处, 但是需要存储next指针, 内存消耗明显

顺序表实现

function ArrayStack(n) {
  this.items = Array(n).fill(nul);
  this.count = 0;
  this.size = 0;
}

ArrayStack.prototype.push(item) {
  if (count === this.size) return false;
  items[count++] = item;
  return true;
}

ArrayStack.prototype.pop() {
  if (count === 0) return null;
  return items[count--];
}

[lewenweijia]

栈

栈? -> 保存函数调用时候的临时变量的啦

栈的应用?
表达式求值(双栈)
括号匹配(最后是否为空)
浏览器的前进后退功能(双栈)