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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

بنابراین این یک اعلان پاپ است ممکن است مانند وجود دارد در بالا سمت چپ نگاه کنید. این تابع برمی گرداند داده ها از ارزش نوع. باز هم ما با استفاده از اس ام اس اعداد صحیح در سراسر. و آن را یک اشاره گر به یک پشته به عنوان پذیرد بحث تنها آن و یا تنها پارامتر. پس چه شده است پاپ کاری انجام دهید؟ بیایید می گویند ما می خواهیم به حال پاپ یک عنصر خارج از بازدید کنندگان. بنابراین به یاد داشته باشید من گفت که پشته گذشته در، اولین بار، LIFO ساختمان داده. کدام عنصر است که به از پشته حذف شده باشد؟ آیا شما حدس می زنم 19؟ از آنجا که شما می شود، راست. 19 آخرین عنصر به اضافه شد پشته هنگامی که ما عناصر هل دادن در، و پس از آن را به رفتن به اولین عنصری است که می شود حذف خواهند شد. آن را به عنوان اگر ما گفت: 28 و پس از آن ما 33 در بالای آن قرار داده است، و ما 19 در بالا از آن قرار داده است. تنها عنصر ما می توانیم را خاموش 19 است. 

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

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

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

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

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

بنابراین در اینجا لیست پیوندی ما است. این به صورت همزمان شامل چهار عنصر است. و کاملا تر در اینجا ما پشته حاوی چهار عنصر است. و اجازه دهید بگویم ما اکنون می خواهیم فشار یک آیتم جدید بر روی این پشته. و ما می خواهیم به فشار یک جدید مورد که ارزش داده 12 است. خب چه می خواهیم کاری انجام دهید؟ خب اول ما قصد داریم به فضای از malloc، به صورت پویا اختصاص فضا برای یک گره جدید. و البته بلافاصله پس از ما را یک به malloc ما همیشه مطمئن شوید که به برای NULL را بررسی کنید، چرا که اگر ما مقدار null کردم بود به نوعی از مشکل وجود دارد. ما برای ارجاع دوباره به که تهی می خواهید اشاره گر و یا شما یک گسل SEG رنج می برند. این خوب نیست. بنابراین ما از گره malloced است. ما باید فرض کنیم ما موفقیت در اینجا بود. ما در حال رفتن به قرار دادن 12 به فیلد داده از آن گره. در حال حاضر شما را به یاد که از اشاره گر ما حرکت بعدی بنابراین ما شکستن زنجیره ای نیست؟ ما یک زن و شوهر از گزینه اینجا اما تنها کسی است که برای رفتن به امن این است که مجموعه اخبار اشاره گر به نقطه به نقطه سر قدیمی از لیست و یا چه به زودی خواهد بود رئیس قدیمی از لیست. و حالا که همه ما عناصر با هم زنجیر، ما فقط می توانید لیست حرکت به نقطه به همان محل می کند که جدید است. و ما در حال حاضر به طور موثر تحت فشار قرار دادند عنصر جدید را بر روی جلو از پشته. 

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

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

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

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