什么是栈？在C++中它们有什么用途？

Question

我一直在用这本书《实用C++编程》复习C++，然后发现了一个叫做“栈”的东西。在书中的定义是，它是一种存储数据的算法。

从我在书中看到的内容来看，它看起来很像汇编语言……我还记得读过某个关于16位的东西。

所以我的问题是：栈有什么用途？它们仍然有用吗？或者说它们是一种旧的方法，可以通过32/64位计算机更简单、更高效地完成？我真的很困惑栈的作用是什么。

---

编辑：由于我的问题太模糊了，我会重新表述一下……什么是栈，什么时候应该使用它。

- Gabriel

---

这是一种数据结构，而不是算法。 - user142019

这与16/32/64位无关，当你需要某种数据结构时，不管你有多少位，你都需要它。 - PlasmaHH

为什么这个帖子会被踩得这么惨？ - Gabriel

可能是因为当程序员声称不知道什么是栈时，每个人都认为这是在耍流氓。 - chrisaycock

@Gabe：下投票按钮还提到“没有展示任何研究努力”，这可能是另一个原因。 - Sebastian Mach

Answer 1

堆栈不是一种方法，而是一种数据结构，它遵循后进先出（LIFO）的原则。

在 C++ 中，std::stack<> 是一个类模板，它的数据可以是任何类型。许多情况下，后进先出正是你所需要的。

例如，虚拟机或解释器就利用堆栈架构来保存函数/过程执行期间的运行状态。考虑以下语言解释器的例子，其中子过程可能不会更改调用者的状态：

std::stack<RunState> state;
Instruction i = fetch();

switch (i.type()) {
case Instruction.Call:
    state.push (state.top());
    break;
case Instruction.Return:
    state.pop();
    break;
...
}

维基百科有更多关于堆栈数据结构的应用示例。一些排序问题可以使用堆栈相对容易地解决。

与所有数据结构一样，C++拥有相当多的数据结构（列表、队列、集合、映射（又称关联数组，字典）、数组/向量等等），也许你现在甚至两年后都不需要它们，但你应该了解它们、它们的属性、优劣势以及何时使用它们是正确的时刻。

- Sebastian Mach

Answer 2

取决于你所谈论的栈是哪种。

首先，它是内存中的一个存储位置。

栈是一种后进先出的数据结构，无论是16/32/64位计算机，它仍然非常有用。

正如其他人所说，调用栈（或“栈”）是栈在操作的一个例子。

- Justin Niessner

---

调用栈也是一种先进后出的堆栈，因此它并不是一种不同类型的堆栈 - 它只是堆栈的一个例子。 - sepp2k

我可能有点刻薄，但是一个声称有C语言经验的近10万贡献者应该知道“内存栈”是栈的一种应用。 - Sebastian Mach

@phresnel - 我同意。我认为这个回答措辞非常不好，试图表明OP可能正在阅读有关数据结构本身或其应用的内容。因此需要重新措辞。对于造成的困惑，我感到抱歉。 - Justin Niessner

@JustinNiessner：但也许我太过分了。也许你只是想要一个关于调用栈或堆栈数据结构的解释。如果我冒犯了你，对不起。 - Sebastian Mach

Answer 3

说白了，当你需要以LIFO（后进先出）的方式存储数据时，它们就会派上用场。你可以在这里找到信息。（链接）。 使用16/32/64或任何位架构与堆栈的原理无关。

- Alexandre Hamez

Answer 4

如果需要符合标准的后进先出逻辑，可以使用堆栈。有很多问题需要遵循后进先出的逻辑。

- AlexTheo