堆栈数据结构介绍

堆栈是一种包含元素列表的数据结构。堆栈基于 LIFO 原则工作，即后进先出，这意味着最近添加的元素是第一个删除的元素。

一个堆栈有两个主要的操作，它们只发生在堆栈的顶部：push 和 pop。push 操作将一个元素放在栈顶，而 pop 操作从栈顶移除一个元素。

名称堆栈来自对一组物理项目的类比，例如 DVD 光盘、书籍，它们相互堆叠。

堆栈有很多应用。例如，最简单的就是反转一个词。要做到这一点，您需要一个字母一个字母地将一个单词推入堆栈，然后从堆栈中弹出这些字母。

堆栈的其他应用是文本编辑器中的“撤消”机制、语法解析、函数调用和表达式转换（中缀到后缀、中缀到前缀、后缀到中缀和前缀到中缀）。

JavaScript Array 类型提供了 push() 和 pop() 方法，允许您将数组用作堆栈。

push() 方法

push() 方法允许您将一个或多个元素添加到数组的末尾。push() 方法返回 length 属性的值，该值指定数组中的元素数。

如果将数组视为堆栈，则 push() 方法在堆栈顶部添加一个或多个元素。下面的示例创建一个名为 stack 的空数组，并在 stack 数组的末尾一个接一个地添加五个数字。这就像将每个数字压入堆栈顶部。


let stack = [];
stack.push(1);console.log(stack); // [1]
stack.push(2);console.log(stack); // [1,2]
stack.push(3);console.log(stack); // [1,2,3]
stack.push(4);console.log(stack); // [1,2,3,4]
stack.push(5);console.log(stack); // [1,2,3,4,5]

下图说明了上述脚本中的每个步骤。

最初，堆栈是空的。每次，我们都会调用该push()方法向堆栈中添加一个数字。5 次调用后，堆栈有 5 个元素。

请注意，push()方法还允许您一次将多个项目添加到数组的末尾。

pop() 方法

pop()方法移除数组末尾的元素并将该元素返回给调用者。如果数组为空，则pop()方法返回undefined。

以下示例显示如何使用 pop() 方法从堆栈顶部弹出元素。


console.log(stack.pop()); //  5console.log(stack); // [1,2,3,4];
console.log(stack.pop()); //  4console.log(stack); // [1,2,3];
console.log(stack.pop()); //  3console.log(stack); // [1,2];
console.log(stack.pop()); //  2console.log(stack); // [1];
console.log(stack.pop()); //  1console.log(stack); // []; -> empty
console.log(stack.pop()); //  undefined

下图说明了脚本中的每个步骤。

最初，堆栈有 5 个元素。pop()方法删除数组末尾的元素，即一次删除一个堆栈顶部的元素。五次操作后，堆栈为空。

使用 JavaScript 堆栈反转字符串

以下示例向您展示了如何使用堆栈反转字符串。


function reverse(str) {    let stack = [];    // push letter into stack    for (let i = 0; i < str.length; i++) {        stack.push(str[i]);    }    // pop letter from the stack    let reverseStr = '';    while (stack.length > 0) {        reverseStr += stack.pop();    }    return reverseStr;}console.log(reverse('JavaScript Stack')); //kcatS tpircSavaJ