JS栈的实现

发表于 |

栈是一个很基础的数据结构, 属于先进后出类型, 在底层的软件当中有着广泛的应用

下面是相关API代码以及示例代码:

1
2
3
4
5
6
7
8
9
function Stack(){
	this.dataStore = []; //用数组实现
	this.top = 0;
	this.push = push;   //栈的压入
	this.pop = pop;     //栈的弹出
	this.peek = peek;   //栈的顶部元素
	this.length = length;
	this.clear = clear;  
}
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
100
101
function push(element) {
	this.dataStore[this.top++] = element;
}
function pop(){
    return this.dataStore[--this.top];
}
function peek(){
    return this.dataStore[this.top-1];
}
function length(){
    return this.top;
}
function clear(){
    this.top = 0;
}
//以下为测试代码
function test_stack(){
    var s = new Stack();
    s.push("David");
    s.push("Raymond");
    s.push("Bryan");
    console.log("length: " + s.length());
    console.log(s.peek());
    var popped = s.pop();
    console.log("The popped element is: " + popped);
    console.log(s.peek());
    s.push("Cynthia");
    console.log(s.peek());
    s.clear();
    console.log("length: " + s.length());
    console.log(s.peek());
    s.push("Cynthia");
    console.log(s.peek());
}
//十进制转换到2至9进制(使用了栈这种结构)
function mulBase(num, base) {
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    var converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}
//进制转换测试用例
function mulBase_test(){
    var base = 2;
    var num = 32;
    var newNum = mulBase(num, base);
    console.log(num + "converted to base " + base + " is " + newNum);
}
//判定给定字符串是否是回文数
function isPalindrome(word) {
    var s = new Stack();
    for (var i = 0; i < word.length; ++i) {
        s.push(word[i]);
    }
    var rword = "";
    while (s.length() > 0) {
        rword += s.pop();
    }
    if (word == rword) {
        return true;
    }
    else {
        return false;
    }
}
//递归计算阶乘
function factorial(n) {
    if (n === 0) {
        return 1;
    }
    else {
        return n * factorial(n-1);
    }
}
//用栈模拟递归过程
function fact(n){
    var s = new Stack();
    while(n > 1) {
        s.push(n--);
    }
    var product = 1;
    while (s.length() > 0){
        product *= s.pop();
    }
    return product;
}
0%