آبجی
15th February 2010, 02:08 PM
يك پشته ساختمان داده اي خطي است كه در ان عمل اضافه كردن يا حذف عنصر تنها در يك انتهاي ان امكانپذير است باين ترتيب به پشته ها ليستهاي اخرين ورودي اولين خروجي LIFO : Last In First Out نيز ميگويند . گاهي به پشته FILO نيز ميگويند .
يكي از كاربردهاي پشته ذخيره ادرس بازگشت و ساخت متغيرهاي محلي در صدا زدن توابع است .
در ابتداي كار با پشته top به عنصر صفرام پشته اشاره ميكند .
يك پشته ليستي از عناصر است كه در آن هر عنصر را ميتوان تنها از يك انتها موسوم به بالاي پشته حذف يا اضافه كرد يعني عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
نقطه اي كه در ان ميتوان اطلاعات را وارد پشته يا از ان خارج كرد مهمترين نقطه پشته است كه به بالاي پشته با نام TOP شناخته ميشود .
بنابراين عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
براي وارد كردن اطلاعات به پشته از عملي به نام PUSH استفاده ميكنيم و براي حذف اطلاعات از ان از POP استفاده ميكنيم .
براي سهولت كار با پشته ها انها را با ليست يكطرفه يا آرايه خطي نشان ميدهند .
براي PUSH كردن يك عنصر در پشته ميتوانيم از پراسيجري به نام PUSH استفاده كنيم كه داراي ورودي هاي مانند نام پوشه (STACK) و نقطه بالايي TOP و حداكثر اندازه پشته و متغيري كه قرار است وارد پشته شود
در پراسيجر بالا ابتدا براي انكه اشتباها سرريز overflow از پشته رخ ندهد بايد چك كنيم كه بالاترين نقطه top در كجاست ؟ ايا امكان دارد يك مقدار به ان اضافه شود در حاليكه از سايز پشته بالاتر نرود ؟
اگر پشته اماده دريافت باشد به گام دوم برنامه فوق ميرويم وگرنه با تايپ شدن پيغام overflow از پراسيجر خارج ميشويم .
در گام دوم پراسيجر يك مقدار به top استفاده ميكنيم تا اشاره به مكاني بكند كه قرار است داده ما به ان وارد شود .
در گام سوم عنصر ما وارد پشته ميشود .
در گام چهارم به نقطه پاياني ميرسيم و سپس از برنامه خارج ميشويم .
براي حذف يك عنصر از پشته از تابع POP استفاده ميكنيم
هرگاه پشته ما خالي بود هر مقداري بازگردانيم كه در اينجا بصورت قراردادي مقدار پوچ null را بازگردانيديم .
پس از انكه مطمئن شديم پشته ما مقداري دارد ان مقداري كه اشاره گر top به ان اشاره ميكند را در متغيري محلي بنام y ميريزيم و سپس از مقدار top يكي كم ميكنيم .
و مقدار y را در نام تابع return ميكنيم .
يكي از كاربردهاي پشته ذخيره ادرس بازگشت و ساخت متغيرهاي محلي در صدا زدن توابع است .
در ابتداي كار با پشته top به عنصر صفرام پشته اشاره ميكند .
يك پشته ليستي از عناصر است كه در آن هر عنصر را ميتوان تنها از يك انتها موسوم به بالاي پشته حذف يا اضافه كرد يعني عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
نقطه اي كه در ان ميتوان اطلاعات را وارد پشته يا از ان خارج كرد مهمترين نقطه پشته است كه به بالاي پشته با نام TOP شناخته ميشود .
بنابراين عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
براي وارد كردن اطلاعات به پشته از عملي به نام PUSH استفاده ميكنيم و براي حذف اطلاعات از ان از POP استفاده ميكنيم .
براي سهولت كار با پشته ها انها را با ليست يكطرفه يا آرايه خطي نشان ميدهند .
براي PUSH كردن يك عنصر در پشته ميتوانيم از پراسيجري به نام PUSH استفاده كنيم كه داراي ورودي هاي مانند نام پوشه (STACK) و نقطه بالايي TOP و حداكثر اندازه پشته و متغيري كه قرار است وارد پشته شود
در پراسيجر بالا ابتدا براي انكه اشتباها سرريز overflow از پشته رخ ندهد بايد چك كنيم كه بالاترين نقطه top در كجاست ؟ ايا امكان دارد يك مقدار به ان اضافه شود در حاليكه از سايز پشته بالاتر نرود ؟
اگر پشته اماده دريافت باشد به گام دوم برنامه فوق ميرويم وگرنه با تايپ شدن پيغام overflow از پراسيجر خارج ميشويم .
در گام دوم پراسيجر يك مقدار به top استفاده ميكنيم تا اشاره به مكاني بكند كه قرار است داده ما به ان وارد شود .
در گام سوم عنصر ما وارد پشته ميشود .
در گام چهارم به نقطه پاياني ميرسيم و سپس از برنامه خارج ميشويم .
براي حذف يك عنصر از پشته از تابع POP استفاده ميكنيم
هرگاه پشته ما خالي بود هر مقداري بازگردانيم كه در اينجا بصورت قراردادي مقدار پوچ null را بازگردانيديم .
پس از انكه مطمئن شديم پشته ما مقداري دارد ان مقداري كه اشاره گر top به ان اشاره ميكند را در متغيري محلي بنام y ميريزيم و سپس از مقدار top يكي كم ميكنيم .
و مقدار y را در نام تابع return ميكنيم .