C++ 栈函数

栈： 栈是一种在 C++ 编程语言中的线性数据结构，遵循“后进先出”（LIFO）的原则。最后添加的元素是第一个被删除的元素。因此，它实际上是元素的集合。栈，就像实际的堆栈或堆一样，例如一叠盘子，经常用于数据传输。

在 C++ 中，可以使用标准模板库 (STL) 来处理栈，它提供了功能齐全且高效的栈容器类。此类提供方法和函数来确认栈是否为空、从栈顶删除元素等等。栈在许多任务中都很有用，包括解析表达式、跟踪程序中的函数调用以及解决需要后进先出策略的数据管理问题。

一叠盘子是栈的一个形象的比喻。想象一下，在餐厅里，服务员将一叠干净的盘子端到你的桌子上。当他们继续为你的桌子服务时，他们会把每个盘子叠在上面。一旦你吃完饭，你或你的同伴就会从叠好的盘子顶部取走一个盘子。你开始取出盘子，从最后添加到叠子上的那个开始。当这个过程完成后，叠子就空了，所有的盘子都被取走了。

栈数据结构可以与这个现实世界的例子进行类比

后进先出 (LIFO)：最晚添加到叠子上的盘子是最先被使用的。这种行为可以类比于计算机科学中栈数据结构的操作。

入栈（Push）和出栈（Pop）：将盘子放在叠子顶部表示“入栈”操作，而从叠子中取走盘子则类似于“出栈”操作。

无法访问中间的盘子：就像在电子系统中只能访问栈顶元素一样，你只能访问或删除顶部的盘子，而不会影响其下方的盘子。

C++ 中的栈函数

C++ 标准库中实现栈数据结构的可适应容器称为“栈”。由于栈是后进先出（LIFO）的数据结构，最后添加到栈中的元素是第一个被删除的。标准模板库 (STL) 将 C++ 栈容器作为其 `` 头文件的一部分。为了使用它，我们必须包含该库。

栈的声明和初始化：要使用 C++ 中的栈，您必须首先包含“stack”头文件。使用 `std::stack` 模板，可以声明和初始化栈。

例如

将元素压入栈：可以使用 `push()` 函数将元素添加到栈顶。此操作也称为“入栈”。

示例

弹出栈中的元素：可以使用 `pop()` 方法弹出栈顶元素并检索它。此时，栈顶元素会被移除，但不会返回任何值。

例如

访问栈顶元素

您可以使用 `top()` 函数在不移除它的情况下访问栈顶元素。通过这样做，您可以检查该元素而不会修改栈的内容。

例如

检查栈的大小和空状态

使用 `size()` 方法可以返回栈中元素的数量，而 `empty()` 函数则返回一个布尔值，指示栈是否为空。

例如

清空栈：通过使用一个空栈和 `std::stack` 库的 `swap()` 方法，可以从栈中移除所有元素。

例如

C++ 中栈的实现类型

在 C++ 中，可以使用各种数据结构来构建栈，每种结构都有其自身的优缺点。以下是几种常见的栈实现类型：

基于数组的栈：基于数组的栈将其元素存储在一个固定大小的数组中。它使用一个索引或指针来跟踪栈顶元素。当一个元素被压入栈时，栈顶索引会递增；当一个元素被弹出时，栈顶索引会递减。如果栈的最大大小可预先知晓，此方法既简单又有效。但是，它有大小限制，并且重新调整大小可能很困难且昂贵。

基于链表的栈：在此实现中，栈的内容存储在单向或双向链表中。链表的每个节点代表一个单独的元素，链表的头等同于栈顶。弹出操作会移除头节点，而压入元素则涉及创建新节点并更新头节点。由于基于链表的栈大小是动态的，因此可以添加或删除元素，而无需考虑固定大小数组的限制。此方法在栈大小波动的环境中效果很好，尽管指针会增加一些额外的内存开销。

STL 栈容器：C++ 标准库提供了 `std::stack` 抽象数据类型，它使用各种底层容器（如 `vector` 或 `deque`）来实现。此栈容器通过抽象底层数据结构，使得使用起来非常简单。开发人员可以专注于栈操作（如 push、pop 和 top），而无需关心实现的细节。此方法适用于大多数应用程序，因为它提供了一个简单的用户界面，并允许您根据自己的需求选择最佳的底层数据结构。

基于 vector 的栈：与基于数组的栈一样，基于 vector 的栈将元素存储在 `std::vector` 等动态容器中。当元素被压入 vector 的末尾时，弹出操作会移除最后一个元素。此方法提供动态大小调整，使栈可以根据需要调整大小。它结合了数组和链表的优点，提供了效率和动态大小之间的折衷。

基于 Deque 的栈：Deque（双端队列）是另一种可用于构建栈的容器。Deque 允许在两端进行高效的插入和删除。根据您的需求，您可以将栈顶视为 deque 的前端或后端。基于 deque 的栈具有动态大小调整、高效的插入和删除以及灵活的用法。

您的栈的实现取决于您应用程序的独特需求。如果您想要一个具有指定最大大小的简单栈，基于数组的栈可能是一个不错的选择。对于不断变化的可伸缩性和高效的插入和删除，链表、基于 vector 的栈或基于 deque 的栈更合适。对于许多 C++ 应用程序，STL 的 `std::stack` 通过抽象实现内部工作以方便用户使用，提供了一种实用且灵活的选择。

使用基于数组的栈的示例代码

输出

解释

此 C++ 代码示例使用一个名为 `MyStack` 的自定义类来创建和使用栈数据结构。在此上下文中，栈遵循“后进先出”（LIFO）原则，即最后添加到栈中的元素最先被取出。

栈的行为由 `MyStack` 类管理。它维护 `top` 和 `stackArray` 两个关键属性。`top` 最初设置为 -1，表示一个空栈，它表示栈顶元素的索引。`stackArray` 是一个整数数组，用于存储栈的元素，其最大存储容量由 `MAX` 常量定义。

代码提供了三种主要的栈操作：push、pop 和 isEmpty。`push` 操作可以将元素添加到栈顶。通过将 `top` 的当前值与最大容量进行比较，它可以确定栈是否已满。如果栈已满，它会输出“Stack Overflow!!!”并返回 false。否则，它会将 `top` 递增到下一个可用位置，并将提供的元素添加到 `stackArray`。每次压入的元素都会被显示出来。

另一方面，`pop` 操作使得从栈顶弹出元素变得容易。通过检查 `top` 的值，它可以确定栈是否为空。如果栈为空，它会输出“Stack Underflow!!!”并返回 0 作为错误值。否则，它会从 `stackArray` 的顶部位置弹出元素，然后将 `top` 向下移动以指向栈中的下一个元素，最后返回找到的值。在主函数中，通过一个循环执行此过程，直到栈变空。

使用链表实现栈的示例代码

输出

解释

栈实现：代码首先定义 `StackNode` 结构，它表示基于链表的栈中的一个节点。每个节点都有一个指向下一个节点的引用 (`struct StackNode* next`) 和一个整数数据值 (`int data`)。

初始化栈：将栈顶初始化为 `NULL`，表示一个空栈。这是在任何函数之外完成的，以确保它在整个程序中都可用。

将元素压入栈：`push` 函数接收一个整数值 `newValue`，将其添加到栈中。它创建一个新节点，用输入值填充其数据字段，并将其 `next` 指针设置为当前栈顶。最后，它更新栈顶以指向新节点，从而将新节点添加到栈中。

弹出函数：从栈中移除顶层元素：`pop` 函数会从栈中移除顶层元素。如果栈不为空（`top` 不为 `NULL`），它会显示被弹出元素的值，并将 `top` 指针更新为指向栈中的下一个元素。通过这样做，顶层元素被有效地移除。

`display` 函数用于显示栈中当前存在的元素。它从栈顶开始遍历栈，并显示每个元素的值。如果栈为空，它会清楚地表明栈是空的。

程序使用 do-while 循环重复向用户显示菜单，直到用户选择退出（choice != 4）。根据用户的选择，会调用相应的函数（push、pop 或 show），从而修改或显示栈。

使用 STL 栈容器的栈示例代码

输出

解释

此 C++ 代码使用标准模板库 (STL) 栈容器来实现栈。通过一个标准的菜单，程序允许用户执行各种栈操作。

代码首先包含必要的 C++ 库，例如用于构建栈数据结构的 `stack` 和用于输入输出操作的 `iostream`。此外，它还包括了用于处理字符串的 `string` 以及用于结束程序的 `cstdlib` 库。

在 `main` 函数中，声明了一个名为 `customStack` 的整数类型栈。此栈将用于存储和管理整数元素。变量 `choice` 和 `element` 分别用于存储用户的菜单选择和将添加到栈中的整数元素。

使用 `while(true)` 结构确保程序进入一个无限循环，直到用户明确指示停止。在循环中，向用户显示一个栈操作菜单，每个操作都有一个数字选项。

栈的应用

1. 中缀转后缀表达式

在计算机科学和编程中，栈经常用于将中缀表达式转换为后缀表达式。由于中缀表达式中的运算符插入在操作数之间，因此计算机可能难以有效计算它们。通过将这些表达式转换为后缀（有时称为逆波兰表示法 RPN）可以简化求值过程。栈对于这种转换至关重要。在转换过程中，运算符被压入栈中，并且当遇到更高优先级的运算符时，会从栈中弹出并添加到输出中，从而确保正确的求值顺序。

结果的后缀表达式是许多应用程序（包括计算器、编译器和电子表格软件）的首选格式，这些应用程序需要高效的表达式求值。可以使用栈或其他数据结构快速对其进行求值。

2. 表达式解析/求值

在 C++ 等编程语言中，栈经常用于表达式解析和求值。为了将中缀表达式（即运算符插入在操作数之间，例如“3 + 5”）转换为更易于求值的后缀或前缀形式，在表达式解析中使用栈。栈对于根据运算符的优先级和结合性在求值过程中处理运算符和操作数至关重要。它确保表达式根据数学规则被准确求值。当用户在计算器程序、电子表格应用程序和数学计算工具中输入中缀表示法的方程时，此应用程序至关重要，因为栈驱动的解析和求值过程可提供准确的结果。

3. 树的遍历

树的遍历，例如中序、前序和后序遍历，是访问和处理树结构（尤其是二叉树）中数据的一种基本策略。在二叉搜索树 (BST) 中，二叉树遍历被广泛使用，BST 通常用于数据存储和检索。在 BST 中，元素按升序访问，这对于查找数据集中最小或最大元素等任务非常有用。前序遍历对于创建树的副本很有用，因为它确保在处理子节点之前处理父节点。后序遍历（常用于内存管理和资源释放）中，在释放父节点之前释放子节点。除了 BST，树遍历是从表达式解析到分层数据处理的许多算法和数据结构的关键工具，用于有效处理分层数据。

4. 排序算法

计算机科学中的排序算法至关重要，并且在各种领域都有多种用途。它们用于按特定顺序排列数据，从而实现高效的数据检索、搜索和分析。排序在数据库和信息检索等领域起着关键作用，以最大限度地提高搜索操作。为了查找数据中的模式和趋势，排序对于数据挖掘和机器学习活动的准备工作至关重要。排序是软件开发中用于管理图形用户界面中的项目列表、改进搜索引擎以及确保有效的数据存储和检索的一种技术。此外，计算几何和算法问题解决方法都依赖于排序。

5. 汉诺塔

多年来，数学家和计算机科学家一直对汉诺塔谜题着迷。它有三根杆和一系列圆盘，最初按递减大小顺序放置在一根杆上。一次只能移动一个圆盘，并且较大的圆盘不得叠放在较小的圆盘之上。目标是在遵循规则的情况下，将整个叠子移动到另一根杆上。这款游戏看似简单，却隐藏着算法开发和计算机科学的重要意义。该问题可以分解为更小、相同的子问题，使其成为教授和理解递归的绝佳示例。汉诺塔同样凸显了有效算法设计的重要性，因为要获得更多圆盘的最佳解决方案，需要仔细的计算和优化。它在实践中被用于优化计算系统中的磁盘存储和数据传输，并作为算法研究中的一个基本问题。

结论

总之，C++ 中的栈函数提供了一种基本的数据结构，用于后进先出 (LIFO) 的数据管理。它们是编程中的一项基本工具，因为它们对于多种应用至关重要，例如函数调用管理、表达式解析和解决汉诺塔等复杂问题。