数据结构-栈

摘要：栈就是和列表类似的一种数据结构它可以用来解决计算机世界里的很多问题栈是一种高效的数据结构因为数据只能在栈顶添加或删除所以这样的操作很快而且容易实现栈的使用遍布程序语言的方方面面从表达式求值到处理函数调用栈的操作栈只能通过列表的一端访问这一端

栈就是和列表类似的一种数据结构, 它可以用来解决计算机世界里的很多问题. 栈是一种高效的数据结构, 因为数据只能在栈顶添加或删除, 所以这样的操作很快, 而且容易实现. 栈的使用遍布程序语言的方方面面, 从表达式求值到处理函数调用.

栈只能通过列表的一端访问, 这一端称为栈顶.
栈被称为 先进后出 的数据结构与 队列 相反.

由于栈具有先进后出的特点, 所以任何不在栈顶的元素都无法访问. 为了得到栈底的元素, 必须拿掉上面的元素.

对栈的三种主要操作:

将一个元素压入栈 使用push().

将一个元素弹出栈 使用pop().

预览栈顶的元素 peek().

这里需要注意的是的第三种. pop()方法虽然可访问栈顶的元素, 但是调用该方法后, 栈顶元素也就从栈中被永久删除. peek()只返回栈顶元素, 而不删除.

这三种为主要方法, 但是栈还有其他方法和属性. clear()清除栈内所有元素, length属性记录栈内元素的个数. 我们还可以定义一个empty属性, 用以表示栈内是否含有元素, 不过使用length属性也可以达到相同目的.

实现一个栈, 首要条件是决定存储数据的底层数据结构. 这里采用数组.

从定义Stack类的构造函数开始:

class Stack {
    constructor() {
        this._dataStore = [];
        this._top = 0;
    }
    push(element) {
        this._dataStore[this._top++] = element;
    }
    pop(element) {
        return this._dataStore[--this._top];
    }
    peek() {
        return this._dataStore[this._top - 1];
    }
    length() {
        return this._top;
    }
    clear() {
        this._top = 0;
    }
}

用数组_dataStore保存栈内元素, 构造函数将其初始化为一个空数组. 变量_top记录栈顶位置, 被构造函数初始化为0, 表示栈顶对应数组的其实位置0. 如果有元素被压入栈, 该变量将随之变化.

push()方法. 向栈中压入一个新元素时, 需要将其保存在数组中变量_top所对应的位置, 然后将_top加1, 让其指向数组中下一个空位置. 这里要注意++操作符的位置, 它放在变量后面, 新元素就会放在_top当前值对应位置, 然后再加1, 指向下一个位置.

pop()方法. 恰好与push()方法相反. 有返回值, 返回栈顶元素. 这里要注意--操作符的位置, 它放在变量前面, 先对_top减1然后再删除对应位置元素.

peek()方法. 返回数组的第_top - 1个位置的元素, 即栈顶元素. 如果对空栈调用peek(), 结果为undefined.

length()方法. 通过返回变量_top值的方式返回栈内的元素个数.

clear()方法. 将变量_top设为0, 轻松清空一个栈.

可以利用栈将一个数字从一种数制转化成另一种数制. 假设将数字n转化为以b为基数的数字, 实现转化的算法如下.

最高位为n % b, 将此位压入栈.

使用n / b代替n.

重复步骤1和2, 直到n等于0, 且没有余数.

持续将栈内元素弹出, 直到栈为空, 依次将这些元素排列, 就得到转换后数字的字符串形式.

注意: 此算法只针对基数为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;
};

console.log(mulBase(32, 2)); // 得到32的二进制值: 100000
console.log(mulBase(88, 8)); // 得到88的八进制值: 130   

回文: 一个单词、短语和数字, 从前往后写和从后往前写都是一样的. eg: 单词"dad"、"racecar"就是回文; 忽略空格和标点下面这个句子也是回文: "A man, a plan, a canal: Panama"; 数字101也是回文.

使用栈可以轻松判断一个字符串是否是回文. 我们将拿到的字符串的每一个字符按从左至右的顺序入栈. 当所有字符都入栈后, 栈内就保存了一个反转后的字符串, 最后的字符在栈顶, 第一个字符在栈底.
字符串完整压入栈内后, 通过持续弹出栈中的每一个字母就可以得到一个新的字符串, 该字符串刚好与原来的字符串顺序相反. 我们只需要比较这两个字符串即可.

function isPalindrome(word) {
    const s = new Stack();
    
    for(let w of word) {
        s.push(w)
    };
    let rword = "";
    while(s.length() > 0) {
        rword += s.pop();
    };

    return word === rword;
};

console.log(isPalindrome("hello")); // false
console.log(isPalindrome("dad")); // true

栈常常被用来实现编程语言, 使用栈实现递归即为一例. 这里只是用栈来模拟递归过程.

为了演示如何用栈实现递归, 考虑一下求阶乘函数的递归定义. 首先看5的阶乘是怎么定义的: 5! = 5 * 4 * 3 * 2 * 1 = 120

下面是一个递归函数, 可以计算任何数字的阶乘:

function factorial(n) {
    if(n === 0) return 1;

    return n * factorial(n - 1);
};

// 尾掉优化
function factorial(n, total = 1) {
    if(n === 0) return total;

    return factorial(n - 1, n * total);
};

console.log(factorial(5)); // 120

使用栈来模拟计算5!的过程, 首先将数字从5到1入栈, 然后使用一个循环, 将数字挨个弹出连乘, 就得到正确答案

下面使用栈模拟递归过程:

function fact(n) {
    const s = new Stack();

    while(n > 1) {
        s.push(n--);
    };
    
    let product = 1;
    while(s.length() > 0) {
        product *= s.pop();
    };
    
    return product;
};

console.log(fact(5)); // 120

例如判断表达式为2.3 + 23 / 12 + (3.14159 * 0.24的算数表达式的括号是否匹配.

function fn(express) {
    const s = new Stack();
    
    for (let i = 0; i < express.length; ++i) {
        if (express[i] === `(`) {
            s.push(i);
        } else if (express[i] === `)`) {
            s.pop();
        }
    };
    console.log(`在第${s.peek()}个字符是不匹配的括号`)
};

fn("2.3 + 23 / 12 + (3.14159 * 0.24"); // 在第16个字符是不匹配的括号

表达式详解
一个算数表达式的后缀表达形式如下:
op1 op2 operator
使用两个栈, 一个用来存储操作数, 另一个用来存储操作符, 设计并实现一个函数, 该函数可以将中缀表达式转换为后缀表达式, 利用栈堆该表达式求值.

const express = "1+((2+3)*4)-5";

function fn(express) {
    const s1 = new Stack(); // 操作符栈
    const s2 = new Stack(); // 操作数栈
    const arr = express.split("");
    arr.forEach((i, index) => {
        if(/^[0-9]*$/.test(i)) {
            s2.push(i)
        } else if(["+", "-", "*", "/"].includes(i)) {
            if(s1.length() === 0 || s1.peek() === "(") {
                s1.push(i)
            } else if (["*", "/"].includes(i) && ["+", "-"].includes(s1.peek())) {
                s1.push(i)
            } else {
                s2.push(s1.pop());
                if(s1.length() === 0 || s1.peek() === "(") {
                    s1.push(i);
                }
            }
        } else if (i === "(") {
            s1.push(i);
        } else if (i === ")") {
            while(s1.peek() !== "(") {
                s2.push(s1.pop());
            }
            s1.pop();
        }
    });
    
    while(s1.length() > 0) {
        s2.push(s1.pop());
    };

    let str = ""
    while(s2.length() > 0) {
        str += ` ${s2.pop()}`;
    };
    
    return str;
};

console.log(fn(express))

现实生活中的例子是佩兹糖果盒. 想象一下你有一盒佩兹糖果, 里面塞满了红色、黄色和白色的糖果, 但是你不喜欢黄色的糖果. 使用栈(有可能用到多个栈) 写一段程序, 在不改变盒内其它糖果叠放顺序的基础上, 将黄色糖果移除.

const boxS = new Stack(); 
boxS.push("red");
boxS.push("yellow");
boxS.push("white");
boxS.push("white");
boxS.push("yellow");
boxS.push("yellow");
boxS.push("red");
boxS.push("red");
boxS.push("white");
boxS.push("yellow");
boxS.push("red");

function changeFn(sourceStack) {
    const s1 = new Stack(); 
    const s2 = new Stack(); 
    const resultS = new Stack(); 

    while(sourceStack.length() > 0) {
        if(sourceStack.peek() === "yellow") {
            s1.push(sourceStack.pop())
        } else {
            s2.push(sourceStack.pop())
        }
    };

    while(s2.length() > 0) {
        resultS.push(s2.pop());
    };
    return resultS;
};
changeFn(boxS);