栈数据结构

1. 什么是栈？
   1. 栈是一种遵从先出后进（LEFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
   2. 在生活中比如（一摞书），一叠盘子。
   3. 栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

创建栈

1. 我们将创建一个类来表示栈。

function Stack() {
	//各种属性和方法的声明
	let item = [];
	this.push = function (elemet) {
        items.push(elemet)
    }
    this.pop = function () {
        return items.pop();
    }
    this.peek = function () {
        return items[items.length - 1];
    }
    this.isEmpty = function(){
        return items.length == 0;
    }
    this.clear = function(){
        items = []
    }
    this.print=function(){
        console.log(items.toString());
    };
}
// 首先 我们需要一种数据结构 来保存栈里的元素，可以选择数组。

// 接下来为我们的栈声明方法。
push(elemet(s))  //添加一个 或者多个元素
pop(); //移除栈顶的元素，同时返回被移除的元素。
peek(); //返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）
isEmpty(); //如果栈里没有任何元素就返回 true 否则返回 false
clear(); //移除栈里的 所有元素
size(); //返回栈里的元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

向栈添加元素

// 现在来实现第一个方法 push()。这个方法 负责往栈里 添加新的元素，该方法只能 添加元素到栈顶，就是栈的末尾。push方法可以这样写
this.push = function (elemet) {
    items.push(elemet)
};
// 因为我们使用了数组来保存栈里的元素，所以可以用数组的 push() 方法来实现。
1
2
3
4
5

从栈移除元素

// 从栈移除元素
// 接着我们来实现pop方法。 这个方法用来移除栈里的元素。 栈遵从LIFO原则，因此移出的是最后添加进去的数组。因此我们可以用数组的pop方法。
this.pop = function(){
    return items.pop;
}
//只用push和pop方法添加和删除栈中元素，这样一来，我们的栈自然就遵从了LIFO原则。
1
2
3
4
5
6

查看栈顶的元素

// 查看栈顶元素
// 现在，为我们的类 实现一些额外的辅助方法，如果想知道栈里 最后添加的元素是什么 可以用peek 方法，这个方法返回栈顶的元素，
this.peek = function () {
    return items[items.length - 1];
}
// 因为类内部使用数组保存元素的
// 所以访问数组的最后一个元素 可以用length - 1;

1
2
3
4
5
6
7
8
9

迷宫问题控制台C++代码

cpp 3星 超过45%的资源 3KB

下载

检查栈是否为空

// 检查栈是否为空
// 下一个实现的是isEmpty，如果栈为空的话将返回true，否则就返回false；
this.isEmpty = function(){
    return items.length == 0;
}

// 类似于数组的length属性，我们也能实现栈的length。 对于集合，
// 最好用size代替length。因为栈的内部使用数组保存元素，所以能简单地返回栈的长度
this.size = function(){
    return items.length;
}
1
2
3
4
5
6
7
8
9
10
11

清空和打印栈元素

//清空和打印栈元素
// 最后我们来实现以下clear方法. clear 方法用来移除栈里所有的元素,把栈清空. 实现这个发给方法最简单的方法是.
this.clear = function(){
    items = []
}
// 另外也可以多次调用pop方法,把数组中的元素全部移除,这样也能实现clear方法.
1
2
3
4
5
6

小测试

// 通过一个例子来放松一下: 
// 为了检查栈里的内容,我们来实现一个辅助方法,叫做print. 它会把栈里的元素
// 全部输出到控制台
this.print=function(){
    console.log(items.toString());
};
// 这样我们完整的创建了栈
1
2
3
4
5
6
7

栈的使用

// 使用Stack 类
// 首先，我们需要初始化Stack类。然后，验证一下栈是否为空，（输出为true 还没有在栈里添加元素）
let stack = new Stack();
// console.log(stack.isEmpty()); //true
stack.push(5);
stack.push(8);
console.log(stack.peek());  //输出8

// 在添加一个元素
stack.push(11);
console.log(stack.size());
// 我们往栈里添加了11。如果调用size方法，输出为3，因为栈里有三个元素（5、8和11）。
// 如果我们调用isEmpty方法，会看到输出了false（因为栈里有三个元素，不是空栈）。最后，
// 我们再添加一个元素：
stack.push(15);
// console.log(stack.size());

// 然后，调用两次pop方法 从栈里移除两个元素
stack.pop();
stack.pop();
console.log(stack.size());  //输出为2
stack.print() //输出 5,8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

ECMAScript 6 和 Stack 类

// ECMAScript 6 和 Stack 类
// 我们花点时间分析一下代码，看看是否能用ECMAScript 6（ES6）的新功能来改进。
// 我们创建了一个可以当作类来使用的Stack函数。JavaScript函数都有构造函数，可以用来模拟
// 类的行为。我们声明了一个私有的items变量，它只能被Stack函数/类访问。然而，这个方法为每
// 个类的实例都创建一个items变量的副本。因此，如果要创建多个Stack实例，它就不太适合了。
// 看看如何用ES6新语法声明Stack类，并和前面的做法比较一下优缺点。

// class Stack{
//     constructor(){
//         this.items = [];
//     }
//     push(elemet){
//         this.items.push(elemet);
//     }
//     // 其他方法
// }
// 只是用ES6的简化语法把Stack函数转换成Stack类。这种方法不能像其他语言（Java、
// C++、C#）一样直接在类里面声明变量，只能在类的构造函数constructor里声明（行{1}），
// 在类的其他函数里用this.nameofVariable就可以引用这个变量。
// 尽管代码看起来更简洁、更漂亮，变量items却是公共的。ES6的类是基于原型的。虽然基
// 于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性（变量）
// 或方法。而且，在这种情况下，我们希望Stack类的用户只能访问暴露给类的方法。否则，就有
// 可能从栈的中间移除元素（因为我们用数组来存储其值），这不是我们希望看到的。

// 1.用ES6的限定作用域Symbol实现类
// ES6新增了一种叫做Symbol的基本类型，它是不可变的，可以用作对象属性，看看怎么用它来在Stack累中声明items属性

let _items = Symbol();

class Stack {
    constructor() {
        this[_items] = []
    }
    // Stack的方法
    push = function (elemet) {
        this[_items].push(elemet)
    }
    pop = function () {
        return this[_items].pop();
    }
    peek = function () {
        return this[_items][this[_items].length - 1];
    }
    isEmpty = function () {
        return this[_items].length == 0;
    }
    clear = function () {
        this[_items] = []
    }
    print = function () {
        console.log(this[_items].toString());
    };
    size = function () {
        return this[_items].length;
    }
}
// 在上面代码中，我们声明了Symbol类型的变量_items,在类的 constructor 函数中初始化它的值。 
// 要访问_items 只需要把所有的this.items 都换成this[_items]
// 这种方法创建了一个假的私有属性， 因为ES6新增的 Object.getOwnPropertySymbols方法能够取到类里面声明的所有Symbols属性，
// let stack = new Stack();
// stack.push(5)
// stack.push(8);
// let objectSymbols = Object.getOwnPropertySymbols(stack);
// console.log(objectSymbols.length); // 1
// console.log(objectSymbols); // [Symbol()]
// console.log(objectSymbols[0]); // Symbol()
// stack[objectSymbols[0]].push(1); 
// stack.print();

// es6的weekMap 实现类
const items = new WeakMap();

// class Stack{
//     constructor(){
//         items.set(this,[]);
//     }
//     push(elemet){
//         let s = items.get(this);
//         s.push(elemet)
//     }
//     pop(){
//         let s = items.get(this);
//         let r = s.pop()
//         return r
//     }
// }
// 现在我们知道，items在Stack类里是真正的私有属性了，但还有一件事要做。items现在
// 仍然是在Stack类以外声明的，因此谁都可以改动它。我们要用一个闭包（外层函数）把Stack
// 类包起来，这样就只能在这个函数里访问WeakMap：
let Stack = (function(){
    const items = new WeakMap();
    class Stack{
        constructor(){
            items.set(this,[])
        }
    }
    return Stack
})()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

用栈解决问题

栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作（后
面的章节讨论图和回溯问题时，我们会学习如何应用这个例子）。Java和C#用栈来存储变量和方
法调用，特别是处理递归算法时，有可能抛出一个栈溢出异常（后面的章节也会介绍）。
既然我们已经了解了Stack类的用法，不妨用它来解决一些计算机科学问题。本节，我们将
学习使用栈的三个最著名的算法示例。首先是十进制转二进制问题，以及任意进制转换的算法；
然后是平衡圆括号问题；最后，我们会学习如何用栈解决汉诺塔问题。

进制转换

function baseConverter(decNumber, base) {
    var remStack = new Stack(), //实例化栈
        rem,
        baseString = "",
        digits = '0123456789ABCDEF';
    while (decNumber > 0) {
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()]
    }
    return baseString;
}
console.log(baseConverter(100345, 2));
console.log(baseConverter(100345, 8));
console.log(baseConverter(100345, 16)); 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18