[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]