故事背景

人物：

​ 大牛、小白

场景：

​ 高铁中 ‘牛与白’ 的深入交流

前言：

栈和队列是计算机科学中使用的比较广泛的两种数据结构，如：程序的递归是使用栈来实现的，操作系统中进程调度网络管理中的打印服务等都是通过队列来实现的。

“啤酒饮料矿泉水，花生瓜子火腿肠。来，腿收一下了啊~”

“列车模型，有需要的乘客吗？列车模型，有需要的乘客吗？”

“这无聊的旅途，相信大家都辛苦了，接下来我给大家带来一个有意思的产品…”

“牛哥，要不然咱们改行来高铁上卖东西吧，看看看看，前边那个小伙子又花钱了。这钱也太好赚了。”

“好啊，你来高铁上开店，我给你赞助。多了没有，三五十还是能投资得起的。”

“在公司就知道你牛哥抠门，没想到出来一趟还是这么抠。哎，我是上了贼船下不去咯。”

“还敢说我抠门，刚才的水白让你喝了是吧？”

“哈哈哈哈哈哈……”小白笑的前仰后翻。“牛哥，你不说还好，你这一说，都能把我笑死，你见谁出个差，灌两瓶自来水带着喝。”

大牛老脸一红，说道：“不说这个不说这个，上次我让你好好学学数据结构和算法，有什么成果没有？”

”您这么一说啊，我这儿正好有个问题需要请教您一下“。听到大牛问他成果，小白也收起了玩笑的表情。认真的说道。

”你小子今天怎么这么谦虚呢，有古怪哈。那你先说说，有什么问题能难住你。“

”我现在不是学到队列了嘛。有点儿不明白栈和队列有什么不一样，他们两个都是线性存储方式，也都有增删功能。我看没什么不一样的。“

”你这专业成绩不是挺好的吗，怎么连这个都不知道？”

”每个人都有自己的长处和短处吗，这个方面我就特别的薄弱，还请牛哥不吝赐教。“

“看你这么诚恳的份儿上。就让老夫好好和你说说。“

先来说一下他们两个的定义：

栈和队列都是受限的线性表。

什么叫受限呢？

意思是说他们的增删功能是受到系统限制的。只能在固定的地方删除或者添加元素，不能任意增删其他位置的元素。

1. 栈

1. 又叫堆栈
2. 受限操作：限定只能在表尾进行增加和删除操作。可进行操作的一端成为 栈顶 。不可操作的一端成为 栈底 。
3. 增加元素的操作又称为进栈、入栈或者压栈。意思是把元素添加到栈顶的位置。
4. 删除元素的操作又称为出栈或者退栈。意思是把元素从栈顶移除。使其相邻元素成为栈顶元素。

2. 队列

1. 受限操作：限定只能在表的前端进行删除操作，只能在表的后端进行插入操作。
2. 进行插入操作的一端称为队尾，进行删除操作的一端称为队头。
3. 增加元素的操作称为入队列 ，意思是把元素添加到队尾的位置。
4. 删除元素的操作称为出队列 ，意思是把元素从队头位置移除。

“这个我知道的牛哥，我问的是有什么不一样。”

”就你懂得多是吧，我这不是还没说到呢吗，你着急什么。“大牛白了一眼小白，然后继续说到。

”栈和队列最大的不同点是元素增删的顺序。栈为 先入后出 ，队列为 先入先出 。

举个栗子来说：

栈：

1. 把一个水杯比作一个栈结构；

2. 将水倒入水杯的过程就是水入栈的过程；

3. 喝水的时候就是水出栈的过程。

   结论：最先被我们倒入杯中的水肯定会最后被我们喝到。 — 先入后出

// 创建一个栈，并实现基本方法
// 首先定义一个栈的类
class Stack{
  constructor() {
    this.data = [];
  }
  // 入栈方法
  push(element){
    this.data.push(element);
    return this.data.length;
  }
  // 出栈方法
  pop() {
    if(this.data.length){
      this.data.pop()
      return this.data.length;
    }
    return false;
  }
  // 查询栈顶方法
  searchStackTop() {
    return this.data[this.data.length - 1];
  }
  // 查询栈是否为空
  isEmpty() {
    return this.data.length === 0
  }
  // 清空栈的方法
  clear() {
    this.data = [];
  }
}

队列：

1. 把银行叫号流程看做一个队列；

2. 用户拿号 — 入队列；

3. 客服人员叫号 — 出队列。

   结论：最先拿到号的客户肯定被首先叫到号 — 先入先出

// 创建一个队列，实现基本操作方法
// 定义一个队列类
class Queue{
  constructor() {
    this.data = [];
  }
  // 入队列方法
  push(element) {
    this.data.push(element);
    return this.data.length;
  }
  // 出队列方法 从队头取出元素
  pop() {
    if(this.data.length){
      this.data.shift();
      return this.data.length;
    }
  }
  // 查询队头元素
  searchQueueHead() {
    return this.data[0];
  }
  // 清空队列方法
  clear() {
    this.data = [];
  }
  // 查询队列是否为空
  isEmpty() {
    return this.data.length === 0;
  }
}

“这里我只是用数组方式分别实现了栈和队列，当然也可以使用其他方式，如：对象。链表等。剩下的方式你可以自己试一下，我就不多写了。“

”好好好，等咱们到了地方我就自己着手实现一次。加深加深印象。不不不，我现在就实现一次。“说这小白从包里拿出来笔记本，‘啪啪啪……’ 的就开始敲代码。

大牛看着小白兴奋的样子也想起来自己年轻的时候，对待技术也是这样狂热。也想起了自己刚接触到算法的时候，每天张口闭口都是算法，都是复杂度。现在回想一下，感觉内心也泛起了一丝涟漪，久久不能平静。

”牛哥牛哥，我这儿实现完了。但是还有一个问题需要问你。“

”哦？还有什么问题“ 大牛被小白打断思路，但是并没有生气。

”经常听他们说栈溢出，栈溢出到底是什么情况？前端怎么才能导致栈溢出？“

3. 栈溢出

栈溢出一般指的是，我们定义的数据所需要占用的内存超过了栈的大小时，就会发生栈溢出。

如：

// 前端常见 -- 执行栈溢出。
function sum(a){
  sum(a);
  console.log(1);
}

解析：

执行过程：函数调用会在内存形成一个"调用记录"，又称"调用帧"，保存调用位置和内部变量等信息。

1. 执行 sum 函数；
2. ……无限循环调用 sum 函数；
3. 直到调用记录超过执行栈的最大存储范围，然后系统抛出错误，终止程序 。

4. 栈溢出解决方法 — 尾递归优化

4.1 尾调用

定义：函数在最后一步调用其他函数，称为尾调用。

// 情况一
function s() {
	let x = y();
  console.log(x);
}
// 情况二
function s(result) {
  if(result){
    return y();
 }
 return y();
}

解析：

1. 情况一 不属于尾调用，因为在调用函数后还有其他操作；
2. 情况二 属于尾调用。

结论：尾调用不一定出现在函数最后，只需要最后一步执行的是函数即可 。

4.2 尾递归

定义：函数在最后一步调用自身，成为尾递归

function s() {
return s();
}

解析：

1. 执行过程：在执行 第二行代码的时候会先将第一行的函数释放掉；

2. 结论：对于尾递归来说，只会存在一个调用记录，所以栈不会溢出。

”原来是这么回事儿，那有栈溢出是不是就会有队列溢出？“

”好小子，这么快就学会举一反三了。“

”主要是牛哥教的好~“

”好好好，这个马屁拍的我很是受用啊。那我们再来说说队列溢出吧。

5. 队列溢出

队列溢出分为真溢出和假溢出两种。

5.1 真溢出：

1. 定义： 指的是由于存储空间不够而产生的溢出叫真溢出；
2. 解决方式： 扩容的方式解决。

5.2 假溢出：

1. 定义： 队列中尚余有足够的空间，但元素却不能入队。一般是由于队列的存储结构或操作方式的选择不当所致。

2. 产生原因：

   

此时是队列达到上限的情况，此时删除一个元素，会成为：

此时查询队列会显示队列已满的情况，但明显队列中还有空余位置。

3. 解决方式:

   1. 删除元素后将所有元素向前移动一位。
   

​ 此时再次查询队列，不会出现队列已满的情况。

2. 还有一种循环队列的解决方式，给你留个任务，把这个方式实现一下。

”啊，还有任务啊？“

”要不然呢？听一遍就过去了？“

”没想到栈和队列看上去这么简单，还有这么复杂的东西。经过牛哥的指点，我感觉我已经对栈和队列了如指掌了。“

”好啊，那你给我说说怎么用两个栈实现一个队列。“

”这个嘛……。嘿嘿，牛哥。”

做人呐，还是得谦虚。我给你说一下实现吧。

我们可以这么做：

1. 创建两个栈 stack1 和 stack2；
2. 向 stack1 里添加元素；（模拟入队列操作）
3. 将 stack1 的元素反向遍历出栈，并入栈 stack2；（此时得到的 stack2 是与 stack1 顺序相反的元素）
4. 出队列操作从 stack2 出栈就可以完成。（因为 stack2 等于 stack1 的逆序。stack2 出栈相当于从 stack1 的栈底出栈）

let stack1 = [];
let stack2 = [];
function push(node){
    stack1.push(node);
}
// pop方法，模拟出队列操作
function pop(){
  	// 若stack2不为空，表示stack2中还有元素，直接做出栈操作
    if(stack2.length){
        return stack2.pop();
    }else{
      	/* 
      		stack2为空，查看stack1 若stack1不为空，则将stack1逆序入栈到stack2
      		如:  stack1 -- 1,2,3,4,5
      				 stack2 -- 5,4,3,2,1
      	*/
        if(stack1.length){
            var len = stack1.length;
            for(var i=0;i<len;i++){
                stack2.push(stack1.pop());
            }
          	//逆序完成后 出栈栈顶元素
            return stack2.pop()
        }else{
             return null
        }
         
    }
}

”我的天哪。这么神奇吗。“

”好了，把刚才我给你说的实现一遍吧，熟练了之后休息一会儿，我们到广西之后还有很多工作要做呢。“

”好的牛哥，你先休息会儿吧，我再看看。“

高铁以极快的速度继续行进着。小白眼望着窗外，思绪久久不能平静。大牛的博学让他仰慕。他也想成为大牛那样的人，却不知道还要多久……

小结：

本节讲述了：

1.栈和队列的基本概念；
2.栈溢出的出现和解决方法 – 尾递归；
3.队列的真溢出和假溢出。

努力学习的你，加油！！！

番外篇

面试题攻坚战 — 叁：

去除最外层的括号

例如：

// 原有字符串为
let originStr = "(()(())(()()))((()))";
// 删除最外层的之后成为如下字符串
let resultStr = "()(())(()())(())"

题目解答：

function countStr(S) {
  	/*
  		使用size模拟栈操作
  		当size为 0 的时候表示这个括号为外层括号
  		入栈 size ++
  		出栈 size --
  	*/  
    let size = 0; 
    let result = '';
    for(let i = 0;i < S.length;i ++){
      // 如果为左括号 入栈 size ++ 
      if(S[i] === '('){
        // 外层括号不加入到输出结果中
        if(size !== 0){
          result += S[i];
        }
        size ++;
        // 如果为右括号 出栈 size -- 
      }else{
        size --;
        // 外层括号不加入到输出结果中
        if(size !== 0){
          result += S[i];
        }
      }
    }
    return result;
}

// 原有字符串为
let originStr = "(()(())(()()))((()))";
countStr(originStr);
// 输出 ()(())(()())(()) 成功将最外层括号删除掉

解析：

1. 我们使用 size 模拟一个栈操作方式，入栈 size ++ 。 出栈 size --；
2. 如果 size 的值为 0 ，表示当前的括号为最外层括号，最外层括号不进入结果中；
3. 遍历结束后，result 字符串为我们想要得到的结果。

TIPS：方法不唯一，可自行实验其他可行方式。