DOUG LLOYD：好吧， 所以通过这点你 可能很熟悉 数组和链表 这是两个主要 我们已经数据结构 谈到保持套 类似的数据类型的数据组织的。 现在我们要谈 约上几个变化 对数组和链表。 在这个视频中，我们要去 谈栈。 具体来说，我们要谈 有关的数据结构称为堆叠。 从前面的讨论召回 关于指针和内存， 堆栈也是 命名为的存储器段 其中，静态声明 memory--内存，你 名称，命名变量，等 等等和功能框架，我们也 调用堆栈帧的存在。 所以这是一个堆栈数据结构 记忆不是一个堆栈段。 好。 

但什么是栈？ 所以这是非常简单，只是一个 特殊的结构 在一个有组织的方式保持数据。 而且还有两个很 常见的方式来实现 栈使用两个数据结构 我们已经很熟悉了， 数组和链表。 是什么让一个堆栈特别是 以何种方式，我们把信息 入堆栈，这样我们的方式 请从堆栈信息。 尤其是对于栈 规则是只有最 最近添加的元素可以被删除。 

这样想来，好像它是一个堆栈。 我们正在打桩信息 其本身上， 只有东西在顶部 桩的可以去掉。 我们不能下删除的东西 因为一切会 折叠和翻倒。 所以，我们真的正在建设一个栈 然后，我们必须逐件除去件。 正因为如此，我们通常所指 到堆栈作为LIFO结构， 后进先出。 后进先出法，后进先出。 

所以这个限制的，因为 信息如何可以被添加到 而从堆栈中删除，没什么 只有两件事情，我们可以用堆栈来。 我们可以推动，这是 我们长期使用的添加 一个新元素的顶部 叠，或者如果栈不存在 我们正在从头开始创建它， 创建堆栈摆在首位 将推动。 然后弹出，这是CS的那种 长期我们用它来删除最近 从堆栈的顶部添加元素。 

因此，我们要看看这两个 实现，无论是基于阵列的 和链表为主。 而且我们要 开始的数组。 因此，这里的基本想法是什么 在基于阵列的堆栈数据结构 会是什么样子。 我们在这里有一个类型的定义。 里面的，我们有两个成员 结构或字段。 我们有一个数组。 又一次我使用的 任意数据类型的值。 

因此，这可以是任何类型的数据， INT char或其他一些数据 你以前创建的类型。 因此，我们有大小容量的阵列。 容量正在一斤定义的常量， 也许别人在我们的文件的地方。 因此，与这个特定的已通知 实现我们的边界 自己作为是典型的 数组的情况下， 这是我们无法动态调整， 那里有一定数量 最大元素 我们可以把我们的堆栈。 在这种情况下，它的电容元件。 

我们也跟踪 堆栈的顶部。 什么元素最重要的是 最近添加到栈？ 因此，我们持续跟踪 在一个变量被称为顶端。 而所有这一切都被包裹起来 成称为栈一个新的数据类型。 而一旦我们创建 这个新的数据类型 我们可以把它像 任何其它数据类型。 我们可以声明堆栈S，就像 我们可以做INT x或字符年。 而当我们说堆栈 S，以及会发生什么 是我们得到了一组 内存预留了我们。 

在这种情况下，容量 我显然决定 是10，因为我有一个 型堆的单可变 其中包含两个字段回忆。 的阵列，在这种情况下，会 是一个整数数组 因为在我的大部分例子的情况。 而另一位整型变量 能够存储的顶部， 最近添加 元件到堆栈中。 因此，一个单一的堆栈我们 刚刚定义看起来像这样。 它包含一个盒子 的10的阵列什么 将在这种情况下，整数和 在绿色的另一个整型变量有 以指示堆栈的顶部。 

要设置的顶部 堆栈，我们只是说s.top。 这就是我们访问 场的结构召回。 s.top有效等于0 这样做是为了我们的堆栈。 所以，再一次，我们有两个操作 我们现在可以执行。 我们可以把我们可以弹出。 让我们先从推动。 再次，推是添加了新的 元素添加到堆栈的顶部。 

那么，我们需要做的 这种基于阵列的实现？ 那么一般 推送功能会 到需要接受 指针到堆栈。 现在，花一秒钟想想。 为什么我们要接受 指针堆栈？ 从以往的视频回忆 变量的作用域和指针， 如果我们只是派会发生什么 堆栈，S而作为一个参数？ 但实际在那里被传递？ 请记住，我们正在创建一个副本 当我们把它传递给函数 除非我们使用指针。 所以这个功能推动需求 以接受的指针堆栈 让我们实际上改变 堆栈，我们打算改变。 

另一件事推可能要 接受的类型值的数据元素。 在这种情况下，再次，一个整数， 我们要添加到堆栈的顶部。 因此，我们有我们的两个参数。 什么是我们要 现在做俯卧撑里面？ 好了，简单地说，我们只是要添加 该元素到堆栈的顶部 然后更改的，其中的顶部 堆栈，使得S点顶部的值。 因此，这是一个函数 声明推 可能看起来像在 基于数组的实现。 

同样，这不是一个硬性规定 你可以改变这一点，有 它以不同的方式而变化。 也许s的全局声明。 所以你甚至不需要 通过它是作为一个参数。 这又是只是一个 一般情况下推动。 也有不同 的方式来实现它。 但在这种情况下，我们 推是要采取 两个参数，一个指向一个堆栈和 类型值，整数的数据元素 在这种情况下。 

因此，我们宣布S，我们 说s.top等于0。 现在让我们来推 28号到堆栈中。 那么这是什么意思？ 那么目前 栈顶部是0。 所以，什么是基本 事情发生是 我们要坚持数 28到数组的位置0。 很简单，对了，那 是顶部，现在我们是好去。 然后，我们需要改变什么 堆栈的顶部会。 因此，下一次 我们推入一个元素， 我们将其存储在 阵列位置，可能不是0。 我们不希望覆盖 我们刚才放在那里。 所以我们只将顶到1。 这可能是有道理的。 

现在，如果我们想要把另一个元素 压入堆栈，说我们要推33， 现在好了，我们只是将采取33 并把它在数组位置数 1，然后更改的顶部我们 堆栈是数组位置排名第二。 因此，如果在下一次我们要 推一个元素入栈中， 它会被放在数组位置2。 而让我们做一个更多的时间。 我们将推动19关栈。 我们将投入19阵列的位置2 和改变我们的堆栈的顶部 要阵列的位置3 所以如果下一次我们 需要做一个推，我们是好去。 

OK，所以这是推动概括地说。 什么大跌眼镜？ 所以大跌眼镜的是排序 对口推。 这是我们如何从堆栈中删除数据。 而在一般流行音乐的需求 做到以下几点。 它需要接受的指针 叠，再在一般情况下。 在其他一些情况下，你可能 已宣布在全球范围堆栈， 在这种情况下，你不需要将它传递 在因为它已经访问了它 作为全局变量。 但随后还有什么需要我们做什么？ 嗯，我们都递增 叠推的顶部， 所以我们可能会想 递减堆栈的顶部 在流行音乐，对不对？ 然后当然 我们也将要 回到我们删除值。 如果我们要添加的元素，我们希望 得到的元素出来以后， 我们可能实际上 要存储他们，所以我们 不只是从删除 堆栈中，然后什么也不做他们。 一般来说，如果我们 推和弹出在这里 我们要存储此 以有意义的方式信息 因此它不会使 感觉只是丢弃它。 所以这个功能应该 可能返回一个值给我们。 

因此，这是一个多么声明流行 可能看起来像有在左上角。 该函数返回 类型值的数据。 我们再次使用已经 整数贯穿始终。 和它接受一个指向一个堆栈 其唯一的参数或唯一的参数。 那么，什么是流行音乐该怎么办？ 比方说，我们希望现在 流行元素断号第 所以请记住我说的堆栈是最后一个 先出，后进先出的数据结构。 该元件是要 从栈中删除？ 你猜19？ 因为你是对的。 19是我们加入的最后一个元素 当我们在推动元件堆叠， 所以它会第一 元素被删除。 这是因为如果我们说28，和 然后我们把33在它的上面， 我们把19最重要的是。 我们可以脱下唯一的元素是19。 

现在，这里的图中我做了什么 是那种从阵列中删除19。 这实际上不是 我们要做的。 我们只是来样 中假装它不存在。 它仍然存在于 该内存位置， 但我们只是要忽略它 通过改变我们的堆栈的顶部 从为3至2。 所以，如果我们现在推 另一元件压入堆栈， 它会在写19。 

但是，我们不要经历的麻烦 中删除19从堆栈中。 我们可以假装它不存在。 为了堆栈就不见了，如果 我们改变顶端是2而不是3。 好了，所以这是相当多了。 这就是我们需要做的 流行元素了。 让我们再来一次。 所以，我已经强调了它在红色这里 表明我们正在做另一个电话。 我们将做同样的事情。 

那么，什么会发生？ 好了，我们要保存 33 x和我们要去 到堆栈的顶部改变到1。 所以，如果我们现在推的 元素进栈，我们是 要做的事情，现在， 什么会发生 是我们要覆盖 阵列位置号码1。 所以这33类中所剩下的 后面，我们只是假装 不存在了，我们只是 要破坏它，并把40同去。 然后，当然， 因为我们做了一个推， 我们要递增 栈顶部1〜2 这样，如果我们现在添加 另一种元素，它会 进入阵列的位置排名第二。 

现在链表是另一种 方法来实现堆栈。 而如果在这个定义 屏幕这里看起来很熟悉你， 这是因为它看起来几乎 完全相同的，事实上， 它几乎是完全 同一个单向链表， 如果你从我们的讨论召回 在另一个视频单链表。 这里的唯一限制 对我们来说是程序员， 我们不允许 插入或删除随机 从单向链表 这是我们可以做以前。 只是现在我们可以插入和删除从 前面或的连接的顶端 名单。 这真的是唯一的 区别不过。 这是否则单链表。 这是唯一的限制 替换上自己 作为程序员 改变成一个堆栈。 

这里的规则是始终保持 指针的一个链表的头部。 当然，这是一个通常 第一个重要的规则。 对于单向链表，反正你 只需要一个指向头部 为了有 链能够参考 至所有其他元素 在链表。 但它是特别 重要用栈。 所以一般你 要真正想要的 这个指针是一个全局变量。 它可能会 可以更容易的方式。 那么什么是push和pop的类似物？ 对。 所以推再次增加 一个新的元素到堆栈。 在一个链表 意味着我们将有 创建一个新的节点，我们是 将添加入链表， 然后按照谨慎的步骤 我们先前已经介绍 在单链表将其添加到 不破坏链的链 和丢失或成为孤儿的任何 链表元素。 而这基本上是什么 文本的小斑点有总结。 让我们一起来看看 它作为一个图。 

因此，这里是我们的链表。 它同时包含四个要素。 而更加完美地在这里是我们的 堆栈包含四个元素。 而且，我们说，我们现在要 推新项目到这个堆栈中。 我们要推新 其数据的价值产品12。 那么我们怎么办呢？ 那么首先我们要 malloc的空间，动态 分配空间用于新的节点。 当然，紧接着又 我们打​​电话到我们的malloc始终 一定要检查空， 因为如果我们得到了空回 有某种问题。 我们不希望取消引用的空 指针，否则就惨了赛格故障。 这不好。 因此，我们已经malloced节点。 我们假设，我们已经在这里取得了成功。 我们打​​算把12进 该节点的数据字段。 现在，你还记得，我们的指针 移动下一个，所以我们不打破链？ 我们有几个选项，在这里，但 是唯一一个将是安全的 是集新闻下一指针 指向老首长名单 或者是不久将成为 老首长的名单。 而现在，我们所有的 元素链接在一起， 我们只要将名单指向 那个新不一样的地方。 现在我们已经有效地推了 新元件压入堆栈的前面。 

要跳出我们只是想 删除第一个元素。 所以基本上是什么 我们要在这里做， 同时，我们必须找到第二个元素。 最终，这将成为新的 头后，我们删除了第一个。 所以，我们只需要从开始 开始的时候，移动一个前锋。 一旦我们已经有了一个保持在一个 在那里，我们期待目前 是我们可以安全地删除第一个 然后我们就可以将头 指向究竟是什么 第二项，然后现 是之后，第一 节点已被删除。 

如此反复，考虑看看 它作为一个图，我们 希望现在流行的 元素关闭该堆栈。 那么我们该怎么办？ 那么我们首先要创建 一个新的指针是怎么回事 为指向相同的位置为头。 我们要移动一个位置 向前说TRAV等号 TRAV接下来为例，它 将推进TRAV指针1 位置前移。 现在，我们已经有了一个 保持第一元件上 通过该指针叫列表，以及 通过指针称为第二元件 TRAV，我们可以安全地删除 从栈第一元件 不失休息 链，因为我们 有办法参考 到第二元件 由前进的道路 指针称为TRAV。 

所以，现在我们可以免费在该节点。 我们可以免费列表。 然后将所有我们现在需要做的是 移动列表指向同一个地方 这TRAV做，而且我们的排序回 我们开始的地方，我们推12日前 在第一地点，合适。 这正是我们在那里。 我们有这四款元素堆栈。 我们增加了五分之一。 我们推第五 元素，然后我们 杀出，以最近 加元回退。 

这真是非常 所有有栈。 您可以实施他们作为阵列。 您可以执行这些链表。 还有，当然，其他 方法来实现它们。 基本上，我们将使用的原因 栈是维持在这样的方式的数据 该最近添加 元素是我们的第一件事情 会想回去。 我是道格·劳埃德，这是CS50。