用栈进行进制转换和回文判断

发表于 | 阅读次数

0

主要是用到了”栈”这个数据结构，之前在上数据结构这门课时感觉栈和队列没有什么有趣的地方，后来仔细复习看书发现也是有很大用处的，比如说回文判断和进制转换。

1. 定义栈

先定义一个栈的类，该类可实现栈的出栈入栈等基本操作

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
// JavaScript
function Stack {
    this.data = [];     // 储存数组
    this.top = 0;       // 栈顶位置
    this.push = push;
    this.peek = peek;   // 栈顶元素
}
function push(element) { // 入栈
    this.data[this.top++] = element;
}
function peek() {
    return this.data[this.top-1];
}
function pop() { // 出栈
    return this.data[--this.top];
}
function clear () {
    this.top = 0;
}
function length() {
    return this.top;
}

2. 数制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
// JavaScript
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;
}

3. 回文判断

什么是回文

数字： 1001 是回文。
字母： dad 是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// JavaScript
    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;
        }
    }

不用栈操作的话，也可以使用两个指针从两边同时往中间扫，逐个判断。

如果是数字类型，还可以用求余和整除运算取代指针，但是要先想办法获取数字长度。