ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

پشته STACK

 
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2973
Location: Tehran

PostPosted: Mon Apr 11, 2005 8:00 pm    Post subject: پشته STACK Reply with quote

يك پشته ساختمان داده اي خطي است كه در ان عمل اضافه كردن يا حذف عنصر تنها در يك انتهاي ان امكانپذير است باين ترتيب به پشته ها ليستهاي اخرين ورودي اولين خروجي 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 ميكنيم .
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2973
Location: Tehran

PostPosted: Mon Apr 11, 2005 8:02 pm    Post subject: Reply with quote

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

گزينه الف صحيح است .
Quote:
اگر رشته اعداد 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 و انگاه اعداد ديگر را بترتيب پاپ ميكنيم .
Quote:
3) كاراكترهاي رشته ABC را بترتيب وارد پشته اي ميشوند . كدام خروجي نميتواند درست باشد ؟
الف) ABC
ب) CBA
ج) CAB
د)ACB
پاسخ گزينه ج است .
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2973
Location: Tehran

PostPosted: Mon Apr 18, 2005 8:48 pm    Post subject: Reply with quote

Quote:
براي محاسبه عبارت 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 پوش عمليات انجام شد .
Back to top
sameti
مهمون يكي دو روزه


Joined: 11 Apr 2008
Posts: 2
Location: tehran

PostPosted: Fri Apr 11, 2008 1:19 pm    Post subject: كمك و راهنمايي در زمينه‌ پشته Reply with quote

با سلام و خسته نباشيد خدمت شما دوست گرامي
من در ابتداي يادگيري در زمينه ساختمان داده‌ها هستم. ازتون مي‌خوام اگر براتون مقدور هست، چند تا سؤال حل شده در زمينه پشته‌ها برام بزاريد. متشكرم.
david_fubric@yahoo.com
Back to top
kami-filkosh
مهمون يكي دو روزه


Joined: 10 Nov 2008
Posts: 1
Location: Iran-Tabriz

PostPosted: Mon Nov 10, 2008 1:44 pm    Post subject: Reply with quote

سلام.من یه تازه واردم.کسی میتونه برنامه های مربوط به پشته رو برام بفرسته.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum