数据结构之栈与队列

发布于 2022-06-22 15:41:09 字数 7823 浏览 845 评论 0

一、栈

栈（stack）又名堆栈，是一种遵循后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

堆栈可以用链表和数组两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是 Stack 结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。

class Stack {
    constructor() {
        this.top = null; // 栈顶指针
        this.size = 0;
    }
    push(val) {
        this.top = {
            data: val,
            next: this.top // 栈顶元素的下一位元素
        };
        this.size++;
    }
    pop() {
        if(this.top === null) return null;
        let out = this.top;
        this.top = this.top.next;
        if(this.size > 0) this.size--;
        return out.data;
    }
    peek() {
        return this.top ===null ? null : this.top.data;
    }
    clear() {
        this.top = null;
        this.size = 0;
    }
    displayAll() {
        if(this.size === null) return null;
        let arr = [];
        let current = this.top;
        for(let len = this.size - 1, i = len; i >= 0; i--) {
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    }
}
let stack = new Stack();
stack.push(11);
stack.push(22);
stack.push(33);
stack.push(44);
stack.pop(); // 44
stack.displayAll(); //  [11, 22, 33]
console.log(stack);

栈的应用

1. 数制间的相互转换（十进制转化为任何进制）

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数
的数字,实现转换的算法如下。
(1) 最高位为 n % b,将此位压入栈。
(2) 使用 n/b 代替 n。
(3) 重复步骤 1 和 2,直到 n 等于 0,且没有余数。
(4) 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符
串形式。

function mulBase(num, base) {
    let stack = new Stack();
    let converted = '';
    let digits = '0123456789ABCDEF';
    while(num) {
        stack.push(num % base);
        num = Math.floor(num /= base);
    }
    while(stack.size) {
        converted += digits[stack.pop()];
    }
    return converted;
}
mulBase(4,2);
mulBase(1231,16); // 4CF
mulBase(1231,8); // 2317
mulBase(1231,2); // 10011001111

注：在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。

2. 判断回文

使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。

字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可，如果它们相等，就是一个回文。

function isPlin(str) {
    let stack = new Stack();
    let nstr = '';
    for(let i = 0, len = str.length; i < len; i++) {
        stack.push(str[i]);
    }
    while(stack.size) {
        nstr += stack.pop();
    }
    return str === nstr ? true : false;
}
isPlin('level');
isPlin('1001');
isPlin('word');

判断回文的其他方式：https://www.jianshu.com/p/cf614dd78f44

3. 递归演示

栈的另一个重要应用是在程序设计语言中实现递归调用。

递归调用：一个函数(或过程)直接或间接地调用自己本身，简称递归(Recursive)。
递归是程序设计中的一个强有力的工具。因为递归函数结构清晰，程序易读，正确性很容易得到证明。

为了使递归调用不至于无终止地进行下去，实际上有效的递归调用函数(或过程)应包括两部分：递推规则(方法)，终止条件。
为保证递归调用正确执行，系统设立一个“递归工作栈”，作为整个递归调用过程期间使用的数据存储区。

每一层递归包含的信息如：参数、局部变量、上一层的返回地址构成一个“工作记录” 。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。

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

function factorial(n) {
    let stack = new Stack();
    let product = 1;
    while(n > 1) {
        stack.push(n--);
    }
    while(stack.size) {
        product *= stack.pop();
    }
    return product;
}
factorial(5);
factorial(6);

其他实现方式：https://www.jianshu.com/p/bbc7e54a98d6

4. 括号匹配检查

栈可以用来判断一个算术表达式中的括号是否匹配。编写一个函数,该函数接受一个算术表达式作为参数,返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子:2.3 + 23 / 12 + (3.14159×0.24。

function bracketsMatch(str) {
    let stack = new Stack();
    let text = '';
    for(let i = 0, len = str.length; i < len - 1; i++) {
        let item = str[i];
        if(item === '(') {
            stack.push(item);
        } else if(item === ')') {
            if(!stack.size || stack.pop() !== '(') return 'error: ) 位置' + i;
        }else {
            text += item
        }
    }
    return stack.size > 0 ? 'error:( 位置' + str.lastIndexOf('(') : 'no error' + text;
}

利用后入先出的这个特点，对字符串（算术表达式）进行遍历，如果遇到左括号"("，就把字符"("压入栈。如果遇到右括号")"，就把栈顶的字符弹出栈。

有两种情况可以判断表达式的括号是否匹配：

字符串遍历结束后，栈的长度不为零，说明表达式缺少了右括号；
字符串遍历过程中，如果在做弹出栈的动作时，发现栈的长度已经为零，说明表达式缺少左括号；

另外，可以将符号匹配抽象成一个类，像这样：

function Matcher(left, right) {
  this.left = left;
  this.right = right;
  this.stack = new Stack();
}
Matcher.prototype.match = function () {
};
var m = new Matcher('{', '}');
m.match(str);

二、队列

队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。队列被用在很多地方,比如提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

class Queue {
    constructor() {
        this.font = null;
        this.end = null;
        this.size = 0;
    }
    // 入队
    enqueue(val) {
        let node = {
            data: val,
            next: null
        }
        if(!this.size) {
            this.font = node;
            this.end = node;
            this.size++;
            return; // return;
        }
        this.end.next = node; // 未入队时队尾的元素的下一个指针应指向新入队的元素
        this.end = node; // 新入队的元素变成队尾
        this.size++;
    }
    // 出队
    dequeue() {
        if(!this.size) {
            console.log('Queue is empty!');
            return; // return 'Queue is empty!';
        }       
        let out = this.font.data;
        this.font = this.font.next;
        if(this.size === 1) this.end.data = null; 
        // ===比较操作符 =赋值操作符 这里如果不写会造成当所有元素都出队时队尾还有值 像下图的情况
        if(this.size > 0) this.size--;
        return out;
    }
    // print
    print() {
        if(!this.size) {
            return false;
        }
        let arr = [];
        let current = this.font;
        // while(this.size) {
        //     arr.push(current.data);
        //     current = current.next;
        //     this.size--; // 这种方式会改变原队列 使最后队列为空
        // }
        for(let i = 0, len = this.size; i < len; i++) {
            arr.push(current.data);
            current = current.next;
        }
        return arr;
    }
}

let q = new Queue();
q.enqueue(11);
q.enqueue(22);
q.enqueue(33);
q.print(); // [11, 22, 33]
console.log(q);