13

我想知道为什么我们使用术语“push”和“pop”来添加/删除堆栈中的项目？是否有一些物理隐喻导致这些术语很常见？

我唯一的建议是类似于手枪的弹簧弹匣，子弹被“推”入其中并可以“弹出”出来，但这似乎不太可能。

第二个堆栈琐事问题：为什么大多数 CPU 将调用堆栈实现为在内存中向下增长，而不是向上增长？

4

11 回答 11

22

对于第二个问题，维基百科有一篇关于控制堆栈的 CS 哲学的文章：

http://en.wikipedia.org/wiki/LIFO

首先，也在维基百科上：

一个常用的比喻是弹簧加载的自助餐厅堆栈中的一堆盘子的想法。在这样的堆叠中，只有顶板对用户可见和可访问，所有其他板保持隐藏。随着新盘子的添加，每个新盘子都成为堆叠的顶部，将每个盘子隐藏在下面，将盘子堆向下推。当顶板从堆叠中移除时，可以使用它们，板弹回，第二个板成为堆叠的顶部。这个比喻说明了两个重要原则：后进先出原则是一个；第二个是堆栈的内容是隐藏的。只有顶板是可见的，所以要查看第三块板上的内容，必须移除第一块和第二块板。这也可以写成FILO-First In Last Out，即

于 2009-01-07T13:39:36.557 回答
13

我相信弹簧加载的板叠是正确的，作为术语 PUSH 和 POP 的来源。

特别是，麻省理工学院的东校区公共食堂在 1957 年至 1967 年的时间范围内装有弹簧加载的盘子。Tech Model Railroad Club 会使用 PUSH 和 POP 这两个术语。我想这就是起源。

Tech Model Railroad Club 无疑影响了 Digital Equipment Corporation (DEC) PDP-6 的设计。PDP-6 是最早在硬件中具有面向堆栈指令的机器之一。指令是 PUSH、POP、PUSHJ、POPJ。

http://ed-thelen.org/comp-hist/pdp-6.html#Special%20Features

于 2009-01-07T13:49:58.767 回答
13

对于第二个问题：小型系统上的汇编程序程序员倾向于编写从内存中的低地址开始的代码，并随着更多代码的添加而增长到更高的地址。

正因为如此，使堆栈向下增长允许您在物理内存的顶部启动堆栈，并允许两个内存区域相互增长。这简化了这种琐碎环境中的内存管理。

即使在具有隔离 ROM/RAM 固定数据分配的系统中，也最容易自下而上构建，从而替换上述说明的代码部分。

虽然这种琐碎的内存方案已经很少见了，但硬件实践仍在继续。

于 2009-01-07T14:11:19.987 回答
6

把它想象成一个 pez 分配器。你可以在上面推一个新的。然后从顶部弹出它。

当我想到 push 和 pop 时，我总是这么想。（虽然可能不是很有历史意义）

你在问自己 PEZ 到底是什么？ 见评论。

于 2009-01-07T13:37:58.057 回答
6

关于您的“第二个微不足道的问题”：我在定义“向上”和“向下”的含义时看到了相当大的不一致！从早期开始，一些制造商和作者在页面顶部绘制低地址的内存图（大概模仿读取页面的顺序），而其他人将高地址放在页面顶部（大概模仿方格纸坐标或建筑物的楼层）。

当然，堆栈的概念（以及可寻址内存的概念）独立于这种视觉隐喻。可以实现一个在任一方向“增长”的堆栈。事实上，我经常看到下面的技巧（在裸机级实现中）用于在两个堆栈之间共享内存区域：

+---+---+--------   -------+--+--+--+
|   |   |   ->   ...   <-  |  |  |  |
+---+---+--------   -------+--+--+--+
^                                   ^
Stack 1      both stacks      Stack 2
base        "grow" toward        base
              the middle

所以我的回答是，从概念上讲，堆栈永远不会“向下”或“向上”增长，而只是从它们的基础增长。单个堆栈可以在任一方向上实现（或者在任何方向上都可以实现，如果它使用带有垃圾收集的链接表示，在这种情况下，元素可能位于节点空间中的任何位置）。

于 2009-01-07T14:00:19.167 回答
5

头韵总是很有吸引力（看看我在那里做了什么？），这些词很短，头韵，暗示性。旧的 BASIC 命令 peek 和 poke 也是如此，它们具有并行 k 的额外优势。

一个常见的物理隐喻是自助餐厅的盘子分配器，其中弹簧加载的盘子堆叠使您可以从顶部取出一个盘子，但下一个盘子会上升到相同的位置。

于 2009-01-07T13:38:37.883 回答
2

此页面上的答案几乎可以回答堆栈方向问题。如果我必须总结一下，我会说它是向下完成的，以保持与古代计算机的一致。

于 2009-01-07T13:40:06.370 回答
0

我认为最初的故事是因为一些开发人员看到了盘子堆（就像你经常在自助餐厅看到的那样）。你把一个新盘子推到堆栈的顶部，你也从顶部弹出一个。

于 2009-01-07T13:41:05.150 回答
0

至于在内存中向下增长的堆栈，请记住，在处理分层数据结构（树）时，大多数程序员都乐于在页面顶部绘制一个底部（或树干）的页面......

于 2009-01-07T14:00:26.547 回答
0

我知道这个线程真的很老，但我对第二个问题有一个想法：

在我看来，堆栈会增长，即使内存地址会减少。如果你要在一张纸上写一大堆数字，你会从左上角开始，从 0 开始。然后你会从左到右增加数字，然后从上到下。所以说堆栈是这样的：

000 001 002 003 004 000 001 002 003 004 000 001 002 003 004
005 006 007 008 009 005 006 007 008 009 005 006 007 008 009 
010 011 012 013 014 010 011 012 013 014      010 011 012 013 014 
015 016 017 018 019 015 016 017 018 019 015 016 017 018 019 
020 021 022 023 024 020 021 022 023 024 020 021 022 023 024
025 026 027 028 029 025 026 027 028 029 025 026 027 028 029

其中粗体数字表示堆栈内存，非粗体数字表示堆栈未使用的内存地址。每个相同编号的块代表调用堆栈增长的程序的一个阶段。

即使内存地址向下移动，堆栈也在向上增长。

同样，对于弹簧加载的板堆，
如果您从堆的顶部取下一个板，您会称其为第一个板（最小的数字），对吗？甚至认为它是最高的。程序员甚至可以称它为第零板。

于 2009-09-11T06:44:49.877 回答
0

对于堆栈为什么会变小的问题，我想它是用来节省内存的。

如果您从堆栈内存的顶部（最高值地址）开始并工作到零，我认为检查您是否已到达地址$0x00000000比分配一个变量来为您提供堆栈的最大高度并检查是否更容易不是你已经到达那个地址。

我认为这可以更容易地检查您是否到达可寻址空间的末尾，因为无论有多少可用内存，堆栈的限制总是$0x00000000.

于 2012-04-14T16:29:26.107 回答