## 数据结构 - 栈的骚气操作

### 简单介绍一下

<ul>
  <li>栈是在表尾进行插入或删除操作的线性表</li>
  <li>对栈来说，表尾称为栈顶，表头称为栈底</li>
  <li>LIFO，先进后出</li>
</ul>

### 基本形态

```javascript
    1 . 栈空
        - 条件: Stack.length == NULL
        - 操作: 不允许出栈

    2 . 栈满
        - 条件: Stack.length == MaxLength
        - 操作: 不允许入栈

    3 . 不空也不满
        - 条件: 0 < Stack.length < MaxLength
        - 操作: 可以入栈，也可以出栈
```

### 实现一下

这里封装了基本方法

|        方法        |        描述         |
| :----------------: | :-----------------: |
| pushStack(element) | 将元素 element 入栈 |
|    popStatck()     |        出栈         |
|      isEmpty       |   判断栈是否为空    |
|     getCount()     |    获取栈的长度     |
|    getHeader()     |    获取栈底元素     |
|     getTail()      |    获取栈顶元素     |

```javascript
  可以把栈看成是数组的一个子集，所以这里使用数组来实现

  function Stack () {
    var stack = []

    this.pushStack = function (element) {
      stack.push(element)
    }

    this.popStatck = function () {
      let popelement = stack.pop()
      console.log('出栈元素为: ', popelement)
    }

    this.isEmpty = function () {
      if (stack.length === 0) {
        return true
      } else {
        return false
      }
    }

    this.getCount = function () {
      return stack.length
    }

    this.getHeader = function () {
      if (stack.length === 0) {
        return null
      } else {
        return statck[0]
      }
    }

    this.getTail = function () {
      return stack[this.getCount() - 1]
    }

    this.show = function () {
      console.log('栈底至栈顶为: ', stack.join(' '))
      console.log('依次出栈顺序为: ', stack.reverse().join(' '))
    }

  }

  var stack = new Stack()
  stack.pushStack('a')
  stack.pushStack('b')
  stack.pushStack('c')
  stack.pushStack('d')
  stack.pushStack('e')
  stack.pushStack('f')
  stack.popStatck()
  // console.log(stack.getHeader())
  // console.log(stack.getTail())
  // console.log(stack.getCount())
  stack.show()

```

### 面试常考

<!--more-->

#### 括号的匹配

```javascript
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

```

```javascript
// 可以利用栈的形式来实现

// 当匹配到 左 ( { [ 的时候，入栈。匹配到 右 ) } ] 的时候出栈，判断是否是同一组括号

function isVilidate(str) {
  let map = {
    '[': -1,
    ']': 1,
    '{': -2,
    '}': 2,
    '(': -3,
    ')': 3
  };

  let stack = [];
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]] < 0) {
      stack.push(map[str[i]]);
    } else {
      let popNum = stack.pop();
      if (popNum + map[str[i]] !== 0) {
        console.log('不是一组有效的括号');
        return false;
      }
    }
  }

  if (stack.length > 0) {
    // 排除 {}[]( 的情况，这时 stack 数组中还存在 (
    return false;
  }

  return true;
}

console.log(isVilidate('{}{}([])'));
```

#### 行编辑程序

```javascript
编写一函数 editString() ，输入一行文本字符，当发现一个退格符 "#" 时，表示前一个字符无效； 当发现一个 "@" 时，表示当前行中的字符均无效

输入: "whli##ilr#e(s#*s)"
输出: while(*s)

输入: "ticknet@hunst(*s=#++)"
输出: hnust(*s++)

```

```javascript
// 可以用栈实现

// 对每个字符做判断，如果既不是#也不是@，则压入栈

// 如果遇到#，则从栈中pop出来前一个字符，如果是一个@，则清空这个栈

function editString(str) {
  let stack = [];

  for (let i = 0; i < str.length; i++) {
    switch (str[i]) {
      case '#':
        if (stack.length !== 0) {
          // 排除 第一个字符就是 #，因为这时候栈为空，无法pop
          let popElement = stack.pop();
          console.log('遇到#，pop前一个元素: ', popElement);
        }
        break;
      case '@':
        stack = [];
        break;
      default:
        stack.push(str[i]);
    }
  }

  return stack.join('');
}

console.log(editString('whli##ilr#e(s#*s)'));
```

## 用两个栈模拟队列

```javascript
题目描述：用两个栈模拟队列的push(入队)和pull(出队)操作，比如现在有个Q队列和栈A，栈B，栈只有两个方法，push()和pop(), 队列也只有两个方法，push()和pull()，队列的进和出都只能通过A和B的push和pop实现。

```

```javascript

// 只考虑每次只能push一次，比如第一次push(a), 第二次push(b)，然后再push(c)，接着pull()就给我弹出a，再pull一次就给我弹出b

队列 “ 先进先出 ” ， 栈 “ 先进后出 ”

  var Stack = function () {
    this.stack = []

    // 入栈
    this.push = function (element) {
      this.stack.push(element)
    }

    // 出栈
    this.pop = function () {
      return this.stack.pop()
    }

    // 判断是否为空
    this.isEmpty = function () {
      return this.stack.length === 0
    }
  }


  var Queue = function () {

    var stackA = new Stack ()
    var stackB = new Stack ()

    // 入队
    this.push = function (element) {
      stackA.push(element) // 入栈 a
    }

    // 出队
    this.pull = function () {
      if (stackA.isEmpty() && stackB.isEmpty()) {
        console.log('两个栈都是空')
      }
      // B 栈为空，则 A 栈的都入B栈
      if (stackB.isEmpty()) {
        while (!stackA.isEmpty()) {
          stackB.push(stackA.pop())
        }
      }
      return stackB.pop()
    }

  }


  var q = new Queue()
  q.push(1)
  q.push(2)
  console.log(q.pull()) // 根据队列先进先出：1
  console.log(q.pull()) // 根据队列先进先出：2

```

### 不使用辅助栈，实现将栈逆序(有点问题，还在想...)

```javascript
  一个栈，压入 1, 2, 3，这时候栈底到栈顶为: 1, 2, 3

  实现逆序，这时候栈底到栈顶为 3, 2, 1

```

```javascript
var Stack = function() {
  this.stack = [];

  // 入栈
  this.push = function(element) {
    this.stack.push(element);
  };

  // 出栈
  this.pop = function() {
    return this.stack.pop();
  };

  // 判断是否为空
  this.isEmpty = function() {
    return this.stack.length === 0;
  };

  // 返回并删除栈底元素
  this.removeElement = function() {
    var res = this.pop();
    if (this.isEmpty()) {
      return res;
    } else {
      var last = this.removeElement();
      this.push(res);
      return last;
    }
  };

  // 逆序
  this.reverse = function() {
    if (this.isEmpty()) {
      return this.stack;
    }

    var last = this.removeElement();

    this.reverse();
    this.push(last);
  };

  // 显示栈
  this.show = function() {
    var result = '';
    for (let i = 0; i < this.stack.length; i++) {
      result += this.stack[i] + ' ';
    }
    console.log('栈底到栈顶: ', result);
  };
};

var stackA = new Stack();
stackA.push(1);
stackA.push(2);
stackA.push(3);
stackA.show();

stackA.reverse();
stackA.show();
```

### 将数字转换为二进制和八进制

```javascript
// (1)最高位为 num % base，将此位压入栈。
// (2) 使用 num/base 代替 num。
// (3) 重复步骤 1 和 2，直到 num 等于 0，且没有余数。
// (4) 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式。

var Stack = function() {
  this.data = [];

  this.push = function(val) {
    this.data.push(val);
  };

  this.pop = function() {
    return this.data.pop();
  };
};

function mulBase(num, base) {
  var stack = new Stack();

  do {
    stack.push(num % base);
    num = Math.floor((num /= base));
  } while (num > 0);

  var convert = '';
  while (stack.data.length > 0) {
    convert += stack.pop();
  }
  return convert;
}

var num = 32;
var base = 2;
var example1 = mulBase(num, base);
console.log(example1); // 100000

var num = 125;
var base = 8;
var example2 = mulBase(num, base);
console.log(example2); // 175
```

### 用栈来模拟递归

```javascript
计算一个数的阶乘;

// 递归
function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
console.log(factorial(5)); // 120

// 用栈模拟, 将数字从 5 到 1 压入栈，然后使用一个循环，将数字挨个弹出连乘
var Stack = function() {
  this.data = [];

  this.push = function(val) {
    this.data.push(val);
  };

  this.pop = function() {
    return this.data.pop();
  };
};

function factorial(n) {
  var s = new Stack();
  while (n > 1) {
    s.push(n--);
  }
  var num = 1;
  while (s.data.length > 0) {
    num *= s.pop();
  }
  return num;
}
console.log(factorial(5)); // 120
```

### 相关链接

Blog: http://blog.pengdaokuan.cn:4001

github: https://github.com/PDKSophia/blog.io