道格·勞埃德：所以如果你 看著堆棧的視頻， 這大概會感覺 像似曾相識的一點點。 這將非常相似的概念， 剛上有一個輕微的扭曲。 我們現在要談的隊列。 這樣一個隊列，類似於一個棧， 是另一種數據結構的 我們可以用它來保持 有組織地數據。 類似於一個堆棧， 它可以實現 作為陣列或鍊錶。 不像堆疊時，規則 我們用它來確定 當事情被添加或者刪除 隊列中有一點點不同。 不像堆棧，它 為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。