什么是堆栈

定义

堆栈（Stack）是一种数据结构，用于存储一组元素，并且只允许在一端进行添加和移除操作。这种操作方式被称为“后进先出”（LIFO, Last In First Out）。这意味着最后添加的元素会最先被移除。堆栈在计算机科学和编程中有着广泛的应用，例如在函数调用、表达式求值、深度优先搜索等场景中。

堆栈主要支持以下几种基本操作：

• 压栈（Push）：将一个元素添加到堆栈的顶端。
• 出栈（Pop）：移除并返回堆栈顶端的元素。如果堆栈为空，则操作可能会失败或抛出异常。
• 查看栈顶元素（Peek 或 Top）： 返回堆栈顶端的元素，但不移除它。
• 检查堆栈是否为空（IsEmpty）：判断堆栈中是否还有元素。
• 获取堆栈的大小（Size）：返回堆栈中元素的个数。

堆栈的应用

• 函数调用：在程序执行过程中，函数调用会使用堆栈来保存当前的执行状态（例如局部变量和返回地址）。这就是所谓的“调用栈”。
• 表达式求值：堆栈可以用于中缀表达式转后缀表达式（逆波兰表达式），以及后缀表达式的求值。
• 深度优先搜索（DFS）：在图和树的遍历中，堆栈可以用于实现深度优先搜索算法。
• 撤销操作：在文本编辑器等应用中，堆栈可以用于实现撤销（Undo）功能，记录用户的操作。

堆栈的优缺点

优点

• 操作简单：堆栈的操作非常简单，只有几种基本操作。
• 高效：堆栈的操作时间复杂度通常为 O(1)。

缺点

• 受限访问：只能访问堆栈顶端的元素，无法直接访问其他元素。
• 空间浪费：如果使用数组实现堆栈，可能会预留不必要的空间。

队列的实现

节点类

首先，我们需要一个节点类来表示链表中的每个节点。每个节点包含一个数据部分和一个指向下一个节点的指针。

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

队列类

• constructor：初始化队列，设置队头和队尾指针为 null 和元素计数为 0。
• enqueue：将元素加入队列尾部。
• dequeue：从队列头部移除元素。
• peek：查看队头元素，但不移除。
• isEmpty：检查队列是否为空。
• size：获取队列中的元素个数。

class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.count = 0;
    }

    enqueue(item) {
        const newNode = new Node(item);
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
        this.count += 1;
    }

    dequeue() {
        if (!this.isEmpty()) {
            const item = this.front.data;
            this.front = this.front.next;
            if (!this.front) {
                this.rear = null;
            }
            this.count -= 1;
            return item;
        } else {
            throw new Error("dequeue from empty queue");
        }
    }

    peek() {
        if (!this.isEmpty()) {
            return this.front.data;
        } else {
            throw new Error("peek from empty queue");
        }
    }

    isEmpty() {
        return this.front === null;
    }

    size() {
        return this.count;
    }
}

示例用法

以下是如何使用上述队列类的示例：

const queue = new Queue();

// 入队
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(`队头元素: ${queue.peek()}`);  // 输出: 队头元素: 1
console.log(`队列大小: ${queue.size()}`);  // 输出: 队列大小: 3

// 出队
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 1
console.log(`队头元素: ${queue.peek()}`);  // 输出: 队头元素: 2
console.log(`队列大小: ${queue.size()}`);  // 输出: 队列大小: 2

// 检查是否为空
console.log(`队列是否为空: ${queue.isEmpty()}`);  // 输出: 队列是否为空: false

// 继续出队
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 2
console.log(`出队元素: ${queue.dequeue()}`);  // 输出: 出队元素: 3

// 检查是否为空
console.log(`队列是否为空: ${queue.isEmpty()}`);  // 输出: 队列是否为空: true

详细说明

Node 类：

• data 属性存储节点的数据。
• next 属性指向下一个节点。

Queue 类：

• constructor 方法初始化队列，front 和 rear 属性分别指向队列的头部和尾部，count 属性记录队列中元素的个数。
• enqueue 方法创建一个新节点，将其添加到队列的尾部，并更新 rear 和 count。如果队列为空，还需要更新 front。
• dequeue 方法移除并返回队列头部节点的数据，更新 front 和 count，如果队列为空则抛出异常。如果 front 变为 null，还需要更新 rear 为 null。
• peek 方法返回队列头部节点的数据，但不移除节点，如果队列为空则抛出异常。
• isEmpty 方法检查 front 是否为 null，以确定队列是否为空。
• size 方法返回 count 的值，即队列中元素的个数。

通过上述实现，你可以使用链表来管理队列中的元素，从而实现高效的队列操作。

总结

堆栈是一种简单而强大的数据结构，广泛应用于各种计算机科学和编程问题中。理解和掌握堆栈的基本操作和应用场景，对于编写高效和可靠的代码非常重要。