堆栈是一种简单的线性数据结构，其工作原理类似于一堆盘子？️。它遵循后进先出 (LIFO) 原则。将其视为一堆盘子：您只能添加或删除堆顶部的盘子。
为了更好地理解栈，让我们来一次短暂的想象之旅吧？.
想象一下您在一家高档餐厅??️，厨房工作人员正在为忙碌的夜晚做准备???。在餐具区，有一大堆盘子等待使用。当食客到来、订单纷至沓来时，工作人员会从最上面的盘子中取出盘子。当添加干净的盘子时，它们会直接放在上面。这个简单的系统确保了堆叠底部放置时间最长的盘子最后被使用，而顶部刚清洁过的盘子首先被使用✨。
本质上，这就是堆栈数据结构的工作原理。堆栈是一种遵循后进先出 (LIFO) 原则的线性数据结构。就像我们的一堆盘子一样，最后添加到堆栈中的项目是第一个被删除的项目。
在这个关于堆栈数据结构的综合教程中，我们将通过简单、适合初学者的方法探索以下主题：
你准备好了吗？让我们深入了解
堆栈是一种遵循后进先出（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 |
可以在堆栈上执行的基本操作是：
堆栈在计算机科学和软件开发中无处不在。以下是一些常见的应用：
撤消功能：在文本编辑器或图形设计软件中，每个操作都被推入堆栈。当您点击“撤消”时，最近的操作将从堆栈中弹出并反转。
浏览器历史记录：当您访问新页面时，它将被推送到堆栈上。 “后退”按钮会将当前页面从堆栈中弹出，显示上一页。
函数调用堆栈：在编程语言中，函数调用是使用堆栈来管理的。当一个函数被调用时，它被压入调用栈。当它返回时，它会弹出。
表达式计算：堆栈用于计算算术表达式，尤其是后缀表示法的表达式。
回溯算法：在解决迷宫或谜题等问题中，堆栈可以跟踪所采取的路径，以便在需要时轻松回溯。
现在，让我们用 JavaScript 实现一个 Stack。重要的是要知道在 JavaScript 中实现堆栈有不同的方法。实现堆栈的常见方法之一是使用数组，另一种方法是使用链表。在本文中，我们将使用链表（单链表）实现堆栈。
我希望你还记得链表是如何工作的吗？您可能需要查看我们本系列之前的一篇文章中的链表实现。
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 ?
}
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++;
}
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;
}
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;
}
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;
}
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;
}
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 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.
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.
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:
Stay tuned and happy coding ???
以上是了解堆栈数据结构：在 JavaScript 中实现堆栈的分步指南的详细内容。更多信息请关注PHP中文网其他相关文章！
