数据结构-栈

发表于 | 分类于 |

chapter-4 栈

特点

  • 高效的数据结构
  • 数据只能在栈顶添加或删除
  • 特殊的列表，栈内元素只能通过列表的一端访问，这一段称为栈顶。
  • 后入先出（LIFO）的数据结构
  • 任何不在栈顶的元素都无法访问，为了得到栈底的元素，必须先拿掉上面的元素
  • 入栈（push），出栈（pop）、预览栈顶元素（peek）

栈的实现

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
function Stack () {
    // 保存栈内元素
    this.dataStore = [];
    // 记录栈顶位置
    this.top = 0;
}
Stack.prototype = {
    constructor: Stack,
    // 向栈中压入元素
    push: function (element) {
        this.dataStore[this.top++] = element;
    },
    // 推出最后一个元素
    pop: function () {
        // 为什么不删除这个元素呢
        return this.dataStore[--this.top];
    },
    // 返回第top - 1个元素
    peek: function () {
        return this.dataStore[this.top - 1];
    },
    // 返回栈内元素个数
    length: function () {
        return this.top;
    },
    // 清空一个栈
    clear: function () {
        // 为什么不把dataStore也清空呢
        this.top = 0;
    }
}

测试结果

2.jpeg

实际问题

将数字n转换为以b为基数的数字，实现转换

  • 最高位为n%b，压入栈
  • 使用n/b代替n
  • 重复前两步，知道n = 0，没有余数
  • 弹出栈内元素，排列

只针对基数为2-9的情况（why？）

1.jpeg

操作符的参考资料：https://developer.mozilla.org/en-US/docs/Web/JavaS
cript/Reference/Operators/Assignment_Operators

数制间转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 数制间的相互转换
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;
}
// 转换为二进制和八进制
mulBase(32, 2);// 100000
mulBase(125, 8);// 175

回文

  • 一个单词、短语或数字，从前往后写和从后往前写都是一样的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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;
        }
        console.log(s.dataStore)
    }
    isPalindrome('hello');// false
    isPalindrome('racecar');// true

递归演示

  • 模拟递归过程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // 使用栈模拟递归过程
    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;
    }
    factorial(5);// 120
    fact(5);// 120