前言
栈是一种后进先出的数据结构，Last In First Out(LIFO)，看似很简单但其实是应用非常广泛的数据结构。就像你先往饼干罐里装饼干，要吃的时候往外拿。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
栈 Stack
栈也是一种线性结构，相比数组来说相应的操作更少，栈对应的操作是数组的子集，因为它的本质就是一个数组，并且它有比数组更多的限制。
栈的本质就是一个数组，它将数据排开来放的，添加元素的时候只能从栈的一端添加元素，取出元素的时候也只能栈的一端取出元素，这一端叫做栈顶，当这样的限定了数组，从而形成了栈这种数据结构之后，它可以在计算机世界中对于组建逻辑产生非常非常重要的作用。
栈的操作，从栈顶添加元素，把元素一个一个的放入到栈中，如添加值的时候为 1、2、3，你取值的时候顺序则为 3、2、1，因为你添加元素是只能从一端放入，取出元素时也只能从一端取出，而这一段就是栈顶，栈的出口和入口都是同一个位置，所以你只能按照先进后出、后进先出的顺序添加数据或者取出数据，不存在插入和索引。
栈的简单应用
栈虽然是一个非常简单的数据结构，但是它能够解决计算机领域非常复杂的一个问题，这个问题就是这种子过程子逻辑的调用，在编译器内部它运行实现的原理是什么，深入理解这个过程，甚至能够帮助你理解一些更复杂的逻辑过程，比如递归这样的一个过程，你会有更加深刻的理解。
无处不在的 Undo 操作（撤销）
编辑器的撤销操作的原理就是靠一个栈来进行维护的，如 将 每次输入的内容依次放入栈中 我 喜欢 你，如果 你 字写错，你撤销一下，变成 我 喜欢，再撤销一下 变成 我。
程序调用的系统栈
程序调用时经常会出现在一个逻辑中间先终止然后跳到另外一个逻辑去执行，所谓的子函数的调用就是这个过程，在这个过程中计算机就需要使用一个称为系统栈的一个数据结构来记录程序的调用过程。
例如有三个函数 A、B、C，当 A 执行到一半的时候调用 B，当 B 执行到一半的时候调用 C，C 函数可以执行，C 函数运行完了之后继续运行未完成的 B 函数，B 函数运行完了就运行未完成 A 函数，A 函数运行完了就结束了。
function A () {
1 ...;
2 B();
3 ...;
}
function B () {
1 ...;
2 C();
3 ...;
}
function C () {
1 ...;
2 ...;
3 ...;
}系统栈记录的过程：
A 函数执行，在第二行中断了，因为要去执行函数 B 了，这时候函数信息A2会被放入系统栈中，系统栈中显示：[A2]，然后 B 函数执行，在第二行也中断了，因为要去执行函数 C 了，这时候函数信息 B2 会被放入系统栈中，系统栈中显示：[A2, B2]，然后 C 函数执行，C 函数没有子函数可执行，那么执行到底，函数 C 执行完毕，从系统栈中取出函数 B 的信息，系统栈中显示：[A2]，根据从系统栈中取出的函数 B 的信息，从函数 B 原来中断的位置继续开始执行，B 函数执行完毕了，这时候会再从系统栈中取出函数 A 的，系统栈中显示：[]，根据从系统栈中取出的函数 A 的信息，从函数 A 原来中断的位置继续开始执行， A 函数执行完了，系统栈中已经没有函数信息了，好的，程序结束。 存入系统栈中的是函数执行时的一些信息， 所以取出来后，可以根据这些信息来继续完成。
系统栈最神奇的地方
在编程的时候进行子过程调用的时候，当一个子过程执行完成之后，可以自动的回到上层调用中断的位置，并且继续执行下去。都是靠一个系统栈来记录每一次调用过程中中断的那个调用的点来实现的。
栈的实现
栈这种数据结构非常有用，但其实是非常简单的。
从用户的角度看，只要支持这些操作就好了，用户不管你要怎样 resize，他只要知道你这个数组是一个动态的，他可以不停的往里面添加元素，并且不会出现问题就 ok，其实对于栈也是这样的，对于具体的底层实现，用户不关心，实际底层也有多种实现方式，所以用户就更加不关心了。
MyStack
void push(e)：入栈 E pop()：出栈 E peek()：查看位于栈顶位置的元素 int getSize()：获取栈中实际元素的个数 boolean isEmpty()：栈是否为空
为了让代码更加的清晰，同时也是为了支持面向对象的一些特性，比如说支持多态性，那么就会这样的去设计，定义一个接口叫做 IMyStack，接口中有栈默认的所有方法，然后再定义一个类叫做 MyStack，让它去实现 IMyStack，这样就可以在 MyStack 中完成对应的逻辑，这个 MyStack 就是自定义的栈。会复用上一篇文章中封装的自定义数组。
代码实现
(class: MyArray, class: MyStack, class: Main)
MyArray
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyStack
class MyStack {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入栈
push(element) {
this.myArray.push(element);
}
// 出栈
pop() {
return this.myArray.pop();
}
// 查看栈顶的元素
peek() {
return this.myArray.getLast();
}
// 栈中实际元素的个数
getSize() {
return this.myArray.getSize();
}
// 栈是否为空
isEmpty() {
return this.myArray.isEmpty();
}
// 查看栈的容量
getCapacity() {
return this.myArray.getCapacity();
}
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Stack: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] stack top is right!`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyStack Area');
let ms = new MyStack(10);
for (let i = 1; i <= 10; i++) {
ms.push(i);
console.log(ms.toString());
}
console.log(ms.peek());
this.show(ms.peek());
while (!ms.isEmpty()) {
console.log(ms.toString());
ms.pop();
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 执行主函数
new Main();
};栈的时间复杂度分析
MyStack
void push(e)：O(1) 均摊 E pop()：O(1) 均摊 E peek()：O(1) int getSize()：O(1) boolean isEmpty()：O(1)
总结
栈的应用：undo 操作-编辑器、系统调用栈-操作系统、括号匹配-编译器。
括号匹配-编译器：无论是写表达式，这个表达式中有小括号、中括号、大括号，，自然会出现括号套括号的情况发生，，在这种情况下就一定会产生一个括号匹配的问题，，如果括号匹配是不成功的，那么编译器会进行报错。
编译器是如何检查括号匹配的问题？
原理是使用了一个栈，可以通过解答 Leetcode 中的一个问题，同时来看栈在括号匹配这个问题中的应用。
leectocde
英文网址：leetcode.com
2017 中文网址：leetcode-cn.com
Leetcode 是总部在美国硅谷一家非常有年头又同时有信誉度的面向 IT 公司面试这样一个在线的平台，只需要注册一个 Leetcode 用户后，就可以看到 Leetcode 上有非常多的问题，对于每一个问题会规定输入和输出之后，然后就可以编写属于自己的逻辑，更重要的是可以直接把你编写的这个程序提交给这个网站，这个网站会自动的判断你的逻辑书写的是否正确。
leetcode.com与leetcode-cn.com的区别
leetcode-cn.com支持中文，leetcode-cn.com的题目数量没有英文版的多。leetcode-cn.com的探索栏目的内容没有英文版的多。leetcode-cn.com中的题目没有社区讨论功能，但英文版的有。
leetcode 中第二十号题目：有效的括号
如：{ [ ( ) ] }，从左往右，先将左侧的括号入栈，然后遇到右侧的括号时就查看栈顶的左侧括号进行匹配，如果可以匹配表示括号有效，否则括号无效，括号有效那么就将栈顶的左侧括号取出，然后继续从左往右，左侧括号就入栈，右侧括号就匹配，匹配成功就让左侧括号出栈，匹配失败就是无效括号。其实栈顶元素反映了在嵌套的层级关系中，最新的需要匹配的元素。
这个算法非常的简单，但是也非常的实用。很多工具中都有这样的逻辑来检查括号的匹配。
Solution
class Solution {
isValid(s) {
// leetcode 20. 有效的括号
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = [];
// 以遍历的方式进行匹配操作
for (let i = 0; i < s.length; i++) {
// 是否是正括号
switch (s[i]) {
case '{':
case '[':
case '(':
stack.push(s[i]);
break;
default:
break;
}
// 是否是反括号
switch (s[i]) {
case '}':
if (stack.length === 0 || stack.pop() !== '{') {
console.log('valid error. not parentheses. in');
return false;
}
break;
case ']':
if (stack.length === 0 || stack.pop() !== '[') {
console.log('valid error. not parentheses. in');
return false;
}
break;
case ')':
if (stack.length === 0 || stack.pop() !== '(') {
console.log('valid error. not parentheses. in');
return false;
}
break;
default:
break;
}
}
// 是否全部匹配成功
if (stack.length === 0) {
return true;
} else {
console.log('valid error. not parentheses. out');
return false;
}
};
return isValid(s);
}
}Main
class Main {
constructor() {
// this.alterLine("MyStack Area");
// let ms = new MyStack(10);
// for (let i = 1; i <= 10 ; i++) {
// ms.push(i);
// console.log(ms.toString());
// }
// console.log(ms.peek());
// this.show(ms.peek());
// while (!ms.isEmpty()) {
// console.log(ms.toString());
// ms.pop();
// }
this.alterLine('leetcode 20. 有效的括号');
let s = new Solution();
this.show(s.isValid('{ [ ( ) ] }'));
this.show(s.isValid(' [ ( ] ) '));
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 执行主函数
new Main();
};