道格·劳埃德：所以如果你 看着堆栈的视频， 这大概会感觉 像似曾相识的一点点。 这将非常相似的概念， 刚上有一个轻微的扭曲。 我们现在要谈的队列。 这样一个队列，类似于一个栈， 是另一种数据结构的 我们可以用它来保持 有组织地数据。 类似于一个堆栈， 它可以实现 作为阵列或链表。 不像堆叠时，规则 我们用它来确定 当事情被添加或者删除 队列中有一点点不同。 不像堆栈，它 为LIFO结构， 后进先出，队列是FIFO 结构，FIFO，先入先出。 现在排队，你可能 有一个比喻队列。 如果你在曾经在行 游乐园或在银行， 有一个排序的公平 实施结构。 行中的第一人，在 银行是第一人 谁得到发言的出纳员。 

这将是形式的比赛 至底部，如果唯一的方式 你有发言的出纳员 银行是成为最后一个人在网上。 每个人总是希望 成为最后一个人在网上， 而该人谁在那里第一次 谁一直在等待了一段时间， 可能是那里几个小时， 和小时，和小时 他们有机会真正前 提取任何款项在银行。 所以队列排序 公平实现结构。 但是，这并不一定意味着 该协议栈是一件坏事，只是 该队列是另一种方式来做到这一点。 如此反复队列是先入先 出来，对一叠这持续的， 先出。 类似于一个堆栈， 我们有两个操作 我们可以在队列表演。 的名称是排队，这是添加 一个新元素添加到队列的末尾， 和出队，这是 以除去最老的 元件从队列的前部。 因此，我们要添加的元素 到队列的末尾， 而且我们要删除元素 从队列的前部。 再次，与堆栈，我们加入 元素添加到堆栈的顶部 和删除元素 从堆栈的顶部。 因此，与排队，它增加了 结束时，从正面除去。 因此，有最古老的东西 永远是未来的事情 出来，如果​​我们试图 和出列的东西。 

如此反复，与队列，我们​​可以 基于阵列的实现 和链表基于实现。 我们将与重新开始 基于阵列的实现。 该结构定义 看起来很相似。 我们有另一个数组 数据类型值的出现， 因此它可以容纳任意类型的数据。 我们再次将使用 整数在本实施例。 

就如同我们 基于阵列的堆栈实现， 因为我们使用的 阵列，我们一定 有一个限制，即C类 的实施对我们来说，这是我们 没有在任何活力我们的 能力增长和收缩的阵列。 我们必须决定在开始 什么是物联网的最大数量 我们可以把这个 队列，并且在这种情况下， 容量为一些英镑 定义我们的代码不变。 并为这个目的 视频，容量将是10。 

我们需要保持跟踪 队列的前面 所以我们知道哪些元素 我们要出列， 而且我们也需要保持跟踪 东西else--元件的数目 我们已经在我们的队列中。 请注意，我们不是在跟踪 队列的末尾的，只是 队列的大小。 而其中的原因将有希望 成为一时有点清晰。 一旦我们完成了 这种类型的定义， 我们有一个新的数据类型 所谓的队列，现在我们可以 声明的数据类型的变量。 而且有点混乱，我决定 调用此队列Q，信 的q代替数据键入q。 

因此，这里就是我们的队列。 它是一个结构。 它包含三个成员，三 字段大小的容纳的阵列。 在这种情况下，容量为10。 而这个数组 将要举办的整数。 在绿色环保是我们的队列前面的 要移除下一个元素，并以红色 将是队列的大小， 多少个元素是目前 现有在队列中。 所以，如果我们说q.front平等 0，和q.size大小等于0-- 我们把0到这些领域。 而在这一点上，我们是非常 准备开始我们的队列中的工作。 

因此，第一个操作，我们可以 执行是要排队的东西， 一个新的元素添加到 的队列的末尾。 那么我们怎么需要 这样做在一般情况下？ 那么这个功能需要排队 以接受的指针我们的队列。 同样，如果我们宣布 我们在全球范围的队列， 我们不会需要做到这一点 必需的，但在一般情况下，我们 需要接受指针 到数据结构 像这样，否则， 我们经过value--我们 传入队列的副本， 所以我们实际上并没有改变 我们打​​算改变队列。 

它需要做的另一件事是接受 适当类型的数据元素。 再次，在这种情况下，它的 将是整数， 但你可以随意 声明数据类型值 和使用这种更普遍。 这就是我们要排队的元素， 我们要添加到所述队列的末端。 然后，我们其实想 放置该数据队列中。 在这种情况下，将其放置在 我们的数组的正确位置， 然后我们要改变大小 队列中，有多少我们的元素 目前拥有。 

所以，让我们开始吧。 这是，同样，这一般 表函数声明 什么排队可能看起来像。 现在我们开始。 让我们排队数 28到队列。 那么，我们该怎么办？ 好了，我们的队列的前面 在0，而我们的队列的大小 为0，所以我们可能要放 数28在数组编号 0，对不对？ 所以，我们现在已经摆在那里。 所以，现在我们需要什么改变？ 我们不希望改变 在队列的前面， 因为我们想知道哪些因素 我们可能需要在以后出列。 因此，我们之所以有前面有 是那种什么是指标 最古老的东西到数组中。 那么最古老的东西在array--中 事实上，在数组中的唯一正确的 now--是28，这是 在数组位置0。 因此，我们不希望 改变这种绿色的数量， 因为这是最古老的元素。 相反，我们要改变大小。 因此，在这种情况下，我们将 增量大小设置为1。 

那里的想法，现在一般的排序 下一个元素是要去一个队列 是添加这两个数字 一起，前部和大小， 并会告诉你在哪里下 在队列元件是要去​​。 所以，现在让我们来排队另一个号码。 让我们排队33。 所以33是要进入 阵列位置0加1。 所以在这种情况下，它将会 进入阵列的位置1， 现在我们队列的大小为2。 

同样，我们不会改变 我们的队列的前面， 因为28仍是 最古老的元素，我们 希望用于：当我们最终得到 要出列，删除元素 从这个队列中，我们想知道 其中最古老的元素。 因此，我们总是需要保持 那里的一些指标。 所以这是0就是那里。 这就是前面就是那里。 

让我们在排队一个更多元，19。 我敢肯定，你能猜到 其中，19是要去。 它打算进入 阵列位置号码2。 这就是0加2。 而现在我们的队列的大小为3。 我们在这3个元素。 所以，如果我们要和我们不会 到现在，排队的另一个元素， 它将进入阵列的位置 号3，和我们的队列的大小 将是4。 所以，我们现在已经入队的几个要素。 现在，让我们开始将其删除。 让我们从队列中出列他们。 

因此，类似的流行，这是排序 这个模拟为堆栈， 出队需要接受 指针queue--再次， 除非它的全局声明。 现在我们要改变位置 在队列前面的。 这有点从何而来 发挥作用，这一方面的变量， 因为一旦我们删除 一个元素，我们希望 将其移动到下一个最古老的元素。 

然后，我们要减少 的队列的大小， 然后我们要返回的值 被从队列中删除。 同样，我们不希望只是将其丢弃。 我们大概是提取 从我们的queue-- 出列，因为我们关心它。 因此，我们希望这个函数返回 型值的数据元素。 再次，在这种情况下，值是整数。 

所以，现在，让我们出列的东西。 让我们从队列中删除的元素。 如果说INT x等于＆Q，符号q-- 再次，这是一个指针，这个Q数据 结构 - 哪些因素 将被出列？ 在这种情况下，因为它是一个第一 入先出的数据结构，FIFO 我们把这个第一件事 队列为28，因此在这种情况下， 我们要采取28出 队列中，不19，这是什么 我们会做，如果这是一个堆栈。 我们将采取28个队列。 

类似于我们用做 堆栈，我们实际上没有 要删除28 从队列本身 我们只是来样 中假装它不存在。 因此，它会呆在那里 在内存中，但我们只是 要通过移动那种忽略它 我们的Q数据的其他两个场 结构体。 我们要改变前。 Q.front现在要 是1，因为这是现 我们有最古老的元素我们 队列，因为我们已经删除28， 这是以前最古老的元素。 

而现在，我们要改变 队列的大小 至两个元素，而不是三个。 早前现在还记得我说过，当我们 要元素添加到队列中， 我们把它放在一个数组位置 这是前部和大小的总和。 因此，在这种情况下，我们仍然把 它，在队列中的下一个元素， 进入阵列的位置3，和 我们会看到，在一秒钟。 

所以，我们现在已经离队了 从队列中第一个元素。 让我们再来一次。 让我们删除其它 元件从队列。 在该情况下，当前最旧的 元素是数组位置1。 这就是q.front告诉我们。 这个绿色的盒子告诉我们， 这是最古老的元素。 因此，x将成为33。 那种我们会就忘 该33存在于数组中， 我们将现在的说， 队列中的新的最古老的元素 是在阵列的位置2，并且大小 元素的队列，数 我们已经在队列，是1​​。 现在，让我们排队的东西，和我 那种一秒钟前给送人了， 但是如果我们想要把40进 队列，哪来的40要去？ 好了，我们已经把它 在q.front加队列的大小， 因此它是有道理的 居然把40在这里。 现在请注意，在 某些时候，我们要去 去的端 我们阵问：里面， 但淡出28和33-- 它们实际上是在技术上 开放的空间，对不对？ 因此，我们可以eventually-- 加入该规则 这两个together--我们最终可能 需要通过MOD容量的大小 所以我们可以环绕。 

因此，如果我们得到的元素 10号，如果我们 取代它的单元号10，我们最好 其实把它放在数组位置0。 如果我们打算 阵列location--原谅我， 如果我们加入他们在一起， 我们得到了一些 11人是在这里，我们将不得不把 它，这并不在此array--存在 它会去出界。 我们可以通过10 MOD和放 它在阵列位置1。 所以这是如何工作的队列。 他们总是会从左边走 向右并可能环绕。 你知道，他们是 全尺寸的话，那红色的框， 变得等于容量。 而且我们添加40到打完 队列，还有什么我们需要做什么？ 那么，最古老的元素 在队列中仍然是19， 所以我们不希望改变 在队列的前面， 但现在我们有两个 在队列中的元素， 所以我们要增加 我们的规模从1到2。 

这几乎是它与 基于阵列的队列的工作， 和类似的堆叠， 还有一种方式 实现一个队列作为一个链表。 现在，如果该数据结构类型 看起来很熟悉你，那是。 这不是一个单向链表， 这是一个双向链表。 而现在，顺便说一句，这是 实际上可以实现 队列作为一个单向链表，但 我认为，在可视化方面， 它实际上可能有助于查看 这是一个双向链表。 但绝对是可能的 做到这一点作为一个单向链表。 

因此，让我们来看看 这是什么可能看起来像。 如果我们想enquue-- 所以现在，我们再次是 切换到一个连接表 在此基础的模式。 如果我们要排队，我们要 以添加新的元件，以及 我们需要什么做的？ 好吧，首先，由于 我们要添加到结束 从除去 开始，我们可能 要保持指针都 头和链表的尾部？ 尾部是另一个术语 链表的末尾， 在该链接的表的最后一个元素。 而这些大概会， 再次，是对我们有利 如果他们是全局变量。 但是现在，如果我们想添加一个新的 元素我们有什么做的？ 我们只是[？马拉克？]或动态 分配我们的新的节点，我们自己。 然后，就像当我们增加任何 元素双向链表我们， 只需要排序of-- 那些过去三年在这里步骤 只是所有关于移动 正确的方法指针 使得元件被添加到 不破坏链的链 或使某种错误 或有某种意外 发生由此我们意外 孤立我们的队列中的某些元素。 以下是这可能看起来像。 我们要添加的元素 10到该队列的末尾。 因此，这里最古老的元素 由头表示。 这是我们把第一件事情 到这里这个假设的队列。 和尾，13，是最 最近添加的元素。 所以，如果我们要排队10到 这个队列，我们​​希望13后把它。 所以，我们要动态地 分配空间用于新的节点 并检查空，以确保 我们没有内存故障。 然后，我们将 放置10到该节点， 现在我们必须要小心 我们如何组织指针 所以我们不打破链。 

我们可以设置10的先前场 指向回到老尾巴， 并且由于'10将是 在某些时候新的尾巴 由时间所有这些 链连接， 没有什么会来 10后现在。 所以10的下一个指针 将指向空， 然后当我们做到这一点，我们已经经过 连接10向后链， 我们可以采取的老脸，或借口 我，排队的老尾巴。 队列的旧端， 13，并使其指向10。 现在，在这一点上，我们有 入队的10号到这个队列中。 现在我们需要做的仅仅是移动 尾指向10，而不是到13。 

出队实际上是 非常相似的弹出 从一个堆栈的 实施为一个链接列表 如果你看过堆视频。 所有我们需要做的就是开始在 开始，找到第二个元素， 释放第一元件， 然后将头 为指向第二元件。 可能更好地进行可视化 只是要格外清楚的。 因此，这里又是我们的队列中。 12是最古老的元件 在我们的队列，头部。 10是最新的元件 在我们的队列中，我们的尾巴。 

所以，当我们要 出列的元素， 我们要删除的最古老的元素。 那么我们该怎么办？ 嗯，我们设置了遍历指针 即开始于头部， 我们移动它，使它 指向第二元件 这说TRAV queue--东西 等于TRAV箭头下，例如， 将移动TRAV有指向 15，其中，当我们出列12， 或之后我们删除12，将 成为当时最古老的元素。 

现在，我们已经有了一个保持在第一 通过指针head元素 和第二元件 通过指针TRAV。 我们现在可以免费的头，然后我们就可以 说没有一样是15前了。 因此，我们可以改变15以前 指针指向空， 我们只是将头以上。 还有，我们走了。 现在，我们已经成功地 出列12，现在我们 有4个元素另一个队列。 这几乎是所有 还有就是排队， 既基于阵列和链表为主。 我是道格·劳埃德。 这是CS 50。