数据结构知否知否系列之 — 栈篇

数据结构知否知否系列之 — 栈篇

栈（Stack）是一种常用的数据结构，遵循后进先出（LIFO）的原则。在计算机科学领域，栈有着广泛的应用，例如表达式求值、函数调用等。本文将从栈的基本概念出发，详细介绍栈的实现方法及其经典应用场景。

栈简介

栈是一种线性数据结构，其主要特点是只能从栈顶进行插入和删除操作。在现实生活中，栈的应用场景比比皆是，例如盘子的叠放、书籍的堆放等。这些场景都体现了栈的两个基本特性：

1. 仅能从栈顶端存取数据
2. 数据存取遵从后进先出原则

栈的运行机制

为了更好地理解栈的运行机制，我们可以通过代码实现一个栈。下面是一个基于JavaScript的栈实现示例：

初始化栈空间

在构造函数中，我们需要初始化栈的容量和栈顶位置。

/**
 * 
 * @param { Number } capacity 栈空间容量
 */
constructor(capacity) {
    if (!capacity) {
        throw new Error('The capacity field is required!');
    }
    this.capacity = capacity;
    this.stack = new Array(capacity);
    this.top = 0; // 初始化栈顶为 0 
}

栈空间是否为空检查

通过检查栈顶位置是否为0来判断栈是否为空。

isEmpty() {
    return this.top === 0 ? true : false;
}

栈空间是否溢出检查

通过比较栈顶位置和栈的容量来判断栈是否已满。

isOverflow() {
    return this.top === this.capacity;
}

入栈

在入栈操作前需要检查栈是否已满，未满时将元素添加到栈顶位置。

/**
 * 入栈
 * @param { * } element 入栈元素
 */
enStack(element) {
    if (this.isOverflow()) {
        throw new Error('栈已满');
    }
    this.stack[this.top] = element;
    this.top++;
}

出栈

在出栈操作前需要检查栈是否为空，未空时从栈顶位置取出元素。

deStack() {
    if (this.isEmpty()) {
        throw new Error('栈已为空');
    }
    this.top--;
    return this.stack[this.top];
}

栈元素长度

通过栈顶位置信息获取栈中元素的数量。

len() {
    return this.top;
}

清除栈元素

将栈顶位置重置为0，清空栈中的所有元素。

clear() {
    this.top = 0;
}

栈销毁

在一些高级语言中，对象不再被引用时会被自动回收。但在某些情况下，可能需要手动释放内存。

destroy() {
    this.stack = null;
}

栈元素遍历

定义 traversing(isBottom) 方法对栈的元素进行遍历输出，默认为顶部遍历，也可传入 isBottom 参数为 true 从底部开始遍历。

traversing(isBottom = false){
    const arr = [];
    if (isBottom) {
        for (let i=0; i < this.top; i++) {
            arr.push(this.stack[i])
        }
    } else {
        for (let i=this.top-1; i >= 0; i--) {
            arr.push(this.stack[i])
        }
    }
    console.log(arr.join(' | '));
}

JavaScript 数组实现栈

JavaScript 中的数组提供了 push 和 pop 方法，可以很方便地实现栈的功能。

初始化队列

初始化一个存储栈元素的数据结构，如果未传入默认赋值空数组。

function StackStudy(elements) {
![](https://wy-static.wenxiaobai.com/chat-rag-image/3651569744150920820)
    this.elements = elements || [];
}

添加栈元素

使用数组的 push 方法实现入栈操作。

StackStudy.prototype.enStack = function(element) {
    this.elements.push(element);
}

移除栈元素

使用数组的 pop 方法实现出栈操作。

StackStudy.prototype.deStack = function() {
    return this.elements.pop();
}

栈的经典应用

十进制转换为二进制、八进制、十六进制

十进制转换为其他进制的过程可以通过栈来实现。具体步骤是：将十进制数除以目标进制，将余数压入栈中，直到商为0。然后依次弹出栈中的元素，即可得到转换后的结果。

const StackStudy = require('./stack.js');
const str = '0123456789ABCDEF';
![](https://wy-static.wenxiaobai.com/chat-rag-image/2592707794179762131)
function dataConversion(num, type) {
    let x = num;
    const s1 = new StackStudy(20);
    while (x != 0) {
        s1.enStack(x % type);
        x = Math.floor(x / type);
    }
    while (!s1.isEmpty()) {
        console.log(str[s1.deStack()]);
    }
    console.log('--------------------');
    return;
}

平衡园括号

在一些运算中，需要检测表达式中的括号是否平衡。这个问题可以通过栈来解决。具体步骤是：遍历表达式中的每个字符，如果是左括号则入栈，如果是右括号则检查栈顶是否为对应的左括号，如果不是则表达式不合法。

const Stack = require('./stack');
const detectionStr = '[]()'; // 定义需要检测的平衡符号，如何还有别的符号按照这种格式定义
function test(str) {
    let isTermination = false; // 是否终止，默认 false
    let stack = new Stack(20); // 初始化栈空间 {1}
    for (let i=0; i<str.length; i++) { // {2}
        const s = str[i];
        for (let d=0; d<detectionStr.length; d+=2) { // {3}
            const enStackStr = detectionStr[d]; // 入栈字符
            const deStackStr = detectionStr[d+1]; // 出栈字符
            switch (s) {
                case enStackStr : // 入栈 {3.1}
                    stack.enStack(s);
                    break;
                case deStackStr : // 出栈 {3.2}
                    if (stack.isEmpty()) {
                        isTermination = true
                    } else {
                        const currElement = stack.deStack();
                        if (!currElement.includes(enStackStr)) { 
                            isTermination = true
                        }
                    }
                    break;
            }
            if (isTermination) break;
        }
        if (isTermination) { // 存在不匹配符号，提前终止 {4}
            stack.enStack(s);
            break;
        }
    }
    if (stack.isEmpty()) { // {5}
        console.log('检测通过');
    } else {
        console.log('检测不通过，检测不通过符号：');
        stack.traversing()
    }
    return stack.isEmpty();
}