stack

[masoud58]

آیا کسی میدونه چه دلیلی داره که نحوه ذخیره سازی در پشته باید بصورت LIFO باشه ؟
حالا اگه FIFO باشه چه اشکالی پیش می یاد ؟
خودم فکر می کنم که به دستور PUSH و POP و رجیستر SP مربوطه

[ناصر منتظری]

پاسخ : stack

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

[masoud58]

پاسخ : stack

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

شاید سوالم یه کم مبتدیانس
میشه بیشتر توضیح بدید

[ناصر منتظری]

پاسخ : stack

شما می تونی یک قفسه رو در نظر بگیری که باید چند تا کتاب توش بزاری به صورت روی هم پس باید کتابها رو به ترتیب بزاری و شماره قرار گرفتن اونها رو بدونی و وقتی می خوای یک کتاب رو برداری باید ابتدا کتابی که روی همه کتاب ها قرار گرفته رو برداری و به همین ترتیب تا به کتاب مورد نظر برسی دقیقا همین اتفاق برای ذخیره اطلاعات رخ میده

[masoud58]

پاسخ : stack

شما می تونی یک قفسه رو در نظر بگیری که باید چند تا کتاب توش بزاری به صورت روی هم پس باید کتابها رو به ترتیب بزاری و شماره قرار گرفتن اونها رو بدونی و وقتی می خوای یک کتاب رو برداری باید ابتدا کتابی که روی همه کتاب ها قرار گرفته رو برداری و به همین ترتیب تا به کتاب مورد نظر برسی دقیقا همین اتفاق برای ذخیره اطلاعات رخ میده

به نظر شما چرا بایستی در پشته ترتیب برداشتن ( کتاب ها ) رعایت بشه ؟
به فرض اگه بخواهیم یه کتابی از وسط برداریم چه اتفاقی میفته ؟ یعنی اگه ترتیب برداشتن بهم بخوره چی میشه ؟
این ترتیب درج و بازیافت اهمیت خاصی داره ؟
البته ببخشید که گیر دادم
می خوام برام ملموس باشه و قانع بشم

[ناصر منتظری]

پاسخ : stack

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

[atige]

پاسخ : stack

خوب اگه فیفو بود که میشد Queue
نمیشد؟

[2012rostami]

پاسخ : stack

مثالهای قفس کتاب و انباری کاملاً گویای مطلب هست.
پشته مثه یه دفتر چرکنویس می مونه که پردازنده وقت نداره پاکنویسش کنه! سریع توش می نویسه و سریع ازش می خونه و پاکش می کنه برا دفعه بعد. در فراخوانی توابع و وقفه ها پشته با مقادیر رجیسترهای مهم برای پردازنده پر می شه و انتهای کار همه چی سرِ جای اول خودش برمی گیرده. متغیرهای محلی هر تابع هم درون پشته ذخیره می شه.
عموماً استفاده از پشته در اختیار خود پردازنده ست و برنامه نویس فقط حجم و آدرس شروعش رو اول برنامه تعیین می کنه. البته به لطف کامپایلرها، برنامه نویس این کارا رو هم لازم نیست انجام بده.
این تصور که بشه از پشته به عنوان یه جا برای نگهداری متغیرها استفاده کرد نادرسته. پشته محل قرارگیری متغیرهای عمومی برنامه نیست. اگر به زبان اسمبلی یا C در محتوای پشته تغییری ایجاد کنید پردازنده شما به احتمال بسیار زیاد هنگ می کنه! :rolleyes:

[masoud58]

پاسخ : stack

با تشکر از دوستانی که پاسخ دادند
همونطور که می دونیم در پشته با هر بار عمل PUSH از رجیستر SP دو واحد کم میشه
سوال دیگه اینکه چرا پشته بایستی از آخر به اول عمل ذخیره سازی رو انجام بده؟
خوب همین عمل LIFO از اول به آخر هم می تونه انجام بشه و به جای اینکه با هر بار عمل PUSH رجیستر SP دو واحد کم بشه به عکس دو واحد زیاد بشه
خوب این هم LIFO از اول به آخر میشه و دقیق هم کار می کنه
حدس خودم اینه که برای عدم همپوشانی CS و SS هست که عمل LIFO از آخر به اول هست
تا ببینیم نظر شما چیه

[mojalan]

پاسخ : stack

یه بار استادمون پشته رو یا stack قاطی کرد گفت پشتک :biggrin:
ولی در کل پشته یا همون stack یا LIFO یه مفهوم در نحوه ذخیره سازی داده هاست ؛ نحوه پیاده سازی این ذخیره کننده (مثل اینکه میگیم چرا از sp دو واحد کم میشه یا زیاد میشه) رفتار اونرو تعیین میکنه ولی در اصل قضه یعنی نحوه پیاده سازی تفاوتی ایجاد نمیشه
پس همواره آخرین داده ذخیره شده اولین داده بازیابی شونده است
صف یا queue یا FIFO هم یه مفهوم هست که در اون اولین داده ذخیره شده اولین داده بازیابی شونده است (حالا نحوه پیاده سازی هرچی باشه آخرسر باید به اینجا برسیم)
کاربردهای اینها هم هر کدوم مشخصه مثلا در فراخوانی توابع چاره ای جز استفاده از پشته نداریم یا در پردازش عبارات ریاضی شامل پرانتز ؛ آخرین پرانتز باز شده باید اول بسته بشه که میشه همون کاربرد پشته ای

[hamidreza.nayeri]

پاسخ : stack

آیا کسی میدونه چه دلیلی داره که نحوه ذخیره سازی در پشته باید بصورت LIFO باشه ؟
حالا اگه FIFO باشه چه اشکالی پیش می یاد ؟
خودم فکر می کنم که به دستور PUSH و POP و رجیستر SP مربوطه

برای این که در خیلی از الگوریتم ها این به کار میاد. والا صف هم وجود داره که به صورت FIFO کار میکنه.
از پشته استفاده میکنن چون خیلی از جاها از نظر منطقی کار رو خیلی راحت میکنه مثلا وقتی میخواید تمامی اعضای یک درخت n-ary رو بخونید، اصلا با غیر پشته نمیشه کار کرد و مثالهایی از این دست خیلی زیاده.
یکی از کاربرد های پشته هم ماشین پشته هستش که در اون جا هم باید نوع اطلاعات LIFO باشه (حتما) در غیر این صورت درست کار نمیکنه.

[hamidreza.nayeri]

پاسخ : stack

با تشکر از دوستانی که پاسخ دادند
همونطور که می دونیم در پشته با هر بار عمل PUSH از رجیستر SP دو واحد کم میشه
سوال دیگه اینکه چرا پشته بایستی از آخر به اول عمل ذخیره سازی رو انجام بده؟
خوب همین عمل LIFO از اول به آخر هم می تونه انجام بشه و به جای اینکه با هر بار عمل PUSH رجیستر SP دو واحد کم بشه به عکس دو واحد زیاد بشه
خوب این هم LIFO از اول به آخر میشه و دقیق هم کار می کنه
حدس خودم اینه که برای عدم همپوشانی CS و SS هست که عمل LIFO از آخر به اول هست
تا ببینیم نظر شما چیه

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

[masoud58]

پاسخ : stack

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

چه جالب :eek:
تو کدوم پردازنده SP زیاد میشه ؟ خیلی دوس دارم بدونم
درضمن باعرض پوزش من بعید میدونم سازنده دلیل نداشته و حال کرده باشه SP رو کم کنه حتما دلیلی برای این کارش داره
این که گفتید به معماری بستگی داره من هم موافقم فقط علتشو نمیدونم چرا؟؟؟؟؟

[hamidreza.nayeri]

پاسخ : stack

چه جالب :eek:
تو کدوم پردازنده SP زیاد میشه ؟ خیلی دوس دارم بدونم
درضمن باعرض پوزش من بعید میدونم سازنده دلیل نداشته و حال کرده باشه SP رو کم کنه حتما دلیلی برای این کارش داره
این که گفتید به معماری بستگی داره من هم موافقم فقط علتشو نمیدونم چرا؟؟؟؟؟

الان یادم نیست ولی فکر میکنم (بازم میگم فکر میکنم) پردازنده های AVR استک پونترشون زیاد میشه نه کم. من دیدم این رو ولی یادم نمیاد کجا بود.
اما جدا میگم هیچ دلیل خاصی نداره چون خیلی از سازنده ها برعکس این موضوع رفتار کرده اند.

[hamidreza.nayeri]

پاسخ : stack

با تشکر از دوستانی که پاسخ دادند
همونطور که می دونیم در پشته با هر بار عمل PUSH از رجیستر SP دو واحد کم میشه
سوال دیگه اینکه چرا پشته بایستی از آخر به اول عمل ذخیره سازی رو انجام بده؟
خوب همین عمل LIFO از اول به آخر هم می تونه انجام بشه و به جای اینکه با هر بار عمل PUSH رجیستر SP دو واحد کم بشه به عکس دو واحد زیاد بشه
خوب این هم LIFO از اول به آخر میشه و دقیق هم کار می کنه
حدس خودم اینه که برای عدم همپوشانی CS و SS هست که عمل LIFO از آخر به اول هست
تا ببینیم نظر شما چیه

یک چیزی رو الان یادم اومد.
در ماشین های x86 وقتی یه کاری که میشه (که غالبا C این کار رو انجام میده)آ اینه که متغیرهایی که به تابعی فرستاده میشن رو پشته قرار داده میشه.
در این حالت شما برای این که بتونید این حافظه ها رو بخونید باید از رو پشته این کار رو انجام بدید.
یکی از دلایلی که تو x86 پشته موقع پوش کردن کم میشه اینه که x86 مداری داره که به صورت بیس و آفستی آدرس رو حساب میکنه و بعد تو اون آدرس مقداری رو میریزه. مثلا فرض کنید شما دارید

mov eax, [esp + 4]

در این صورت مقدار پارامتر اول ( در سیستم های ۳۲ بیتی)آ به رجیستر eax منتقل میشه.
علت این که اینجا پشته کم میشه اینه که این مدار فقط جمع کننده داره و نمیتونه تفریق کنه یعنی اگر موقع پوش شدن به جای تفریق جمع رخ بده دیگه نمیشه این دستور رو در یک پالس ساعت انجام داد.

اما علت این که تو بعضی ماشین ها این طوری نیست علتش اینه که تو اون ماشین ها این مدار جمع کننده وجود نداره و در هر حال این دستور در دو پالس ساعت انجام میشه.


یکی از دلایل کم شدن پشته در x86 این مداره.