سری آموزش های لیگ2 - ساختمان های داده - پشته و صف

سلام گلهای تو خونه، ACM ای های نمونه :)

با سری اول آموزش های کانتست های تمرینی - آموزشی لیگ دو انجمن ACM دانشگاه اصفهان همراه باشید. این سری آموزش ها با تمرکز و آموزش اجمالی روی ساختمان های داده شروع میشه و امیدواریم که با یاری شما ادامه دار و همچنین روز به روز مفید تر واقع بشه. ^_-

چطوری بیشترین بهره رو ببریم؟

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

خب دیگه بریم سر اصل مطلب.

ساختمان داده

یه توضیح خیلی کوچیک از اینکه اصلا ساختمان داده چی هست.

ساختمان داده، ساختمان هایی هستند که توشون داده است!

ساده بود نه؟ ^_^ در واقع، هر کدوم از این ساختمان ها، که توی خودشون داده نگه میدارن، قوانین خاص خودشونو دارن. مثلا شما ممکنه بتونین با دمپایی پلاستیکی وارد یه ساختمان مسکونی بشین، اما وارد یه ساختمان اداری قطعا نمیتونین :). همینطور، زمانی که میخوایم خونه بخریم، نمیریم یه دهنه مغازه توی یه پاساژ بخریم، بلکه متناسب با خواسته مون میریم تو ساختمان های مسکونی خونه میخریم. در نتیجه؛ دونستن این قوانین به ما کمک میکنه که توی مسائلی که باهاشون مواجه هستیم، متناسب با شرایط و خواسته های اون مسئله ساختمان داده ی مناسب رو انتخاب و درنتیجه الگوریتم بهینه تری ارائه بدیم.

پشته ( Stack )

یه ساختمان داده ی خیلی ساده و در عین حال پر کاربرد. توی این ساختمان داده شما اطلاعات رو روی سر هم وارد میکنین. مثل تعدادی بشقاب که اونهارو روی هم چیدین. اگر بشقاب بخواین بگذارین ( ما به بشقاب گذاشتن میگیم push )، روی سر بالاترین بشقاب میذارین ( ما به بالاترین بشقاب میگیم top ) و اگر هم بخوایم بشقاب برداریم همون بشقاب top رو برمیداریم ( ما به بشقاب برداشتن میگیم pop ). همین رو بهش میگن Last In Fist Out یعنی هر کی زودتر اومد تو، دیرتر میره بیرون، مثل اتوبوس های دانشگاه!

به طور کلی توی هر زبانی، ساختمان داده stack شامل function ها و متد های زیر میشه:

• push(value)
• pop()
• top()
• size()

میتونین توضیحات جامع و بهتری رو توی ویدیوی زیر که توسط احسان جلالی آماده شده ببینین:

مطالعه بیشتر

• از یکی از بهترین سایت ها در زمینه آموزش data structure سایت GeeksforGeeks هست که مطمئنا باهاش آشنایی دارین. مطالب آموزشی توی این سایت با اینکه معمولا خلاصه و روان هستن ، زیادن و آدم رو توی عمق یه موضوع میبرن. من خودم چند بار غرق شدم، یه بار هم چندتا کوسه دیدم! اما خب فقط کافیه که از کل مباحث، معرفی استک، کتابخانه استاندارد C++ رو مطالعه بکنین. البته مطالعه هرچه بیشتر مفید تر هست پس دنبال مطالب جذابی هم که میبینید برید.
• این مطلب هم خیلی خلاصه همراه با یه پیاده سازی خوب، پشته رو توضیح داده. این هم آموزش پشته توی سایت tutorialspoint هست. اگر حوصله ی خوندن دارین و همیشه سریع سراغ YouTube نمیرین، میتونه مناسب باشه ؛)
• خب دیگه مطالعه کافیه. بریم سوال حل کنیم. این سوال معرفی شده توی ویدیو ی بالاست که قول دادین اول خودتون بهش فکر کنین ^_-

اینها هم چند تا سوال خوب:

Stock Span , Next Greater Element, Hanoi Tower, Jumpy Humpy, Capital of Hills, Just Next, Street Parande, Compilers and Parsers

• و اینم یه problem set خوب از سوالات مربوط به stack

صف ( Queue )

همونطور که از اسمش معلومه، این ساختمان داده مثل یک صف نانوایی عمل میکنه. به همین دلیل بهش میگن First In First Out. پس هر عنصری که زوتر وارد بشه، زودتر نوبتش میشه که از صف خارج بشه.

برای صف از دوتا اشاره گر به نام های front یا head ( که بهمون میگن نفر اول توی کدوم خونه وایساده ) و rear یا tail ( که بهمون میگن نفر آخر توی کدوم خونه وایساده ) استفاده میکنیم.

صف کامپیوتریا، یه فرق کوچیکی با صف نونوایی داره. توی صف نونوایی وقتی نفر اول نونش رو بخره، همه چند قدم میرن جلو تا به نانوا نزدیک بشن و نوبتشون بشه. اما تو صف کامپیوتریا، وقتی نفر اول از صف رفت بیرون، بقیه تکون نمیخورن و نانوا ( نانوا همون اشاره گر head یا front هست ) چند قدم میاد جلو تا به نفر اول فعلی نزدیک بشه! چون حرکت دادن اشاره گر آسون تر از shift دادن همه ی عناصره. در نتیجه توی هر بار حذف یه عنصر از صف، front به اندازه یدونه خونه به rear نزدیک تر میشه. این باعث میشه که یه جایی بالاخره rear و front مقدارشون با هم برابر بشه و هر دو هم ته صف باشن. ( یعنی وقتی که همه آدامای توی صف نونشون رو خریدن ). اما دیگه نمیتونیم front رو برگردونیم سر جاش در نتیجه صف همیشه یکبار مصرفه و ما دوباره نمیتونیم پرش کنیم که خب دردسر بزرگیه.

برای حل این مشکل ساختمان داده ی صف حلقوی ( circular queue ) طراحی شده. تفاوت های کوچولوی زیادی با صف داره اما مهم ترین فرقش اینه که وقتی front رسید به آخر، اگه باز بخوایم عنصر اضافه کنیم، front میره اول صف.

به طور کلی توی هر زبانی، ساختمان داده queue شامل function ها و متد های زیر میشه:

• enqueue(value) یا push(value)
• dequeue() یا pop()
• size()
• empty()

میتونین توضیحات جامع و بهتری رو توی ویدیوی زیر که توسط رضا فرهنگ آماده شده ببینین:

مطالعه بیشتر

• میتونین بازم با GeeksforGeeks شروع کنیم. معرفی صف، کاربرد های صف، صف حلقوی رو از این سایت حتما مطالعه کنین. این هم آموزش صف از سایت tutorialspoint. اگه اون آموزش ها رو مطالعه کردین این آموزش خیلی نیازتون نمیشه اما چون کوتاهه توصیه میکنم نگاهی یهش بندازین.

بریم سراغ سوالات:

• یه problem set از سایت hackerearth از سوالات صف و همچنین یه problem set خیلی خوب با کلی سوال آسون تا سخت دیگه از سایت techiedelight.
• این سوال و این یکی سوال، یکمی با مباحث درخت توی گسسته آمیخته است که امیدوارم یادتون باشه.

معالعه ی بیشتر تر!

• پیاده سازی پشته با صف
• پیاده سازی صف با پشته
• مرتب سازی پشته
• یه ویدیو از پشته و صف
• صف اولویت
• مقایسه FIFO با LIFO

امیدوارم این مطلب تونسته باشه هم مفید هم جذاب باشه و ما هم شما رو هر چه سریعتر بالای جدول های مسابقات هفتگی ببینیم B)