داگ لوید: بنابراین اگر شما تماشای ویدئو بر روی پشته، این است که احتمالا رفتن به احساس مانند یک کمی از deja vu به. آن را به یک مفهوم بسیار مشابه، فقط با یک پیچ و تاب و کمی بر روی آن. ما قصد داریم به بحث در حال حاضر حدود صف. بنابراین یک صف، شبیه به یک پشته، نوع دیگری از ساختار داده است که ما می توانیم برای حفظ داده ها در یک روش سازمان یافته. شبیه به یک پشته، می توان آن را اجرا به عنوان یک آرایه یا یک لیست پیوندی. بر خلاف یک پشته، قوانین که ما برای تعیین زمانی که همه چیز اضافه کنید و از حذف یک صف هستند کمی متفاوت است. بر خلاف یک پشته، که ساختار LIFO است، آخرین در، اولین بار، یک صف FIFO است ساختار، FIFO، برای اولین بار در سال، از اول. در حال حاضر صف، شما احتمالا یک قیاس به صف. اگر شما تا به حال در خط در شده یک پارک تفریحی و یا در یک بانک، مرتب کردن بر اساس انصاف وجود دارد اجرای ساختار. اولین کسی در خط در بانک اول شخص است که می شود به صحبت می کنند به گوی. 

این امر می تواند از یک مسابقه به پایین اگر تنها راه شما رو به صحبت می کنند به گوی در بانک بود که به آخرین نفر در خط. همه همیشه می خواهید به آخرین فرد در خط، و کسی که وجود دارد برای اولین بار بود که شده است در انتظار در حالی که، می تواند برای ساعت وجود داشته باشد، و ساعت، و ساعت قبل از آنها احتمال به واقع برداشت هر گونه پول در بانک. و به این ترتیب صف ها مرتب سازی بر اساس انصاف اجرای ساختار. اما این لزوما به معنای که پشته یک چیز بد، فقط که صف راه دیگری برای انجام آن است. بنابراین دوباره صف است برای اولین بار در، برای اولین بار خارج، در مقابل یک پشته که در آخرین، برای اولین بار بیرون. شبیه به یک پشته، ما دو عملیات که ما می توانیم در صف را انجام دهد. نام ها در نوبت قراردادن، است که به اضافه یک عنصر جدید به انتهای صف، و dequeue است که به حذف از قدیمی ترین عنصر از جلوی صف. بنابراین ما قصد داریم برای اضافه کردن عناصر را به انتهای صف، و ما قصد داریم به حذف عناصر از جلوی صف. باز هم، با پشته، ما اضافه شد عناصر به بالای پشته و از بین بردن عناصر از بالای پشته. بنابراین با در نوبت قراردادن، آن را با اضافه کردن به پایان، از بین بردن از جلو. بنابراین قدیمی ترین چیزی که در آن وجود دارد همیشه چیزی که بعد از به بیرون آمدن اگر ما سعی و dequeue چیزی. 

پس دوباره، با صف، ما می توانیم پیاده سازی مبتنی بر آرایه و مرتبط لیست پیاده سازی است. ما دوباره با شروع پیاده سازی مبتنی بر آرایه. تعریف ساختار به نظر می رسد بسیار مشابه است. ما یک آرایه وجود دارد از داده ها ارزش نوع، پس از آن می توانید انواع داده های دلخواه را نگه دارید. ما دوباره قصد استفاده از اعداد صحیح در این مثال. 

و درست مثل با ما مبتنی بر آرایه اجرای پشته، چرا که ما با استفاده از یک آرایه، ما لزوما که محدودیت این نوع C از به اجرا می گذارد بر ما است که ما هیچ پویایی در ندارد ما توانایی رشد و کوچک آرایه. ما باید تصمیم در آغاز چه حداکثر تعداد از چیزهایی است که ما می توانیم به این قرار داده صف، و در این مورد، ظرفیت خواهد بود برخی از پوند در کد ما ثابت تعریف شده است. و برای اهداف این ویدئو، ظرفیت است برای رفتن به 10. 

ما نیاز به پیگیری جلوی صف بنابراین ما می دانیم که عنصر ما می خواهیم به dequeue، و ما نیز نیاز به پیگیری از چیزی else-- تعدادی از عناصر که ما در صف ما داشته باشد. توجه داشته باشید که ما در حال پیگیری نمی از انتهای صف، فقط اندازه صف. و دلیل است که امیدوارم تبدیل شدن به یک کمی روشن تر در یک لحظه. هنگامی که ما به پایان رسید این تعریف نوع، ما باید یک نوع داده جدید به نام صف، که در حال حاضر ما می توانیم متغیر با آن نوع داده را اعلام کند. و تا حدودی گمراه کننده، من تصمیم گرفتم پاسخ به این صف Q، نامه Q به جای نوع داده q است. 

بنابراین در اینجا صف ما است. این یک ساختار است. این شامل سه عضو یا سه زمینه ها، آرایه ای از ظرفیت اندازه. در این مورد، ظرفیت 10 است. و این آرایه است رفتن به برگزاری اعداد صحیح است. در سبز جلوی صف ما است، عنصر بعدی را حذف شود، و با رنگ قرمز خواهد بود که اندازه صف، چگونه بسیاری از عناصر در حال حاضر موجود در صف. بنابراین اگر ما می گویند برابر q.front 0، و اندازه q.size برابر 0-- ما در حال قرار دادن 0s و به کسانی که در زمینه. و در این نقطه، ما بسیار است آماده برای شروع کار با صف ما. 

پس از عمل اول ما می توانیم انجام است به نوبت چیزی، برای اضافه کردن یک عنصر جدید به در پایان از صف. خب چه چیزی ما نیاز به در حالت کلی انجام دهد؟ خب این تابع نوبت نیازهای به قبول یک اشاره گر به صف ما. باز هم، اگر ما اعلام کرده بود صف ما در سطح جهان، ما نمی خواهد نیاز به انجام این لزوما، اما به طور کلی، ما نیاز به قبول اشاره گر در ساختار داده مانند این، به دلیل غیر این صورت، ما در حال value-- ما در حال عبور عبور در نسخه از صف، و بنابراین ما در واقع در حال تغییر نیست صف که ما قصد داریم به تغییر است. 

نکته دیگر آن نیاز به انجام است قبول یک عنصر داده از نوع مناسب. باز هم، در این مورد، آن را رفتن به اعداد صحیح، اما شما می توانید خودسرانه اعلام نوع داده به عنوان ارزش و استفاده از این به طور کلی. که عنصر ما می خواهیم به نوبت است، ما می خواهیم برای اضافه کردن به انتهای صف. پس از آن ما واقعا می خواهید قرار است که داده ها را در صف. در این مورد، قرار دادن آن در محل صحیح از آرایه ما، و پس از آن ما می خواهیم برای تغییر اندازه از صف، چگونه بسیاری از عناصر ما در حال حاضر داشته باشد. 

بنابراین اجازه دهید آغاز شده است. در اینجا این است، دوباره، که به طور کلی اعلان تابع فرم آنچه در نوبت قراردادن ممکن است مانند نگاه. و در اینجا ما به. بیایید تعداد نوبت 28 به صف. بنابراین چه می خواهیم کاری انجام دهید؟ خوب، جلوی صف ما در 0، و به اندازه صف ما است در 0، و بنابراین ما احتمالا خواهید برای قرار دادن تعداد 28 در تعداد عنصر آرایه 0، درست است؟ بنابراین ما در حال حاضر قرار داده ام که در آن وجود دارد. بنابراین در حال حاضر چه چیزی نیاز داریم را تغییر دهید؟ ما نمی خواهیم به تغییر جلوی صف، چرا که ما می خواهند بدانند چه عنصر ما ممکن است نیاز به dequeue بعد. بنابراین به این دلیل ما باید جلو وجود دارد مرتب کردن بر اساس یک شاخص از آنچه است قدیمی ترین چیزی که در آرایه. خوب قدیمی ترین چیزی که در آرایه در واقع، تنها چیزی که در آرایه سمت راست now-- 28 است، که در محل آرایه 0. بنابراین ما نمی خواهید تغییر این تعداد سبز، چرا که از قدیمی ترین عنصر است. در عوض، ما می خواهیم به تغییر اندازه. بنابراین در این مورد، ما افزایش اندازه به 1. 

در حال حاضر یک نوع کلی از ایده که در آن عنصر بعدی است که برای رفتن در یک صف است برای اضافه کردن این دو عدد با هم، جلو و اندازه، و به شما بگویم که در آن بعدی عنصر در صف است که برای رفتن. پس به شماره دیگر نوبت. بیایید نوبت 33. بنابراین 33 است که برای رفتن به محل آرایه 0 به علاوه 1. بنابراین در این مورد، آن را برای رفتن به محل آرایه 1، و در حال حاضر به اندازه صف ما 2 است. 

باز هم، ما در حال تغییر نیست جلوی صف ما، چون 28 است که هنوز هم قدیمی ترین عنصر، و ما می خواهید to-- هنگامی که ما در نهایت به dequeuing، از بین بردن عناصر از این صف، ما می خواهند بدانند که در آن از قدیمی ترین عنصر است. و بنابراین ما همیشه نیاز به حفظ برخی نشانه های که در آن است. بنابراین این چیزی است که وجود دارد برای 0. این چیزی است که مقابل وجود دارد برای. 

بیایید در نوبت قراردادن یک عنصر، 19. من مطمئن هستم که شما می توانید حدس بزنید هستم که در آن 19 است که برای رفتن. آن را به رفتن به محل آرایه شماره 2. که 0 به علاوه 2 است. و در حال حاضر به اندازه صف ما 3 است. در حال حاضر 3 عناصر در آن است. بنابراین اگر ما به بود، و ما قصد داریم به در حال حاضر، نوبت عنصر دیگری، آن را به محل آرایه شماره 3، و اندازه صف ما می شود 4. بنابراین ما در حال حاضر چند عنصر را enqueued است. حالا اجازه دهید شروع به آنها را حذف کنید. اجازه دهید آنها را از صف dequeue. 

بسیار شبیه به موسیقی پاپ، که نوعی از آنالوگ از این آمدن، dequeue نیاز به پذیرش یک اشاره گر به queue-- دوباره، مگر اینکه آن را در سطح جهانی اعلام کرد. حالا ما می خواهیم به تغییر محل از جلوی صف. این جایی است که آن را از می آید را به بازی، که متغیر جلو، چرا که یک بار ما را حذف یک عنصر، ما می خواهیم این حرکت را به قدیمی ترین عنصر بعدی. 

پس ما می خواهیم به کاهش اندازه صف، و پس از آن ما می خواهیم برای بازگشت به ارزش که از صف حذف شد. باز هم، ما نمی خواهیم به آن را فقط دور بیندازید. ما احتمالا می استخراج آن را از queue-- ما dequeuing چون ما در مورد آن اهمیت می دهند. بنابراین ما می خواهیم از این تابع برای بازگشت یک عنصر داده ها از ارزش نوع. باز هم، در این مورد، مقدار صحیح است. 

بنابراین در حال حاضر اجازه دهید چیزی dequeue. بیایید یک عنصر از صف حذف. اگر ما می گویند INT x برابر و Q، علامت q-- دوباره که یک اشاره گر به این اطلاعات Q است structure-- چه عنصر در حال رفتن به dequeued شود؟ در این مورد، به دلیل آن را برای اولین بار در، اولین بار ساختار داده ها، FIFO، اولین چیزی که ما را به این قرار صف 28 بود، و بنابراین در این مورد، ما در حال رفتن به 28 از صف، 19، است که آنچه ما را انجام داده اند اگر این یک پشته بود. ما در حال رفتن به 28 از صف. 

مشابه آنچه که ما با انجام یک پشته، ما در واقع نیست رفتن به حذف 28 از صف خود را، ما فقط رفتن به نوع از تظاهر آن است وجود ندارد. طوری که آن را به ماندن وجود دارد در حافظه است، اما ما فقط در حال رفتن به نوع آن را با حرکت چشم پوشی دو رشته دیگر داده Q ما ساختار. ما در حال رفتن به تغییر جلو. Q.front در حال حاضر به رفتن 1، چرا که در حال حاضر قدیمی ترین عنصر در دارند ما صف، چرا که ما در حال حاضر حذف این 28، که قدیمی ترین عنصر سابق بود. 

و در حال حاضر، ما می خواهیم به تغییر اندازه صف به دو عنصر به جای سه. در حال حاضر به یاد داشته باشید قبل از من گفت: هنگامی که ما می خواهید برای اضافه کردن عناصر به صف، ما آن را در یک مکان به آرایه قرار که در مجموع از جلو و اندازه است. بنابراین در این مورد، ما هنوز هم قرار دادن آن، عنصر بعدی در صف، به محل آرایه 3، و خواهیم دید که در یک ثانیه. 

بنابراین ما در حال حاضر dequeued به ما اولین عنصر از صف. اجازه دهید دوباره آن را انجام. بیایید یکی دیگر از حذف عنصر از صف. در مورد، در حال حاضر قدیمی ترین عنصر آرایه محل 1 است. این چیزی است که q.front ما می گوید. جعبه سبز رنگ است که ما می گوید که که قدیمی ترین عنصر است. و به این ترتیب، X تبدیل خواهد شد 33. ما فقط می خواهیم نوع فراموش که 33 در آرایه وجود دارد، و ما در حال حاضر، می گویم که قدیمی ترین عنصر جدید در صف در محل آرایه 2، و به اندازه از صف، تعدادی از عناصر ما باید در صف، 1 است. حالا اجازه دهید چیزی نوبت، و من مرتب سازی بر اساس این دور دوم پیش به، اما اگر ما خواهید برای قرار دادن 40 به صف، که در آن 40 برای رفتن؟ خوب ما شده است از قرار دادن آن در q.front علاوه صف اندازه، و پس از آن را حس می کند در واقع به قرار دادن 40 در اینجا. حالا توجه کنید که در برخی از نقطه، ما قصد داریم برای رسیدن به پایان آرایه ما داخل Q، اما پژمرده 28 و 33-- آنها در واقع هستید، از لحاظ فنی فضاهای باز، درست است؟ و به این ترتیب، ما ممکن است eventually-- که حکومت اضافه کردن این دو together-- ما در نهایت ممکن است نیاز به وزارت دفاع به اندازه ظرفیت بنابراین ما می توانیم در اطراف بپیچید. 

بنابراین اگر ما به عنصر گرفتن شماره 10، اگر ما جایگزین کردن آن در عنصر شماره 10، ما می خواهم در واقع آن را در محل آرایه 0. و اگر ما از رفتن به شد آرایه location-- ببخشید، اگر ما آنها را باهم جمع، و ما به شماره کردم 11 می شود که در آن ما باید برای قرار دادن آن را، که در این آرایه وجود ندارد این امر می تواند بیرون رفتن از مرزهای. ما می تواند به 10 وزارت دفاع و قرار آن را در محل آرایه 1. بنابراین این که چگونه صف کار می کنند. آنها همیشه در حال رفتن به سمت چپ بروید از به راست و احتمالا حدود بپیچید. و شما می دانید که آنها اگر در اندازه کامل، که جعبه قرمز، به ظرفیت برابر می شود. و به این ترتیب پس از 40 به اضافه شده صف، به خوبی آنچه که ما باید انجام دهید؟ خب، قدیمی ترین عنصر در صف هنوز 19، بنابراین ما نمی خواهید به تغییر جلوی صف، اما در حال حاضر ما دو عناصر در صف، و بنابراین ما می خواهم به افزایش اندازه ما 1-2. 

که تقریبا آن را با کار با صف مبتنی بر آرایه، و شبیه به پشته، نیز وجود دارد یک راه برای پیاده سازی یک صف به عنوان یک لیست پیوندی. حال اگر این نوع ساختار داده به نظر می رسد برای شما آشنا، آن است. این یک لیست تنهایی مرتبط نیست، آن را به یک لیست مضاعف مرتبط است. و در حال حاضر، به عنوان یک کنار، آن است که در واقع ممکن است برای پیاده سازی یک صف به عنوان یک لیست تنهایی مرتبط، اما من از نظر تجسم فکر می کنم، آن را در واقع ممکن است به نظر کمک این به عنوان یک لیست مضاعف مرتبط. اما قطعا ممکن است به انجام این کار به عنوان یک لیست تنهایی مرتبط. 

بنابراین اجازه دهید یک نگاهی به این ممکن است مانند نگاه. اگر ما می خواهیم به enquue-- بنابراین در حال حاضر، دوباره ما تعویض به یک لیست مرتبط مدل مبتنی بر اینجا. اگر ما می خواهیم به نوبت، ما می خواهیم برای اضافه کردن یک عنصر جدید، به خوبی چه چیزی ما باید انجام دهید؟ خب، اول از همه، به دلیل ما در حال اضافه به پایان و از بین بردن آغاز، ما احتمالا می خواهید برای حفظ اشاره گر به هر دو سر و دم از لیست پیوندی؟ دم بودن اصطلاح دیگری برای در پایان از لیست پیوندی، آخرین عنصر در لیست پیوندی. و این احتمالا، دوباره، به نفع ما باشد اگر آنها از متغیر های جهانی هستند. اما در حال حاضر اگر ما می خواهیم برای اضافه کردن یک جدید عنصر چه چیزی ما باید انجام دهید؟ آنچه که ما فقط [؟ ملک؟] و یا به صورت پویا اختصاص گره جدید ما برای خودمان. و پس از آن، درست مثل زمانی که ما از هر اضافه عنصر به یک لیست مضاعف مرتبط ما، فقط باید به مرتب سازی بر اساس of-- این سه مرحله گذشته در اینجا فقط همه چیز در مورد حرکت هستند اشاره گر را در راه درست به طوری که این عنصر می شود به اضافه زنجیره ای بدون شکستن زنجیره ای و یا نوعی از اشتباه و یا داشتن یک نوع تصادف اتفاق می افتد که به موجب آن ما به طور تصادفی یتیم برخی از عناصر صف ما. در اینجا چیزی است که این ممکن است مانند نگاه. ما می خواهیم به اضافه کردن عنصر 10 تا پایان این صف. بنابراین قدیمی ترین عنصر در اینجا توسط سر شده است. که اولین چیزی که ما قرار داده است به این صف فرضی، در اینجا. و دم، 13، بیشتر است اخیرا عنصر اضافه شده است. و بنابراین اگر ما می خواهیم به نوبت 10 به این صف، ما می خواهیم به آن را پس از 13. و بنابراین ما قصد داریم به صورت پویا اختصاص فضا برای یک گره جدید و بررسی برای NULL مطمئن شوید ما یک شکست حافظه ندارد. پس از آن ما قصد داریم به مشخصات 10 به آن گره، و در حال حاضر ما باید مراقب باشید در مورد ما چگونه سازماندهی اشاره گر بنابراین ما شکستن زنجیره ای است. 

ما می توانیم درست قبلی 10 مجموعه برای برگشت به دم قدیمی، و از آنجا که '10 خواهد بود دم جدید در برخی از نقطه توسط تمام این زمان زنجیر به هم متصل، هیچ چیز را به آمده پس از 10 در حال حاضر. و به همین ترتیب بعدی اشاره گر 10 اشاره خواهد شد به تهی، و سپس بعد از انجام این کار، پس از این ما 10 عقب متصل به زنجیره ای، ما می توانیم سر قدیمی، و یا، بهانه ای را من، دم قدیمی از صف. پایان قدیمی از صف، 13، و آن را به 10 نقطه. و در حال حاضر، در این نقطه، ما باید تعداد 10 به این صف را enqueued. همه ما نیاز به انجام اکنون فقط حرکت دم به نقطه را به 10 به جای 13. 

Dequeuing است که در واقع بسیار شبیه به ظاهر از یک پشته است که اجرا به عنوان یک لیست پیوندی اگر شما این ویدئو پشته دیده می شود. همه ما باید انجام دهیم این است که شروع در آغاز، پیدا کردن عنصر دوم، آزاد عنصر اول، و پس از آن حرکت سر به نقطه را به عنصر دوم. احتمالا بهتر آن را تجسم فقط به فوق العاده در مورد آن روشن است. بنابراین در اینجا صف ما دوباره. 12 قدیمی ترین عنصر است در صف ما، سر. 10 جدید ترین عنصر است در صف ما، دم ما است. 

و تا زمانی که ما می خواهیم به dequeue یک عنصر، ما می خواهیم به حذف از قدیمی ترین عنصر است. پس چه کار کنیم؟ خوب ما مجموعه ای از یک اشاره گر پیمایش که شروع می شود در سر، و ما آن را به حرکت به طوری که آن اشاره به عنصر دوم این queue-- چیزی گفت TRAV برابر TRAV فلش در کنار، برای مثال، می TRAV وجود دارد حرکت به نقطه را به 15، که، پس از ما dequeue 12، و یا بعد از ما حذف 12، خواهد شد پس از آن تبدیل شدن به قدیمی ترین عنصر است. 

در حال حاضر ما رو نگه دارید در اولین عنصر از طریق سر اشاره گر و عنصر دوم از طریق TRAV اشاره گر. ما می توانید سر در حال حاضر رایگان، و سپس ما می توانید می گویند هیچ چیز می آید قبل از 15 نیست. بنابراین ما می توانیم تغییر 15 قبلی اشاره گر به اشاره به تهی، و ما بیش از حرکت سر. و ما به. در حال حاضر ما موفقیت dequeued 12، و در حال حاضر ما صف دیگری از 4 عناصر است. که تقریبا همه این است که به صف وجود دارد، هر دو مبتنی بر آرایه و مرتبط لیست بر اساس. من داگ لوید هستم. این CS 50 است.