پشته stack

[Y@SiN]

يك پشته ساختمان داده اي خطي است كه در ان عمل اضافه كردن يا حذف عنصر تنها در يك انتهاي ان امكانپذير است باين ترتيب به پشته ها ليستهاي اخرين ورودي اولين خروجي LIFO : Last In First Out نيز ميگويند . گاهي به پشته FILO نيز ميگويند .
يكي از كاربردهاي پشته ذخيره ادرس بازگشت و ساخت متغيرهاي محلي در صدا زدن توابع است .
در ابتداي كار با پشته top به عنصر صفرام پشته اشاره ميكند .
يك پشته ليستي از عناصر است كه در آن هر عنصر را ميتوان تنها از يك انتها موسوم به بالاي پشته حذف يا اضافه كرد يعني عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
نقطه اي كه در ان ميتوان اطلاعات را وارد پشته يا از ان خارج كرد مهمترين نقطه پشته است كه به بالاي پشته با نام TOP شناخته ميشود .
بنابراين عناصر به ترتيب عكسي كه وارد پشته ميشوند از پشته حذف ميشوند .
براي وارد كردن اطلاعات به پشته از عملي به نام PUSH استفاده ميكنيم و براي حذف اطلاعات از ان از POP استفاده ميكنيم .
براي سهولت كار با پشته ها انها را با ليست يكطرفه يا آرايه خطي نشان ميدهند .
براي PUSH كردن يك عنصر در پشته ميتوانيم از پراسيجري به نام PUSH استفاده كنيم كه داراي ورودي هاي مانند نام پوشه (STACK) و نقطه بالايي TOP و حداكثر اندازه پشته و متغيري كه قرار است وارد پشته شود :

PROCEDURE PUSH(stackname,topplace,sizeofstack,itemForAdd)
1. [if stack is available ? overflow ]
if topplace=sizeofstack
then write(‘OverFlow’)
exit
2. [increase TOP]
top:=top+1
3.[insert item]
s[top]:=itemForAdd
4.[finished]
exitدر پراسيجر بالا ابتدا براي انكه اشتباها سرريز overflow از پشته رخ ندهد بايد چك كنيم كه بالاترين نقطه top در كجاست ؟ ايا امكان دارد يك مقدار به ان اضافه شود در حاليكه از سايز پشته بالاتر نرود ؟
اگر پشته اماده دريافت باشد به گام دوم برنامه فوق ميرويم وگرنه با تايپ شدن پيغام overflow از پراسيجر خارج ميشويم .
در گام دوم پراسيجر يك مقدار به top استفاده ميكنيم تا اشاره به مكاني بكند كه قرار است داده ما به ان وارد شود .
در گام سوم عنصر ما وارد پشته ميشود .
در گام چهارم به نقطه پاياني ميرسيم و سپس از برنامه خارج ميشويم .
براي حذف يك عنصر از پشته از تابع POP استفاده ميكنيم :


POP(stackname,top,sizeofstack,element)
1.[underflow?]
if top=0
then write(‘underflow!’)
return(null)
2.[pickup elemnt]
y:=s[top]
3.[decrease TOP]
top:=top-1
4.[finished]
return(y)
در تابع فوق همانطور كه ميبينيد باز هم در اولين گام چك كرديم كه ايا ارايه عنصري دارد ؟ اگر ندارد اشتباها نميتوانيم عنصري از ان بردارد بنابراين از خطاي احتمالي زيرريز underflow جلوگيري كرديم . بصورت قرار دادي ميتوانيم در خروجي تابع هرگاه پشته ما خالي بود هر مقداري بازگردانيم كه در اينجا بصورت قراردادي مقدار پوچ null را بازگردانيديم .
پس از انكه مطمئن شديم پشته ما مقداري دارد ان مقداري كه اشاره گر top به ان اشاره ميكند را در متغيري محلي بنام y ميريزيم و سپس از مقدار top يكي كم ميكنيم .
و مقدار y را در نام تابع return ميكنيم .

[Y@SiN]

push و pop كردن به ترتيب به چه معناست ؟
الف) برداشتن عنصر بالايي پشته – گذاشتن عنصر جديد در پشته
ب) خالي كردن پشته – پركردن پشته
ج) ديدن عنصر بالايي پشته – برداشتن عنصر بالايي پشته
د) گذاشتن عنصر در پشته – خواندن عنصر بالايي پشته
گزينه الف صحيح است .

اگر رشته اعداد 1و3و4و5و7را بترتيب از سمت راست وارد پشته كنيم كداميك از خروجيهاي زير از اين پشته امكان پذير نيست ؟ ( خروجيها را از سمت راست بخوانيد )
الف) 7و5و4و3و1
ب) 1و3و7و5و4
ج) 1و7و3و5و4
د) 1و4و3و7و5

توضيح :‌ از انجايي كه اين گونه تست ها نياز به پيگيري و اكثرا عمليات زيادي نياز دارند . پيشنهاد ميكنم به جاي انكه بدلخواه گزينه اي را شروع به تست كنيد . از همان گزينه الف شروع به تست كردن صحت گزينه ها بكنيد . چراكه تجربه به من نشان داده است كه اصولا طراحان تست هاي استاندارد گزينه درست را در همان اوايل ميگذارند . در ضمن اگر از پايين شروع به تست بكنيد و به گزينه بالايي برسيد . سر جلسه شايد افسوس بخوريد كه چرا براي حل مساله از همان گزينه الف شروع نكرديد .
اين مساله براي دوستاني كه تا بحال تست هاي ساختمان داده ها را نزده اند كمي گيج كننده است . كه لازمه حل اين تست ها حل كردن يكي از انهاست . در اين گونه مساله ها محدوديت ها توسط مساله ذكر ميشوند . از ان پس شما ميتوانيد با كنار گذاشتن محدوديات به عمليات بپردازيد . در اين مساله محدوديت ما نحوه پوش كردن اطلاعات است . اطلاعات بايد بترتيب گفته شده در مساله پوش شوند . بنابراين محدوديتي در تعداد پوش ها نيست .
در ضمن درصورت مساله تست بالا يك توضيح اضافي به چشم ميخورد كه :‌ داده ها را از سمت راست بترتيب وارد ميكنيم . اگر بگويد داده ها را بترتيب وارد ميكنيم . خود شما بايد حدس بزنيد كه داده ها از سمت راست وارد ميشوند چرا كه بين اعداد”و” امده است . و ترتيب خواندن انها در زبان فارسي از سمت راست به چپ خواهد بود . نمونه تست ديگري در زير براي اين نكته خواهيم اورد .
مساله ساده ايست . براي حل ان بايد به داده هاي ان توجه كنيد . رشته اعداد قرار است بترتيب داده شده يعني به ترتيب 75431 وارد پشته شوند . با استفاده از دستور PUSH يكي از داده ها را وارد پشته ميكنيم . اگر لازم شد ميتوانيم انرا POP كنيم وگرنه باز هم داده بعدي را PUSH ميكنيم . بازهم توجه ميكنيم كه ايا قرار است كه داده اي را POP كنيم يا خير . بهمين ترتيب تك تك گزينه ها را چك ميكنيم .
گزينه الف كه واضح و صريح است .
گزينه ب : ابتدا 1 را به پشته ميفرستيم دوباره انرا پاپ ميكنيم . ميرويم سراغ اعداد باقيمانده 7543
براي پاپ كردن 3 انرا وارد پشته ميكنيم ( پوش)‌ و سپس پاپ ميكنيم . اعداد باقيمانده 754 هستند . براي پاپ كردن 7 طبق خواسته مساله اول بايد 3 سپس 4 و بعد از ان 5 و در نهايت 7 وارد پشته شود . بنابراين سه عدد ديگر را بترتيب گفته شده در مساله به پشته پوش ميكنيم . سپس 7 را پوش ميكنيم . حال چه بخواهيم چه نخواهيم مجبوريم بعد از پاپ كردن 7 عدد 5 و بدنبال ان عدد 4 را پاپ كنيم . بنابراين در اين گزينه مشكلي به چشم نخورد .
گزينه ج : ابتدا يك را مانند گزينه قبلي پوش ميكنيم . سپس انرا پاپ ميكنيم . نوبت به 7 رسيده است . براي پاپ كردن 7 طبق خواسته مساله بايد ديگر اعداد بترتيب گفته شده وارد پشته شوند يعني بترتيب 543 و بعد از ان 7 را پوش ميكنيم . حال بايد 7 را پاپ كنيم . بنابراين 1و7 بترتيب در خروجي امده اند . اما همانطور كه در پشته داريم نوبت به پاپ شدن 5 است اما در اين گزينه از ما خواسته شده است كه 3 را پاپ كنيم . كه از اين نقطه متوجه ميشويم كه اين گزينه غلط است .
گزينه دال :‌ براي پاپ كردن يك همانطور كه در بالا نيز گفته شد انرا ابتدا در پشته بتنهايي پوش ميكنيم و سپس انرا پاپ ميكنيم . بعد از ان بايد 4 به پشته پوش شوند اما مساله از ما ميخواهد كه ابتدا 3 را پوش كنيم و سپس 4 را بنابراين طبق خواسته مساله پيش ميرويم . بعد از پاپ كردن 4 ميبينيم گزينه چه ميخواهد از ما ؟ بله عدد 3 را ميخواهد ( ميتوانست عدد ديگري نيز بخواهد ) چون عدد سه يكبار به پشته پوش شده است بنابراين فقط با پاپ كردن ان از پشته به مرحله بعد ميرويم . گزينه عدد 7 را از ما ميخواهد . بنابراين ان دو عدد ديگر را بترتيب گفته شده در مساله وارد پشته سپس عدد 7 و انگاه اعداد ديگر را بترتيب پاپ ميكنيم .
:3) كاراكترهاي رشته ABC را بترتيب وارد پشته اي ميشوند . كدام خروجي نميتواند درست باشد ؟
الف) ABC
ب) CBA
ج) CAB
د)ACBپاسخ گزينه ج است .

[Y@SiN]

push و pop كردن به ترتيب به چه معناست ؟
الف) برداشتن عنصر بالايي پشته – گذاشتن عنصر جديد در پشته
ب) خالي كردن پشته – پركردن پشته
ج) ديدن عنصر بالايي پشته – برداشتن عنصر بالايي پشته
د) گذاشتن عنصر در پشته – خواندن عنصر بالايي پشته
گزينه الف صحيح است .
2 -اگر رشته اعداد 1و3و4و5و7را بترتيب از سمت راست وارد پشته كنيم كداميك از خروجيهاي زير از اين پشته امكان پذير نيست ؟ ( خروجيها را از سمت راست بخوانيد )
الف) 7و5و4و3و1
ب) 1و3و7و5و4
ج) 1و7و3و5و4
د) 1و4و3و7و5
توضيح :‌ از انجايي كه اين گونه تست ها نياز به پيگيري و اكثرا عمليات زيادي نياز دارند . پيشنهاد ميكنم به جاي انكه بدلخواه گزينه اي را شروع به تست كنيد . از همان گزينه الف شروع به تست كردن صحت گزينه ها بكنيد . چراكه تجربه به من نشان داده است كه اصولا طراحان تست هاي استاندارد گزينه درست را در همان اوايل ميگذارند . در ضمن اگر از پايين شروع به تست بكنيد و به گزينه بالايي برسيد . سر جلسه شايد افسوس بخوريد كه چرا براي حل مساله از همان گزينه الف شروع نكرديد .
اين مساله براي دوستاني كه تا بحال تست هاي ساختمان داده ها را نزده اند كمي گيج كننده است . كه لازمه حل اين تست ها حل كردن يكي از انهاست . در اين گونه مساله ها محدوديت ها توسط مساله ذكر ميشوند . از ان پس شما ميتوانيد با كنار گذاشتن محدوديات به عمليات بپردازيد . در اين مساله محدوديت ما نحوه پوش كردن اطلاعات است . اطلاعات بايد بترتيب گفته شده در مساله پوش شوند . بنابراين محدوديتي در تعداد پوش ها نيست .
در ضمن درصورت مساله تست بالا يك توضيح اضافي به چشم ميخورد كه :‌ داده ها را از سمت راست بترتيب وارد ميكنيم . اگر بگويد داده ها را بترتيب وارد ميكنيم . خود شما بايد حدس بزنيد كه داده ها از سمت راست وارد ميشوند چرا كه بين اعداد”و” امده است . و ترتيب خواندن انها در زبان فارسي از سمت راست به چپ خواهد بود . نمونه تست ديگري در زير براي اين نكته خواهيم اورد .
مساله ساده ايست . براي حل ان بايد به داده هاي ان توجه كنيد . رشته اعداد قرار است بترتيب داده شده يعني به ترتيب 75431 وارد پشته شوند . با استفاده از دستور PUSH يكي از داده ها را وارد پشته ميكنيم . اگر لازم شد ميتوانيم انرا POP كنيم وگرنه باز هم داده بعدي را PUSH ميكنيم . بازهم توجه ميكنيم كه ايا قرار است كه داده اي را POP كنيم يا خير . بهمين ترتيب تك تك گزينه ها را چك ميكنيم .
گزينه الف كه واضح و صريح است .
گزينه ب : ابتدا 1 را به پشته ميفرستيم دوباره انرا پاپ ميكنيم . ميرويم سراغ اعداد باقيمانده 7543
براي پاپ كردن 3 انرا وارد پشته ميكنيم ( پوش)‌ و سپس پاپ ميكنيم . اعداد باقيمانده 754 هستند . براي پاپ كردن 7 طبق خواسته مساله اول بايد 3 سپس 4 و بعد از ان 5 و در نهايت 7 وارد پشته شود . بنابراين سه عدد ديگر را بترتيب گفته شده در مساله به پشته پوش ميكنيم . سپس 7 را پوش ميكنيم . حال چه بخواهيم چه نخواهيم مجبوريم بعد از پاپ كردن 7 عدد 5 و بدنبال ان عدد 4 را پاپ كنيم . بنابراين در اين گزينه مشكلي به چشم نخورد .
گزينه ج : ابتدا يك را مانند گزينه قبلي پوش ميكنيم . سپس انرا پاپ ميكنيم . نوبت به 7 رسيده است . براي پاپ كردن 7 طبق خواسته مساله بايد ديگر اعداد بترتيب گفته شده وارد پشته شوند يعني بترتيب 543 و بعد از ان 7 را پوش ميكنيم . حال بايد 7 را پاپ كنيم . بنابراين 1و7 بترتيب در خروجي امده اند . اما همانطور كه در پشته داريم نوبت به پاپ شدن 5 است اما در اين گزينه از ما خواسته شده است كه 3 را پاپ كنيم . كه از اين نقطه متوجه ميشويم كه اين گزينه غلط است .
گزينه دال :‌ براي پاپ كردن يك همانطور كه در بالا نيز گفته شد انرا ابتدا در پشته بتنهايي پوش ميكنيم و سپس انرا پاپ ميكنيم . بعد از ان بايد 4 به پشته پوش شوند اما مساله از ما ميخواهد كه ابتدا 3 را پوش كنيم و سپس 4 را بنابراين طبق خواسته مساله پيش ميرويم . بعد از پاپ كردن 4 ميبينيم گزينه چه ميخواهد از ما ؟ بله عدد 3 را ميخواهد ( ميتوانست عدد ديگري نيز بخواهد ) چون عدد سه يكبار به پشته پوش شده است بنابراين فقط با پاپ كردن ان از پشته به مرحله بعد ميرويم . گزينه عدد 7 را از ما ميخواهد . بنابراين ان دو عدد ديگر را بترتيب گفته شده در مساله وارد پشته سپس عدد 7 و انگاه اعداد ديگر را بترتيب پاپ ميكنيم .
:3) كاراكترهاي رشته ABC را بترتيب وارد پشته اي ميشوند . كدام خروجي نميتواند درست باشد ؟
الف) ABC
ب) CBA
ج) CAB
د)ACBپاسخ گزينه ج است .

[Y@SiN]

براي محاسبه عبارت A+B^(A+B)*(A-B) ابتدا ان را به postfix تبديل كرده و از پشته استفاده ميكنيم . براي اينكار پشته مورد نياز حداقل چند خانه بايد داشته باشد و چند بار عمل push در ان صورت ميگيرد ؟
1)4 خانه – 10 بار
2)5خانه – 8 بار
3)4خانه – 8بار4)5 خانه – 10 بار
صورت مساله خواسته است عبارت را ابتدا به postfix تبديل كنيم . با استفاده از روشي كه قبلا گفتيم !
روش تستي تبديل اين عبارات به Postfix انستكه كل عبارت را با توجه به اولويتها پرانتز گذاري كنيد . مانند زير
(A+(B^(A+B))*(A-B))پس از پرانتزگذاري هركدام از عملگر ها را به بيرون از پرانتز خود ببريد . چيزي شبيه به فرم زير :
(A(B(AB)+)^(AB)-)*)+حال پرانتزها را پاك كنيد :
ABAB+^AB-*+
عبارت شما POSTFIX شد .
حال ادامه سوال را ميخوانيم .
حداكثر خانه هايي كه پشته ميتواند داشته باشد به تعداد كاراكترهاي ماست . كه در اينجا 11 تا هستند . حداكثر تعداد پوش هم ظاهرا 11 تاست .
اما شروع به پوش كردن عبارت POSTFIX ميكنيم . 4 كاراكتر اول هر كدام يك خانه اشغال ميكنند . بنابراين 4 بار پوش كرديم در 4 خانه . حال به عملگر + ميرسيم . عملگر +‌ بايد بين a و b قرار بگيرد . بنابراين در بالاترين خانه پشته عبارت a+b قرار ميگيرد كه يك خانه از چهار خانه اشغال شده در مرحله قبل ازاد ميشود . حال توان وارد ميشود . توان بين b و a+b قرار ميگيرد . كه بالاترين نقطه پشته b^(a+b) ميشود . ( توجه داشته باشيد كه در محاسبات ديگر مقدار a+b به اين صورت نيست كه يك عدد خواهد بود ) بنابراين يك خانه ديگر از پشته خالي ميشود . و تنها دو خانه از پشته اشغال شده است .
حال A و B وارد پشته ميشوند . كه در نتيجه چهار خانه دو باره اشغال مشوند . سپس – وارد ميشود كه يك خانه پشته خالي ميشود و منفي بين A و B قرار ميگيرد . در نتيجه بالاترين نقطه پشته ميشود (A-B) حال * وارد ميشود كه اين ضرب بين b^(a+b) و (a-b) قرار ميگيرد . كه باعث ميشود يك خانه ديگر از پشته خالي شود : (b^(a+b))*(a-b) اگر دقت كرده باشيد اكنون دو خانه پشته اشغال شده است . خانه اول اولين A و خانه دوم مقداري كه در نقطه top پشته است وجود دارد يعني :‌ (b^(a+b))*(a-b)
اگر به نكته اي كه هميشه مطرح است توجه نكنيد در اينجا + را به پشته پوش ميكنيد و در نتيجه در پشته مقدار a+(b^(a+b))*(a-b)) را خواهيد داشت و نتيجاتا 11 پوش خواهيد داشت . در حاليكه اخرين عمليات به پشته پوش نميشود بلكه از پشته خارج ميشود .
بنابراين در اين مساله تنها به 4 خانه پشته احتياج داشتيم و با 10 پوش عمليات انجام شد .

[elham67to]

:79:سلام کسی جواب اینو میدونه؟
برنامه ای بنویسید که عبارت میان وندی ورودی را با استفاده از پشته به عبارت پسوندی تبدیل کند:169:

[Borna66]

:79:سلام کسی جواب اینو میدونه؟
برنامه ای بنویسید که عبارت میان وندی ورودی را با استفاده از پشته به عبارت پسوندی تبدیل کند:169:

سلام
این برنامه خیلی آسونه ! اگر کمی تجربه تو C داری خیلی راحت خودت میتونی بنویسیش . اینم الگوریتمش :

- دو تا پشته در نظر میگیریم .
2- نماد های عبارت infix رو از آخر به اول بررسی می کنیم بشکل زیر :

1) اگر نماد پرانتز بسته یا عملگر بود اونو توی پشته شماره 1 میزاریم
2) اگر نماد عملوند بود در پشته شماره 2 قرار میدیم
3) اگر نماد پرانتز باز بود ، از پشته 1 دوتا نماد برمیداریم . هر کدوم از اونها که عملگر بود به پشته دوم اضافه می کنیم .


3-این عمل رو تا جایی که به اول عبارت infix برسیم تکرار می کنیم .
4- در پایان مقدار موجود در پشته دوم رو معکوس می کنیم . در این زمان به جواب prefix می رسیم .

روزگار خوش

[emprator_01]

سلام
این برنامه خیلی آسونه ! اگر کمی تجربه تو c داری خیلی راحت خودت میتونی بنویسیش . اینم الگوریتمش :

- دو تا پشته در نظر میگیریم .
2- نماد های عبارت infix رو از آخر به اول بررسی می کنیم بشکل زیر :

1) اگر نماد پرانتز بسته یا عملگر بود اونو توی پشته شماره 1 میزاریم
2) اگر نماد عملوند بود در پشته شماره 2 قرار میدیم
3) اگر نماد پرانتز باز بود ، از پشته 1 دوتا نماد برمیداریم . هر کدوم از اونها که عملگر بود به پشته دوم اضافه می کنیم .


3-این عمل رو تا جایی که به اول عبارت infix برسیم تکرار می کنیم .
4- در پایان مقدار موجود در پشته دوم رو معکوس می کنیم . در این زمان به جواب prefix می رسیم .

روزگار خوش


اگه با یه مثال توضیح بدی ممنون میشم

[golsa72]

سلام اگه میشه برنامه عبارت میانوندی به زبان c# رو بهم بگین ممنون میشم.:79::79:

[Borna66]

سلام اگه میشه برنامه عبارت میانوندی به زبان c# رو بهم بگین ممنون میشم.:79::79:
با سلام

دوست گرامي شرمنده.
درخواست شما مقدور نيست به علت مطرح كردن در جاي نامناسب
روزگار خوش

[meysam0241]

کسی میتونه به این سوال پاسخ بده؟
تعداد حالت های مختلفی که میتوان برای خروج اعداد از پشته نوشت ؟(مثال :در 6 تا عدد 24 حالت وجود دارد)
یه فرمول میخوام.