了解堆栈数据结构：在 JavaScript 中实现堆栈的分步指南

堆栈是一种简单的线性数据结构，其工作原理类似于一堆盘子？️。它遵循后进先出 (LIFO) 原则。将其视为一堆盘子：您只能添加或删除堆顶部的盘子。

为了更好地理解栈，让我们来一次短暂的想象之旅吧？.
想象一下您在一家高档餐厅??️，厨房工作人员正在为忙碌的夜晚做准备??‍?。在餐具区，有一大堆盘子等待使用。当食客到来、订单纷至沓来时，工作人员会从最上面的盘子中取出盘子。当添加干净的盘子时，它们会直接放在上面。这个简单的系统确保了堆叠底部放置时间最长的盘子最后被使用，而顶部刚清洁过的盘子首先被使用✨。

本质上，这就是堆栈数据结构的工作原理。堆栈是一种遵循后进先出 (LIFO) 原则的线性数据结构。就像我们的一堆盘子一样，最后添加到堆栈中的项目是第一个被删除的项目。

目录

在这个关于堆栈数据结构的综合教程中，我们将通过简单、适合初学者的方法探索以下主题：

1. 什么是堆栈？
2. 使用堆栈的优点和缺点
3. 堆栈的实际应用
4. 堆栈上的关键操作
5. JavaScript 中的堆栈实现
6. 结论

---

---

你准备好了吗？让我们深入了解

什么是堆栈？

堆栈是一种遵循后进先出（LIFO）原则的线性数据结构。这意味着最后添加到堆栈的元素将是第一个被删除的元素。将其想象为一摞书：您只能添加或删除书堆顶部的书。

使用堆栈的优点和缺点

在我们继续流程并编写一些代码之前，了解在哪里以及在哪里不使用 Stack 是很有帮助的。下表详细给出了堆栈的优点和缺点。

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

堆栈上的关键操作

可以在堆栈上执行的基本操作是：

1. push()：将一个元素添加到栈顶。
2. pop()：从堆栈中删除最顶层的元素。
3. peek()：返回栈顶元素，但不删除它。
4. isEmpty()：检查堆栈是否为空。
5. size()：返回堆栈中元素的数量。

堆栈的实际应用

堆栈在计算机科学和软件开发中无处不在。以下是一些常见的应用：

1. 撤消功能：在文本编辑器或图形设计软件中，每个操作都被推入堆栈。当您点击“撤消”时，最近的操作将从堆栈中弹出并反转。

2. 浏览器历史记录：当您访问新页面时，它将被推送到堆栈上。 “后退”按钮会将当前页面从堆栈中弹出，显示上一页。

3. 函数调用堆栈：在编程语言中，函数调用是使用堆栈来管理的。当一个函数被调用时，它被压入调用栈。当它返回时，它会弹出。

4. 表达式计算：堆栈用于计算算术表达式，尤其是后缀表示法的表达式。

5. 回溯算法：在解决迷宫或谜题等问题中，堆栈可以跟踪所采取的路径，以便在需要时轻松回溯。

JavaScript 中的堆栈实现

现在，让我们用 JavaScript 实现一个 Stack。重要的是要知道在 JavaScript 中实现堆栈有不同的方法。实现堆栈的常见方法之一是使用数组，另一种方法是使用链表。在本文中，我们将使用链表（单链表）实现堆栈。

使用链表实现堆栈

我希望你还记得链表是如何工作的吗？您可能需要查看我们本系列之前的一篇文章中的链表实现。

如何在 JavaScript 中实现单链表

伟大的解决方案？ ・ 10 月 4 日

#javascript #初学者 ＃编程 #dsa

Now, let's start implementing our stack using singly linked list. Shall we?

First, we'll create a Node class to represent our stack individual item.

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

Then, we'll create a Stack class to represent our stack.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Push Operation

The push operation adds a new element to the top of the stack. It creates a new StackNode, sets its next pointer to the current top, and then updates top to point to this new node. Finally, it increments the size.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

Pop Operation

The pop operation removes the topmost element from the stack. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it removes the top element, updates the top pointer to the next node, and decrements the size. Finally, it returns the removed element.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Peek Operation

The peek operation returns the top element without removing it. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it returns the data of the top element.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty Operation

The isEmpty operation checks if the stack is empty. It returns true if the stack is empty, and false otherwise.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

getSize Operation

The getSize operation returns the size of the stack. It returns the number of elements in the stack.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Print Operation

The print operation prints the stack. It returns the data of the top element.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Usage Example

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

In this implementation, we used a linked list (singly linked list) structure to represent our stack. Each element is a Node with a data value and a reference to the next Node. The top of the stack is always the most recently added Node.

Conclusion

Stacks are a fundamental data structure in computer science that follow the Last In, First Out (LIFO) principle. They are used in various applications, including managing function calls, implementing undo functionality, and evaluating arithmetic expressions.

In this tutorial, we've covered the basics of stacks, pros and cons of using them, and their implementation in JavaScript (using linked list). Understanding stacks is not just about knowing how to implement them, but also recognizing when they're the right tool for solving a problem.

As you continue your journey in software development, you'll find that stacks are an indispensable tool in your problem-solving toolkit. They're simple yet powerful, and mastering them will significantly enhance your ability to design efficient algorithms and data structures.

---

---

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding ?‍??

以上是了解堆栈数据结构：在 JavaScript 中实现堆栈的分步指南的详细内容。更多信息请关注PHP中文网其他相关文章！