栈在数据结构中的应用

栈是后进先出 (LIFO) 的数据结构。这种数据结构在不同方面有一些重要的应用，如下所示：

• 表达式处理：

  • 中缀表达式转后缀表达式或中缀表达式转前缀表达式：

    栈可以用于将某些中缀表达式转换为其等效的后缀表达式或前缀表达式。这些后缀或前缀表示法用于计算机表达某些表达式。这些表达式与中缀表达式不太熟悉，但它们也有一些很大的优势。我们不需要维护运算符顺序和括号。

  • 后缀表达式或前缀表达式的求值：

    转换为前缀或后缀表示法后，我们需要计算表达式以获得结果。为此，我们也需要栈数据结构的帮助。

• 回溯过程：

  回溯是算法设计技术之一。为此，我们深入研究某种方法，如果该方法效率不高，我们会回到之前的状态，并尝试其他路径。要从当前状态返回，我们需要存储先前状态。为此，我们需要栈。回溯的一些例子包括寻找骑士巡游问题或 N 皇后问题的解等。

• 栈的另一个重要用途是在函数调用和返回过程中。当我们从另一个函数调用一个函数时，该函数调用语句可能不是第一个语句。调用函数后，我们还必须从函数区域返回到我们离开控制的地方。因此，我们希望恢复我们的任务，而不是重新启动。为此，我们将程序计数器的地址存储到栈中，然后转到函数体执行它。执行完成后，它从栈中弹出地址并将其分配给程序计数器以再次恢复任务。

Arnab Chakraborty

更新于：2019年8月27日

3K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习