[Powered by Google Translate] [第6條：不太舒服] 內特 - 哈迪森] [哈佛大學] 這是CS50。[CS50.TV] 好的。第6節。 這個星期，我們將要討論關於數據結構的部分， 這主要是因為這週的問題上設置spellr 做了一大堆不同的數據結構探索。 有一堆不同的方式，你可以去的問題集中， 和更多的數據結構，你知道的，你可以做很酷的事情。 

因此，讓我們開始吧。首先，我們要談棧， 棧和隊列的數據結構，我們要談的。 棧和隊列是非常有用的，當我們開始談論圖形， 我們不打算現在做這麼多的權利。 但他們真的很好理解的一個大的基本數據結構的CS。 問題集規範中的描述， 如果你拉了起來，談論類似於堆棧的 樁，你必須在食堂，在食堂用餐托盤 在那裡，當在餐廳的工作​​人員來了，放出來後，他們已經清理了他們的用餐托盤， 他們疊上其他頂級之一。 然後，當孩子們在食物中獲得， 他們拉盤，先頂一個，然後它下面的一個，然後是下一個。 所以，實際上，第一盤，就餐人員放下是最後一個被採取關閉。 ，餐廳工作人員把最後一個是第一個被關閉晚餐。 在這個問題集的規格，您可以下載，如果你還沒有的話， 我們談論建模堆棧中的數據的金盞使用這種結構。 

因此，我們有什麼，這是什麼，提出了在課堂上， 除了在課堂上，我們提出了這個int類型，而不是為char *。 這將是一個堆疊中儲存？ 丹尼爾？什麼是存儲在棧？ [丹尼爾]字符串？ >>我們的字符串存儲在棧，準確。 你需要有以創建一個堆棧是一個數組 一個特定的容量，在這種情況下， 能力將是全部大寫，因為它是一個常數。 然後在除了陣列，我們需要跟踪的是電流大小的數組。 這裡有一點要注意這是一種很酷 是，我們正在創造的堆積之上的另一種數據結構，數組的數據結構。 有不同的方法來實現棧。 我們不會做還相當，但希望做鍊錶的問題後， 你會看到，你可以很容易地實現一個棧的鍊錶。 但現在，我們將堅持到陣列。 所以，再一次，所有我們需要的是一個數組，我們只需要跟踪數組的大小。 [三]對不起，那你為什麼說堆棧的頂部的字符串？ 對我來說，似乎，像字符串是在棧。 [哈迪森]是啊。我們正在創造的，我們正在做我們的數組的數據結構 -  這是一個很大的問題。所以，問題是，誰是看這個網上的人， 為什麼我們說堆棧頂部的字符串， 因為在這裡它看起來像兩個字符串裡面的堆棧嗎？ 這是完全的情況下。 我指的是，我們已經有一個數組的數據結構。 我們已經得到的char *數組，這個數組的字符串， 我們要加至，以創建數據結構的層疊。 

因此，一個堆棧比數組稍微更複雜。 我們可以使用一個數組來建立一個堆棧。 所以這就是我們說的堆棧是建立在一個陣列的頂部。 同樣，正如我前面所說，我們可以建立一個堆棧上的鍊錶。 而不是使用一個數組來保存我們的元素， 我們可以使用一個鍊錶來保持我們的元素，並建立堆棧左右，。 讓我們通過幾個例子，看一些代碼， 看看這裡發生的一切。 在左邊的，我扔了下來，堆棧結構看起來就像在內存中 如果能力在＃定義為4。 我們有我們的四元素的char *數組。 我們已經有了字符串[0]字符串[1]，字符串[2]，字符串[3]， 然後就是最後我們的空間大小的整數。 這有意義嗎？好吧。 這是發生什麼，如果我做什麼的權利， 這將是我的代碼，只需要聲明一個結構，稱為s的堆疊結構。 這就是我們所得到的。它規定了這佔用內存中。 這裡的第一個問題是，該堆棧結構的內容是什麼？ 現在他們什麼都不是，但不是完全沒有。 他們這種垃圾。我們不知道是什麼。 當我們宣布棧S，我們僅僅是用下來的內存上。 這是一種類似於聲明INT I，而不是初始化它。 你不知道有什麼可以做的。你可以在那裡讀什麼， 但它可能不會是有幫助的。 你要永遠記住做的一件事是初始化任何需要被初始化。 在這種情況下，我們要初始化的大小是零， 因為那將是對我們非常重要。 我們可以繼續前進，初始化的指針，所有的char * S， 一些可以理解的價值，可能為null。 但它不是完全必要的，我們做到這一點。 

現在，這兩個主要操作棧是什麼？ 有人還記得演講一摞摞你做了什麼？是嗎？ [斯特拉入棧和出棧？ “沒錯。 入棧和出棧的兩個主要操作棧。 推做什麼？ >>它把東西到頂部 棧，然後大跌眼鏡把它關閉。 [哈迪森沒錯。因此，推，推壓在堆棧的頂部上的東西。 這就像在餐廳工作人員的用餐托盤放在櫃檯上。 大跌眼鏡的是一個餐盤堆棧。 讓我們通過一對夫婦的例子發生了什麼 當我們事情推入堆棧。 如果我們推到我們的堆棧字符串'hello'， 這是我們的圖現在是什麼樣子。 看看會發生什麼？ 我們推入我們的字符串數組的第一個元素 我們調升我們的規模數為1。 因此，如果我們看兩個幻燈片之間的區別，在這裡為0，前推。 這裡是後推。 前推，後推。 現在，我們有我們的棧中的一個元素。 這是字符串“hello”，這就是它。 一切，在我們的字符串數組，數組中的垃圾。 我們沒有初始化它。 比方說，我們推進另一個字符串到我們的堆棧。 我們要推動“世界”這個時間。 所以，你可以看到這裡的“世界”頂部的“hello”， 和的大小計數上升到2。 現在，我們可以把“CS50”，那將再次走在上面。 如果我們回去吧，你可以看到我們如何推動事情的堆棧的頂部。 現在，我們得到流行。 當我們彈出的堆棧的東西，這是怎麼回事？ 任何人看到其中的差別嗎？這是很微妙的。 [學生]的大小。 “是的，變化的大小。 

你還有什麼改變？ [學生]中的字符串。 “沒錯。的字符串。 事實證明，當你做它，這樣一來， 因為我們還沒有的元素複製到我們的堆棧， 我們其實並不需要做什麼，我們就可以使用的大小 跟踪的一些事情在我們的數組 所以，當我們再次彈出，再次我們只是我們的規模遞減下降到1。 有沒有必要去和覆蓋任何東西。 一種時髦的。 事實證明，我們通常只是離開的事情，因為這是我們做的工作的。 如果我們不回去，覆蓋的東西，那麼為什麼這樣做？ 所以，當我們的堆棧，彈出兩次的，它是遞減的大小了幾次。 再次，這僅僅是因為我們並沒有複製的東西到我們的堆棧。 是嗎？來吧。 不知所云] >> [學生，然後會發生什麼，當你把東西了嗎？ 當你再次推的東西，它在哪裡去了？ 到哪裡去了，瓦西裡？ >>轉換成字符串[1]？ “沒錯。 它為什麼不進入字符串[3]？ 因為它忘記了，有什麼字符串中的[羅勒] [1] [2]？ [哈迪森沒錯。我們的棧，從本質上講，“忘了”，這是到什麼 [1]中的字符串或字符串[2]，因此，當我們把“活泉”， 它只是將字符串[1]的元素。 是否有任何問題，這是如何工作的，在一個基本的水平呢？ [三]因此，這是不以任何方式，在動態方面的金額 或條款的堆棧大小？ [哈迪森沒錯。這是 - 這一點，這是不是一個動態growning的堆棧。 這是一個堆棧，可容納最多4的char *，最多四件事情。 如果我們試圖和推動五分之一的事情，你認為應該發生的嗎？ [學生，不知所云] [哈迪森沒錯。有一些事情會發生。 它可能會段錯誤，這取決於我們什麼 -  我們究竟是如何實現的後端。 它可以覆蓋。它可以有，我們在課堂上談到，緩衝區溢出。 什麼是最明顯的事情，可能會被覆蓋 如果我們試圖把一個額外的東西，我們的堆棧嗎？ 所以你提到的緩衝區溢出。 可能被寫入或出醜的事情是什麼 如果我們溢出意外試圖把一個額外的東西嗎？ [丹尼爾，不知所云] >>可能。 但在最初，可能會發生什麼？如果我們試圖把四分之一的事情嗎？ 它可能會覆蓋的大小，至少，我們已經有了這個內存圖。 

在這個問題中集規範，這就是我們將要實施的今天， 我們做想做的事，只是返回false。 我們的push方法會返回一個布爾值， 和布爾值是true，如果成功推 假的，如果我們不能把任何東西更多，因為堆棧是滿的。 讓我們通過一點點的代碼。 下面是我們的推送功能。 我們的推送功能的堆棧中的字符串放到棧中。 這將返回true，如果該字符串被成功地推 在堆棧，否則返回false。 什麼可能是一個良好的第一件事就是在這裡做的任何建議嗎？ [三]如果大小等於能力，那麼返回假的？ [哈迪森]賓果遊戲。尼斯的工作。 如果大小的能力，我們將返回false。 我們不能把任何東西在我們的堆棧。 否則，我們要放東西的堆棧的頂部。 “堆棧的頂部，”最初是什麼？ [丹尼爾]大小為0？大小為0。 後，有一件事在堆棧中的堆棧的頂部是什麼？大小姐，你知道嗎？ [大小姐]。 >>尺寸是的，沒錯。不斷增加的大小， 每次你把新的元素在數組中的索引大小。 我們可以做這樣的一個班輪，如果是有道理的。 所以，我們有我們的字符串數組，我們要訪問它的規模指數， 我們只是在那裡來存儲我們的char *。 請注意有沒有字符串複製在這裡， 沒有動態分配的內存？ 然後大小姐帶來了什麼，我們現在要做的， 因為我們的字符串存儲在陣列中的適當位置， 她說，我們的規模遞增，所以我們已經準備好為未來推。 因此，我們可以做到這一點，與s.size + +。 在這一點上，我們已經被推到我們的數組。我們必須做的最後一件事情是什麼？ [學生]：返回true。 >>返回true。 因此，它是非常簡單的，一個非常簡單的代碼。不太多。 一旦你已經包裹著你的頭周圍的堆棧是如何工作的， 這是非常簡單的實現。 

現在，下一個的一部分，這是一個字符串關閉堆棧彈出。 我想給你們一些時間來工作，這是一個有點。 這幾乎是本質上是相反的我們做了什麼在推動。 我所做的其實是 - 哎呀。 我已經啟動的器具，在這裡，在家電， 我拉起的設置5規範的問題。 如果我們放大在這裡，我們可以看到我在cdn.cs50.net/2012/fall/psets/pset5.pdf。 你們下載的代碼，設在這裡，section6.zip？ 好的。如果你還沒有這樣做，這樣做，現在，真的很快。 我會做到這一點在我的終端窗口。 其實，我在這裡做了。是啊。 是的，山姆？ >>我有一個問題，你為什麼說s.string的括號內的大小= STR？ STR是什麼？的是，以前在什麼地方，或 - 哦，在char *海峽？ [哈迪森]是的，沒錯。這是的說法。哦，沒關係。抱歉。 [哈迪森我們指定的字符串推入。 其他可能遇到的問題，我們並沒有真正在這裡談論的是 我們想當然的，我們有這個變量稱為s 這是在範圍和訪問。 我們採取理所當然地認為是這個堆棧結構。 所以回頭看這推的代碼， 你可以看到，我們正在做的東西與這個字符串的時候傳遞 但隨後突然，我們訪問s.size，如，走到哪兒呢？ 在代碼中，我們要看看在一節中的存檔 然後設置的東西，你會做你的問題， 我們已經取得了我們的協議棧結構的一個全局變量 這樣我們就可以訪問它，在我們所有的不同的功能 而無需手動傳遞它，並通過它的參考， 做所有這類的東西。 我們只是騙了一點點，如果你願意，讓事情變得更好的。 這就是我們在這裡做的東西，因為它的樂趣，它更容易。 通常情況下，你會看到人們這樣做，如果他們有一個很大的數據結構 在他們的程序中的操作。 

讓我們回到的設備。 每個人都成功地得到section6.zip？ 每個人都將它解壓縮使用解壓縮section6.zip？ 如果你進入第6節目錄 -  AAH，所有的地方 -  和你列出在這裡，你看，你有三個不同的c文件。 你有一個隊列中，SLL，這是單鍊錶，和堆棧。 如果你打開stack.c， 你可以看到，我們已經為我們定義了這個結構， 確切的結構，我們剛才講的幻燈片中。 我們已經得到了我們的全局變量的堆棧， 我們已經得到了我們的推送功能， 然後我們有我們的流行功能。 我會把代碼的推背在幻燈片上， 但我想你們做的是，盡你的能力， 去實現彈出的功能。 一旦你實現了它，你就可以編譯使堆棧， 然後運行生成的可執行堆棧， 將運行所有測試代碼在這裡，在主。 主要負責的實際push和pop調用 ，確保一切通過所有權利。 它也初始化堆棧的大小在這裡 所以你不必擔心初始化該。 你可以假設它被正確初始化 的時候，你訪問它，在彈出的功能。 這是否有意義嗎？ 所以，在這裡，我們走了。有“推”的代碼。 我給你們5分鐘或10分鐘。 如果你有任何問題，在此期間，當你編碼， 請大聲問他們。 所以，如果你得到一個棘手的問題，就問我。 讓我知道，讓其他人知道。 工作與你的鄰居了。 [丹尼爾]我們只是實現POP現在好了嗎？ >>只是彈出。 雖然你可以推，如果你想複製的實施 使測試工作。 因為它是難以測試的東西進入 -  或者，這是很難測試彈出堆棧出來的東西，如果沒有任何堆棧中開始。 

流行音樂應該是返回是什麼？從堆棧頂部的元素。 它應該得到元素的堆棧的頂部 然後遞減堆棧的大小， 現在你已經失去了元素的頂部。 然後返回的元素在上面。 [學生，不知所云] [哈迪森]所以，如果你這樣做，會發生什麼？ [學生，不知所云] 最終發生的是什麼，你可能訪問任何 尚未初始化的元素，所以你的計算 最後一個元素是處於關閉狀態。 所以在這裡，如果你注意到，在推，我們訪問在s.size元素的字符串 因為它是一個新的索引。 這是新的堆棧的頂部。 而在流行音樂，s.size將是下一個空格， 空間的所有元素在堆棧的頂部。 因此，最頂端的元素是不在s.size， 但相反，它是在它下面。 

其他的事情，當你 - 在彈出 你有遞減的大小。 如果你還記得我們的小圖就在這裡， 真的，只有我們看到了發生的事情，當我們調用pop 是，這個尺寸下降，第一至第2，然後為1。 然後，當我們把一個新的元素，它會繼續在適當的位置。 羅勒如果s.size 2，然後將它的元素， ，然後你要彈出該元素嗎？ 因此，如果我們去了 - “”所以，讓我們再看看這個。 如果這是我們在這一點上堆 我們稱之為流行， 指數是最上面的元素嗎？ [羅勒] 2，但它是怎麼回事，彈出3。 “沒錯。 所以這就是我們的規模是3，但我們要流行的元素，索引2處。 這是典型的種關閉的，你有零的數組索引。 所以，你要彈出的第三個元素，但第三個元素是不是在索引3。 原因我們沒有做到這一點減1，當我們正在推動 是因為現在，你注意到最上面的元素， 如果此時我們推入堆棧別的， 我們希望將它在索引3。 它只是發生的大小和排隊的指數，當你推。 

誰擁有一個工作棧的實現？ 你已經有了一個工作中的堆疊。你有沒有流行的工作嗎？ 丹尼爾：是的。我是這麼認為的。 >>程序的運行，而不是段的斷層，它打印出來嗎？ 它打印出來的“成功”，當你運行它呢？ 是啊。疊加，運行它，如果它打印出的“成功”，不繁榮， 然後，所有的好。 好的。讓我們的設備真的很快， 我們將步行通過。 如果我們看一下這是怎麼回事在這裡的流行音樂， 丹尼爾，究竟是什麼做的第一件事，你呢？ [丹尼爾]如果s.size是大於0。 [哈迪森]好吧。你為什麼這樣做呢？ [丹尼爾]為了確保堆棧中，有一種內在的東西。 [哈迪森權。你想進行測試，以確保，s.size大於0; 否則，你有什麼要發生嗎？ [丹尼爾]返回空值嗎？ >>返回NULL，準確。 因此，如果s.size是大於0。那麼什麼是我們該怎麼辦？ 如果堆棧不為空，我們該怎麼辦？ [斯特拉]遞減的大小嗎？ >>您遞減的大小，還行。 所以，你是怎麼做到這一點呢？ >> s.size  - 。 [哈迪森大。然後你做了什麼？ [斯特拉然後我說回s.string [s.size]。 [哈迪森大。 否則返回null。是的，山姆？ [三]為什麼不需要s.size的+ 1？ [哈迪森]加1？ >>呀。 “知道了。 [三]我想因為你正在服用1個輸出， 然後你要回來，他們要求的不是一個。 哈迪森而這正是我們在談論這個問題的0指數。 因此，如果我們在這裡放大。 如果我們看一下這傢伙在這裡，你可以看到，當我們彈出， 我們在彈出的元素索引2處。 

因此，我們減少我們的規模，我們的規模符合我們的索引中。 如果我們不遞減的大小，那麼我們需要做的大小，-1，然後遞減。 大。所有的好？ 任何問題嗎？ 有許多不同的方式來寫這個問題，以及。 事實上，我們可以做一些事情，甚至 - 我們可以做一個班輪。 我們可以做一個單行的回報。 因此，我們實際上可以減小之前，我們通過這樣做，返回。 因此，把 - 前s.size中。 這使該行真的很密集的。 凡 - 第大小和s.size  - 之間的差異 這個後綴 - 他們把它叫做後綴因為 - 來自後s.size  -  意味著s.size找到索引的目的評價 因為它是目前被執行時，這條線， 然後 - 發生後，該行被執行。 後的元素在索引s.size的訪問。 這不是我們所希望的，因為我們希望首先發生遞減。 Othewise，我們將要訪問的陣列，有效地，出界了。 我們將要訪問的元素，我們要訪問一個以上。 是啊，山姆？ “是更快或使用較少的內存在同一行或不使？ [哈迪森說實話，這真的視情況而定。 [山姆店，不知所云] >>呀，視情況而定。你可以做編譯器技巧 讓編譯器認識到，通常情況下，我想。 

所以，我們所提到的有關該編譯器優化的東西一點點 您可以在編譯， 這是一個編譯器可能能夠找出什麼樣的事情， 喜歡哦，嘿嘿，也許我可以做這一切在一次操作中， 而不是在從RAM加載的大小變量， 遞減，其存儲回，然後再重新加載 處理此操作的其餘部分。 但通常情況下，沒有，這是不諸如此類的事情， 這將會使你的程序顯著更快。 任何更多的問題棧？ 

因此，入棧和出棧。如果你們想嘗試的黑客版， 我們所做的黑客版實際上是走了 ，這個堆棧動態增長。 面臨的挑戰主要是在推功能在這裡， 弄清楚如何使該數組中成長 當你繼續推到堆棧上越來越多的內容。 它實際上是沒有太多額外的代碼。 只需要打一個電話 - 你必須記住要調用malloc（）有正確的， 然後當你要調用realloc的。 這是一個有趣的挑戰，如果你有興趣。 

但暫時，讓我們繼續前進，讓我們來談談隊列。 滾動經過這裡。 隊列是親兄妹的堆棧。 所以在堆棧中的東西，放在最後 的第一件事情，然後進行檢索。 我們已經得到這最後的，先出，或後進先出法，訂貨。 而在隊列中，你所期待的，當你站在線， 線，第一件事就是到隊列中的第一人， 是的第一件事就是被從隊列中檢索。 隊列也經常被用來當我們正在處理的圖形， 像我們談到了簡短的堆棧， 和隊列的一堆其他東西也很方便。 有一件事，往往出現正在努力維持，例如， 元素的排序列表。 你可以做到這一點的數組。您可以保持在一個數組的排序列表的東西， 但在變得複雜的是，那麼你總是要找到 在適當的地方插入接下來的事情。 所以，如果你有一個數組的數字，從1到10， 然後你要擴大到所有的數字1到100， 你得到這些數字中隨機的順序，並試圖把一切都 排序，你通過，你最終做了很多的轉移。 某些類型的隊列和某些類型的底層數據結構， 實際上，你可以保持相當簡單。 您不必添加一些東西，然後洗牌整個事情的時間。 你也做了很多的內部元素的轉移。 當我們在看一個隊列，你看 - 在queue.c也一節中的代碼 -  的結構，我們已經給了你，我們給你一個堆棧的結構非常類似。 

有一個例外，唯一的例外 是，我們有這個額外的整數稱為頭， 和這裡的頭部為隊列頭的跟踪的 或在隊列中的第一個元素。 用一個堆棧，我們能夠跟踪我們要擷取的元素， 或堆棧頂部的，只是使用的大小， 而我們的隊列，處理兩端。 我們正在努力結束時粘性的東西，但然後返回從正面的東西。 因此，有效的是，用頭，我們有隊列的開頭的索引， 和容量給我們的隊列的末尾的索引 這樣我們就可以獲取事物從頭部添加東西的尾巴。 鑑於帶層疊，我們只處理堆棧的頂部。 我們從來沒有訪問堆棧的底部。 我們只添加東西到頂部，拿了東西的頂部 所以我們並不需要額外的內部結構領域。 一般有意義嗎？ 好的。是的，夏洛特？ [夏洛特，不知所云] 哈迪森]這是一個很大的問題，這是一個在演講。 也許走過的幾個例子說明了為什麼 我們不希望使用字符串[0]的隊列的頭。 

所以，想像一下，我們有我們的隊列中，我們將調用它的隊列。 在剛開始的時候，我們剛剛實例化它， 當我們剛剛宣布了它，我們還沒有初始化任何東西。 這是所有的垃圾。當然，我們要確保我們初始化 的大小和頭信息是0，一些合理的。 我們還可以繼續前進，在我們的隊列空出的元素。 此圖配合，請注意，現在我們的隊列只能容納三要素; 而我們的堆疊可容納四，我們的隊列只能容納3。 而這僅僅是使圖適合。 這裡發生的第一件事情是我們進行排隊字符串“hi”。 就像我們與堆棧，這裡沒有什麼可怕的不同， 我們拋出的字符串，字符串[0]和我們的規模遞增1。 我們的入隊“再見”，它被裝出來的。 因此，這看起來就像一個堆棧的大部分。 我們這裡，開始了新的元素，新元素，規模不斷上升。 在這一點上會發生什麼事時，我們要出列的東西嗎？ 當我們要出列，這是我們要出列的元素嗎？ [羅勒]字符串[0]。 >>零。沒錯，羅勒。 我們要擺脫的第一個字符串，這其中，“喜”字。 那麼，是什麼其他的事情，改變了嗎？ 請注意，當我們突然出現的堆棧的東西，我們只是改變了大小， 但在這裡，我們有一對夫婦的一些改變。 不僅的大小變化，但頭部的變化。 這是要回到夏洛特點： 為什麼我們有這個頭呢？ 這是否有意義，夏洛特？ >>類的。 [哈迪森怎樣的呢？到底發生了什麼，當我們出列嗎？ 什麼頭做的，現在是有趣的？ [夏洛特]哦，因為它改變了 - 好吧。我明白。 因為頭 - 頭指向的位置方面的變化。 它不再是零指數1。 >>是的，沒錯。 發生了什麼事，如果出隊的高元 做，我們沒有這個頭字段 因為我們總是在0指數，我們的隊列的頭，調用該字符串 然後，我們不得不轉移，其餘的隊列。 我們不得不轉向“再見”從字符串[1]的字符串[0]。 字符串[2]到字符串[1]。 我們不得不這樣做的整個列表中的元素， 整個陣列的元素。 當我們這樣做是一個數組，變得非常昂貴。 所以在這裡，它不是一個大問題。我們只需要在數組中的三個要素。 但是，如果我們有一千或一萬個元素的隊列， 然後突然間，我們開始出列了一堆調用所有在一個循環中， 事情真的要放慢，因為它轉移一切不斷。 你知道嗎，轉移1，移位1 1，移位，移位1。 相反，我們使用這個頭，我們把它稱為一個“指針”，即使它不是一個真正的指針 從嚴格意義上講，它不是一個指針類型。 這不是一個int *或char *或類似的東西。 但是，它指向或表示我們的隊列的頭。是嗎？ 

[學生]：出隊知道如何只彈出，無論是在頭部？ [哈迪森如何出隊知道如何彈出無論是在頭嗎？ “是的，是的。 >>什麼，它看起來是，只是任何頭字段被設置為。 因此，在這第一種情況下，如果我們看一下在這裡， 我們的頭是0，索引為0。 “沒錯。 [哈迪森]因此，它只是說，好吧，索引為0的元素，字符串“您好”， 在我們的隊列頭的元素。 因此，我們要出列，那傢伙。 那將會是元素，該元素被返回給調用者。 是的，薩阿德嗎？頭“等基本設置 - 你要去的地方的索引呢？ 這是它的開始呢？ >>呀。 “好了。 哈迪森]這是我們的陣列成為新的開始。 所以，當你出列的東西，所有你所要做的是在索引訪問元素q.head， 和將要出列的元素。 您還可以遞減的大小。 我們會看到在事情變得有點棘手，這一點。 我們出列，而現在，如果我們再進行排隊， 我們進行排隊在哪裡？ 在我們的隊列中的下一個元素哪裡？ 假設我們要排隊的字符串“CS”。 到索引會去嗎？ [學生]字符串[2]。 >>雙。 為什麼是2而不是0呢？ [羅勒]因為現在的頭是1，所以這就像開始的列表嗎？ [哈迪森權。表示最終的名單什麼？ 我們來表示我們的隊列？ 頭是頭，我們的隊列中，開始我們的隊列中。 我們的隊列中的結局是什麼？ [學生]大小。 >>大小，準確。 因此，我們的新的元素，在大小，並在頭的元素，我們採取的脫落。 當我們加入隊列的下一個元素，我們正在把它在大小。 [學生]：在您提出，雖然，大小為1，正確的嗎？ [哈迪森權。因此，在大小相當。尺寸+，+1，+頭。 因為我們將一切頭量。 所以在這裡，現在我們已經有了一個大小為1的隊列開始在索引1。 尾巴是指數2。是嗎？ 

[學生]：會發生什麼事時，你出列字符串[0]，和字符串的內存插槽 一下就空了，基本上，或者只是忘了嗎？ [哈迪森]是啊。從這個意義上說，我們只是忘記他們。 如果我們存儲副本 -  許多數據結構往往會保存自己的副本的元素 管理的數據結構，使該人不必擔心 所有這些指標都在哪裡。 數據結構包含的一切，擁有所有的副本， 以確保這一切仍然存在，適當的。 然而，在這種情況下，這些數據結構只是為了簡單起見， 不是我們的東西都存儲在他們的副本。 [學生]：所以，這是一個連續的數組 - ？ “是的。 如果我們回頭看，這種結構的定義是什麼，它是。 這只是一個標準的數組，就像你看到的那樣， 數組的char *。 那是 - ？是啊，我只是想知道 如果你最終會耗盡內存，在一定程度上， 如果您有您的陣列中的所有這些空點嗎？ 哈迪森]是啊，這是一個很好的點。 

如果我們看看發生了什麼事，現在在這一點上， 我們已經充滿了我們的隊列中，它的樣子。 但是我們還沒有真正填補了我們的隊列 因為我們有一個隊列的大小，但它在索引1開始， 因為這就是我們的頭指針。 像你說的，在字符串的元素[0]，在0指數，是不是真的存在。 這不是在我們的隊列中了。 我們只是懶得去和覆蓋它時，我們出列。 因此，即使它看起來就像我們的內存已經用完了，我們真的沒有。 這點是可供我們使用。 適當的行為，如果我們試圖和第一個出列的東西 如“再見”，會彈出再見關閉。 現在，我們的隊列開始索引2處，大小為1。 現在，如果我們試圖再次進行排隊東西，比如50， 50應該在這點指數0 因為它仍然為我們提供。是的，薩阿德嗎？ [薩阿德並自動發生嗎？ [哈迪森它不會自動發生相當。你必須做數學題 它的工作，但基本上是我們所做的就是我們剛剛纏。 [薩阿德是好，如果在它的中間有一個洞？ 哈迪森的是，如果我們能正確的數學工作。 

事實證明，這實際上是很難做到的mod運算符。 所以，就像我們與凱撒和加密東西， 使用模，我們可以得到的東西，以環繞，並保持下去 周圍一圈又一圈與我們的隊列中， 保持周圍，頭指針移動。 請注意，尺寸總是尊重的元素數實際上內的隊列中。 而這僅僅是頭指針，騎自行車通過。 如果我們看看這裡發生了什麼事，如果我們回到開頭， 你只是看看會發生什麼頭 當我們進行排隊的東西，什麼都沒有發生的頭部。 當我們排隊的其他東西，什麼都沒有發生的頭部。 只要我們出列的東西，頭一個。 我們排隊的東西，什麼也沒有發生的頭部。 當我們出列的東西，一下子頭會增加。 當我們進行排隊的東西，什麼也沒有發生的頭部。 

在這一點上會發生什麼，如果我們再次出列的東西嗎？ 有什麼想法？頭會發生什麼？ 什麼是應該發生的頭 如果我們出列別的東西嗎？ 頭現在是索引2處， 這意味著隊列頭部的字符串[2]。 [學生]：它返回0？ >>，它應該返回為0。它應該換點左右，準確。 到目前為止，我們每次叫出隊，我們已經添加一個頭， 添加一個頭，加一個頭，添加一個頭。 一旦這個頭指針到達最後一個索引在數組中， 然後，我們必須把它包起來開始回到身邊，回到0。 [夏洛特]確定堆棧的隊列中的能力？ [哈迪森在這種情況下，我們剛剛一直在使用一個＃定義的常量。 “好了。 [哈迪森在實際的文件，你可以去和淤泥一點點 大或小，你想要的。 [山貓]因此，當你正在做一個隊列，怎麼你的計算機知道 你想堆疊就可以有多大？ 哈迪森]這是一個很大的問題。 有一對夫婦的方式。一種是只定義了前 並說這將是一個隊列中有4個元素或50個元素或10,000。 另一種方法是做的黑客版的人在做什麼 並創建功能，讓您的隊列動態地增長，越是得不到的東西加進來 

[山貓]第一個選項，語法是什麼您使用 告訴程序什麼是隊列的大小嗎？ 哈迪森啊。所以，讓我們離開這。 我仍然在這裡stack.c，所以我只是要滾動到頂部。 在這裡你能看到這種權利？這是的＃define能力10。 這幾乎是完全相同的語法，我們已經為隊列。 除了在隊列中，在這裡，我們已經得到了額外的結構域。 [夏洛特]哦，我想指的是容量為字符串的能力。 哈迪森啊。 >>這個詞，它的最大長度。 “知道了。 是啊。這裡的能力 - 這是一個偉大的點。 這是這是棘手的 因為我們已經在這裡聲明的是一個數組的char *。 數組的指針。 這是一個字符數組。 這可能是你見過的時候，你已經宣布你的緩衝區的文件I / O， 當你已經創建字符串手動在堆棧中。 然而，我們得到的是一個數組的char *。 因此，它是一個數組的指針。 其實，如果我們放大了，我們看看這是怎麼回事 在演示文稿中，您將看到實際的元素，字符數據 沒有被存儲在數組本身。 什麼是存儲在我們的數組的指針的字符數據。 好吧。因此，我們已經看到了如何與堆棧，隊列大小就像， 大小始終尊重當前隊列中的元素的數量。 2 enqueue操作完畢後，大小為2。 在出隊的規模現在是1。 在另一個排隊的大小是高達2。 這樣的大小在隊列中，絕對尊重的元素數 頭，然後不斷循環。 從0-1-2，0-1-2，0-1-2。 每次我們調用出隊，頭指針會遞增到下一個索引。 如果頭走了過來，這回繞到0。 所以，我們可以編寫出列的功能。 我們要離開排隊功能來實現，而不是你們。 

當我們隊列中取出一個元素，我們的隊列中， 丹尼爾的第一件事情就是當我們開始寫的堆棧彈出功能是什麼？ 讓我聽到從別人誰沒有發言。 讓我們來看看，薩阿德，你還記得丹尼爾做的第一件事時，他寫道：彈出？ [薩阿德]，它是 -  >>他測試的東西。 薩阿德]如果大小是大於0。 “沒錯。 那是什麼測試？ 薩阿德測試，看看如果有什麼事，裡面的數組。 [哈迪森]是啊。沒錯。所以，你可以不彈出任何出棧，如果它是空的。 同樣，你不能從隊列中出列任何東西，如果它是空的。 什麼是我們應該做的，我們出隊函數的第一件事，你覺得呢？ 薩阿德]如果大小是大於0？ >>呀。 在這種情況下，我其實只是測試，看它是否為0。 如果是0，我們可以返回null。 但相同的邏輯。 讓我們繼續。 如果不為0，是我們要出列的元素？ 薩阿德在頭嗎？ “沒錯。 我們可以在我們的隊列中拉出的第一個元素 通過訪問的頭部處的元素。 沒有什麼神秘的。 在那之後，我們應該怎麼辦？有什麼發生呢？ 其他的事情，我們談到在出隊的是什麼？ 有兩件事情要發生，因為我們的隊列已經改變。 [丹尼爾減少的大小。 >>我們必須縮小尺寸，並增加頭部？沒錯。 為了增加頭部，我們不能只是一味地增加了頭，記住了。 我們可以不只是做queue.head的+ +。 我們也必須包括這個MOD的能力。 我們為什麼要國防部的容量，Stella嗎？ 斯特拉由於它具有環繞。 “沒錯。 我們的國防部的容量，因為它具有包裝回繞到0。 所以，現在，在這一點上，我們可以做什麼，丹尼爾說。 我們可以減小尺寸。 然後我們就可以返回的元素在隊列的最前面。 它看起來有點粗糙第一。你可能有一個問題。你說什麼？ 

[三]為什麼是第一個在隊列的最前面？哪裡去了？ 哈迪森]從第四線從底部。 經過我們測試，以確保我們的隊列不為空， 我們拉出來的char *首先，我們拉出來的元素，坐在頭指數 我們的數組，字符串數組，“呼叫，第一呢？ [哈迪森]，我們稱之為第一。是啊。 只是跟進，為什麼你認為我們必須這樣做嗎？ [三]每個第一剛剛返回q.strings的[q.head？ >>呀。 “因為我們正在做這個不斷變化的的q.head的MOD功能的， 有沒有辦法做到這一點也回線內。 [哈迪森沒錯。你點上。三是完全發現。 究其原因，我們在我們的隊列中拉出的第一個元素，並將其存儲到一個變量 是因為這條線我們剛剛q.head的， 有mod運算符在那裡沒有的東西，我們可以做的 並使其生效的頭沒有 - 在同一行。 因此，我們必須拿出的第一個元素，然後調整頭， 調整大小，然後再回到我們拉出的元素。 而這點，我們將看到後與 鍊錶，我們打他們。 很多時候，當你釋放或處理鍊錶 你需要記住的下一個元素，在未來的鍊錶的指針 在處理當前。 因為否則你扔掉的左邊列表中的信息。 現在，如果你去到您的設備，你打開queue.c-X了這一點。 所以，如果我打開queue.c，讓我在這裡變焦， 你會看到，你有一個外觀類似的文件。 我們早前曾與stack.c外觀類似的文件。 我們已經得到了我們的結構定義的隊列，就像我們在幻燈片上看到的。 

我們有我們的排隊功能，這是為你做的。 我們這裡出列功能。 在該文件中的“出列”的功能未實現， 但我會把它備份，讓您可以輸入，如果你想在PowerPoint。 因此，在接下來的5分鐘左右，你們的工作排隊 這幾乎是正好相反出列。 您不必調整頭，當你入隊，但你有什麼調整嗎？ 大小。所以，當你排隊，頭部保持不動，被改變的大小。 但它確實需要一點點 - 你將不得不發揮與模 弄清楚究竟什麼樣的指標應插入新的元素。 所以，我給你們一點點，把出列在幻燈片上， 你們有問題，喊出來，使我們可以 都在談論他們作為一個群體。 此外，你不知道不知道 - 當你調整大小的尺寸，你永遠可以 -  你有沒有曾經國防部的大小嗎？ [丹尼爾]第>>您不必國防部的大小，正確的。 因為大小總是會，如果讓隱私無處藏 - 假設你正在管理的事情適當地， 的大小總是會在0和3之間。 你在哪兒於MOD當你在做排隊嗎？ [學生]的頭。 “僅適用於頭部，準確。 你為什麼國防部在排隊？ 的情況是，你必須為mod是什麼時候？ [學生]：如果你有東西在空間，喜歡在空間1和2， 然後你需要添加的東西在0。 [哈迪森]是的，沒錯。所以，如果你的頭指針是在最後， 如果你的尺寸加上你的頭比較大，或者更確切地說，是怎麼回事到環繞的隊列。 

因此，在這種情況下，我們已經有了在這裡在幻燈片上， 如果我現在要排隊， 我們要排隊什麼的索引為0。 因此，如果你在50“，我稱之為排隊50， 它會在底部。它在索引0。 它取代了已經出列'嗨'。 [丹尼爾]不要你照顧，出隊了嗎？ 為什麼它是做什麼用頭在排隊嗎？ [哈迪森]哦，這樣你就不會修改的頭，對不起。 但是，當你訪問，你必須用mod運算符 你要排隊，當你訪問的元素 你的隊列中的下一個元素。 瓦西裡我沒有做到這一點，我在那裡的“成功”。 [丹尼爾：哦，我明白你在說什麼。 [哈迪森所以，你並沒有 - 你只是做了在q.size？ [羅勒]是啊。我只是改變了雙方的，我沒有做任何事情的頭部。 [哈迪森]你實際上並不需要重設的頭是什麼， 但是當你到字符串數組中的索引， 你必須繼續前進，計算出下一個元素是， 因為枝條堆棧中的下一個元素在堆棧總是 的大小相對應的索引。 如果我們回顧一下，在我們的壓棧功能， 索引的大小，我們總是可以花掉我們的新元素。 而與隊列，我們不能這樣做， 因為如果我們在這種情況下， 如果我們排隊的50我們新的字符串，字符串[1] 我們並不想這樣做。 我們希望有新的字符串的索引為0。 

是否任何人 - 是嗎？ [學生]：我有一個問題，但它不是真正相關。 當有人要求類似PRED指針是什麼意思？ 那是什麼名字的簡稱嗎？我知道這只是一個名字。 哈迪森] PRED指針？讓我們來看看。在什麼情況下？ [學生]：這是插入。如果你想，我可以請你以後 因為它不是真正相關的，但我只是 -  [哈迪森從大衛的講座插入代碼？ 我們可以拉起來，說這些了。 我們將討論下，一旦我們得到的鏈接列表。 

因此，讓我們看排隊的函數看起來像真的很快。 人的第一件事就是試圖在您的排隊線是什麼？插入此隊列中呢？ 類似的堆棧推你做了什麼。 你做了什麼，Stella嗎？ [斯特拉，不知所云] [哈迪森沒錯。如果（q.size ==容量） -  在正確的地方，我需要把我的大括號 - 返回false。 在一點點放大。好吧。 現在什麼是未來的事情，我們必須做的嗎？ 與堆棧，就像插在正確的地方。 因此，什麼是正確的位置插入，？ 與堆棧是索引的大小，這不是很。 [丹尼爾]我有q.head- -   -  >> q.strings的嗎？ >>呀。 的q.strings q.head + q.size模能力]？ [哈迪森我們可能要加上括號解決這個問題 這樣我們就得到適當的優先，所以，大家cleart。 和平等的嗎？ >>海峽？ >>給乙方。大。 現在我們必須做的最後一件事是什麼？ 就像我們在堆棧中。 >>增量的大小嗎？ >>增量的大小。 轟。之後，從啟動代碼只是返回false默認情況下， 我們要更改為true，如果一切順利，一切順利。 好的。這是一個很大的信息部分。 我們不是挺了過來。我們要談談真的很快單鍊錶。 我會把這，所以我們可以回去吧。 但是，讓我們回到我們的介紹只是多了一些幻燈片。 因此，排隊是的TODO，現在我們已經做到了。 

現在，讓我們來看看在單鍊錶。 在講座中，我們談到了這些多一點點。 有許多你們在這裡我們看到的演示的人 笨拙地指向到相互持股數？ >>，我就在那。 “你們認為什麼？這樣做，希望神秘面紗這一點嗎？ 與列表，事實證明，我們應對這種類型的，我們要調用一個節點。 而與隊列和棧我們，我們會打電話給隊列，棧的結構， 我們有這些新的隊列，堆棧類型， 這裡的列表實際上只是由一堆節點。 以同樣的方式，字符串的字符只是一堆所有排隊彼此相鄰的。 鍊錶是一個節點和另一個節點和另一個節點和另一個節點。 而不是砸的所有節點，並將其存儲連續 所有彼此在內存中， 這下指針允許我們存儲節點的地方，隨意。 然後他們種線一起從一個點到下一個。 

是什麼很大的優​​勢，這有一個數組？ 連續超過存儲一切只是停留彼此？ 你還記得嗎？是嗎？ >>動態內存分配？ >>動態內存分配在什麼意義呢？ [學生]，你可以保持它大，你沒有將你的整個陣列？ [哈迪森沒錯。因此，一個數組，當你想要把一個新的元素，它的中間， 你有改變一切，以騰出空間。 而像我們談論的隊列中， 這就是為什麼我們保持頭指針， 所以，我們不是不斷變化的東西。 因為得到昂貴的，如果你有一個大數組 你經常做這些隨機的插入。 而與列表，所有您需要做的是把它的新節點上， 調整指針，你就大功告成了。 什麼吸什麼呢？ 除了事實上，它是不容易的工作數組？是嗎？ [丹尼爾]嗯，我想它要困難得多訪問某個特定的鏈接列表中的元素？ [哈迪森你不能只是跳轉到鍊錶中的任意一個元素。 你怎麼做，而不是嗎？ >>您逐步完成整個事情。 [哈迪森]是啊。你必須去通過一次一個地，一次一個。 這是一個巨大的 - 這是一個痛苦。 有什麼其他 - 這還有另一個倒台。 羅勒，您可以向前和向後走？你必須去一個方向嗎？ [哈迪森]是啊。那麼，我們如何解決這個問題，有時？ [羅勒]雙鍊錶？ “沒錯。有雙鍊錶。 也有 - 對不起嗎？ 

[三]是一樣PRED的事情， -  我想起來了，這不正是PRED的是嗎？ 這不就是在雙和單間？ [哈迪森]讓我們看看他在做的究竟是什麼。 所以，在這裡，我們走了。下面的代碼。 在這裡，我們有predptr，在這裡。這是你在談論什麼嗎？ 因此，這是 - 他釋放的名單，他試圖保存一個指向它的指針。 這是不是雙重，單鏈接列表。 我們可以稍後再談談這個問題，因為這是在談論釋放名單 我想告訴一些其他的東西。 但它只是 - 它記住的指針的值 [學生]：哦，這是前面的指針嗎？ >>呀。 所以，我們就可以遞增：指針本身之前，我們就可以自由predptr是什麼。 因為我們不能免費指針，然後調用PTR =指針下，對不對？ 這將是壞的。 所以，讓我們來看看，這個傢伙。 

有關列表的其他壞事，而數組 我們只是有自己的堆棧彼此的所有元素， 在這裡，我們也介紹了這個指針。 因此，有一個額外的內存塊，我們使用 對於每一個元素，我們要存儲在我們的名單。 我們得到的靈活性，但它是有代價的。 它配備了這個時間成本， ，它與此內存成本。 時間在這個意義上，我們現在必須在數組中的每個元素 找到在索引10中的一個，或者說，將有在一個數組中的索引10。 

真的很快，當我們圖的這些名單， 通常我們認為在頭部的列表或列表中的第一個指針 注意，這是一個真正的指針。 它只有4個字節。它本身不是一個實際的節點。 所以你看它有沒有int值，沒有next指針。 它實際上只是一個指針。 它要指向的東西，是一個實際的節點結構。 [三]一個指針，稱為節點？ >>這是 - 沒有。這是一個指向某種類型的節點。 它是一個指針的節點結構。哦，沒關係。 圖上的左，右側列表符號。 我們可以將其設置為null，這是一個很好的方式開始。 當你圖它，你要么寫為空或通過它，你放了行這樣的。 

使用列表的最簡單的方法之一， ，我們要求你都前置和追加到兩者之間的差異， 但在前面加上是肯定更容易。 當你在前面加上，這就是你的 - 當你預定（7） 你去創建節點結構 設置第一個指向它，因為現在，因為我們前面加上它， 它要在列表的開頭。 如果我們預定（3），，創建另一個節點，但現在前7。 因此，我們本質上推動我們的名單上。 現在，你可以看到前置，有時人們把它推， 因為你推到你的列表中一個新的元素。 在前面的列表中刪除它也很容易。 所以，人們往往會調用該彈出。 以這種方式，你可以模擬一個堆棧使用鍊錶。 哎呀。很抱歉，現在我們正在為追加。所以，我們在這裡前綴（7），現在我們預定（3）。 如果我們預先考慮別的東西到這個列表中，（4），如果我們預先考慮 然後，我們有4個，然後3，然後7。 那麼我們就可以彈出並刪除，刪除，刪除7。 通常情況下，更直觀的方式來思考這個是附加的。 所以，我圖表示出來，它看起來像什麼與附加在這裡。 在這裡，追加（7）不看有什麼不同 因為只有一個列表中的元素。 並追加（3）將它結束。 也許你可以看到現在的訣竅追加 是因為我們只知道該從哪裡開始的列表， 要追加到一個列表，在列表中，你必須走一路 去年底，停止，然後建立您的節點，和普拉克一切的下降。 連接所有的東西。 因此，前置，作為我們只是洞穿這真的很快， 當你預先準備的列表，這是相當簡單的。 

你讓你的新節點，涉及到一些動態內存分配。 所以，在這裡，我們正在做一個節點使用malloc的結構。 所以malloc的，我們正在使用的，因為這會為我們預留內存後 因為我們不希望這樣 - 我們希望這記憶將持續很長一段時間。 我們得到了一個指針，我們只是分配的內存空間。 我們使用的節點的大小，我們不總結的領域。 我們不手動生成的字節數， 相反，我們使用sizeof，讓我們知道我們得到適當的字節數。 我們一定要測試我們的malloc調用成功。 這是你想要做的一般。 在現代化的機器上，運行內存不足是不是一件容易 除非你分配一噸的東西，使一個巨大的名單， 但是，如果你的東西，比如說，像iPhone或Android， 你只有有限的內存資源，特別是如果你正在做的事情激烈。 所以這是很好的實踐。 

請注意，我在這裡已經使用了幾個不同的功能 您已經看到了，是種新的。 因此，fprintf同於printf 除了它的第一個參數是你要打印其中的流。 在這種情況下，我們要打印到標準錯誤字符串 這是從標準outstream不同。 默認情況下，它顯示了在同一個地方。 它也打印到​​終端，但你可以 -  使用這些命令，您了解，重定向技術 您了解了在托米的視頻，你可以直接問題集4 不同的區域，然後退出，在這裡，你的程序退出。 它本質上就像是從main返回， 除了我們使用exit因為這裡的利潤不會做任何事情。 我們不是主要的，因此返回不退出程序，像我們希望的。 因此，我們使用exit函數，並給它一個錯誤代碼。 那麼在這裡我們設置新節點的值字段，其i現場等於我，然後我們其連接。 我們設置新節點的next指針指向第一， 那麼首先將指向新的節點。 這些第一行代碼中，我們實際上是在建立新的節點。 不是最後兩行的這個功能，但第一的。 實際上，你可以拉成一個函數，一個輔助函數。 這通常我做什麼，我拉出來的功能， 我把它類似於構建節點， 的前置功能保持相當小，僅有3行，然後。 我打電話到我的體型節點的功能，然後我線的一切行動。 

最後一點，我想告訴你， 我會讓你做追加和自己的， 是如何遍歷列表。 還有一堆不同的方法來遍歷列表。 在這種情況下，我們要找到一個列表的長度。 因此，我們從長度= 0。 這是非常類似於寫strlen的一個字符串。 這就是我要告訴你，這個循環在這裡。 它看起來有點古怪，它不是一般的INT I = 0，我不管，我+ +。 相反，它的初始化我們的變量n的列表開始。 然後，我們的迭代變量不為空，我們繼續前進。 這是因為，按照慣例，我們的名單將是無效的。 然後遞增，而不是做+ +， 鍊錶相當於+ + N = N->下。 

我會讓你填寫在這裡的差距，因為我們沒時間了。 但記住這一點，當你在你的spellr的pset。 鍊錶，如果你正在實現一個哈希表， 一定會非常方便。 這個成語循環的事情，使生活變得更加簡單，希望。 如有任何疑問，速度夠快嗎？ [三]你會發出完成的SLL和SC？ [哈迪森]是啊。我會發出完成幻燈片和SLL協議棧和queue.cs的。 [CS50.TV]