پشته یکی از داده ساختارهای پرکاربرد در علوم کامپیوتر است که دنبالهای از عناصر را ذخیره میکند. تغییرات در عناصر پشته فقط از دو نوع میتواند باشد:
برای مثال فرض کنید پشتهای به صورت {١, ۵, ۴, ٣} باشد. با اضافه کردن عضوی با مقدار ٧ به انتها، پشته به صورت {٧, ١, ۵, ۴, ٣} خواهد شد. همچنین اگر از انتهای پشتهی {٣, ١٠, ٢} یک عنصر را حذف کنیم، پشته به صورت {١٠, ٢} خواهد شد.
اکنون میخواهیم یکی از روشهای ذخیره سازی پشته در کامپیوتر را شرح دهیم. در این روش، عملهای زیر را میتوان انجام داد:
عمل اضافه کردن به پشته: با دستور $push(S, x)$ مقدار $x$ به انتهای پشتهی $S$ اضافه میشود. دو حالت داریم:
حافظهی مربوط به $S$ دارای خانهی خالی باشد؛ در این صورت عدد $x$ در نخستین خانهی خالی حافظهی مربوط به پشتهی $S$ قرار میگیرد. برای مثال اگر حافظهی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 6)$ اجرا شود، حافظهی مربوط به $S$ به شکل سمت راست در خواهد آمد:
![](/_media/%D8%B3%D9%88%D8%A7%D9%84%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D9%BE%DB%8C%D8%A7%D8%AF/%D9%85%D8%B1%D8%AD%D9%84%D9%87_%DB%8C_%D8%A7%D9%88%D9%84/%D8%AF%D9%88%D8%B1%D9%87_%DB%8C_%DB%B3%DB%B0/screenshot_from_2022-06-23_23-51-28.png)
اجرای عمل بالا یک واحد زمان مصرف میکند.
حافظهی مربوط به $S$ دارای خانهی خالی نباشد؛ در این صورت جایی جدید از حافظه با دو برابر تعداد خانههای حافظهی فعلی به $S$ اختصاص داده شده و سپس عمل اضافه کردن انجام میشود. برای مثال اگر حافظهی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 10)$ اجرا شود، حافظهی مربوط به $S$ به شکل سمت راست خواهد آمد:
اجرای چنین عملی به اندازهی تعداد خانههای حافظهی جدید اختصاص داده شده زمان مصرف میکند. برای نمونه، در مثال بالا ٨ واحد زمان مصرف میشود.
عمل حذف کردن از پشته: با دستور $pop(S)$ یک عنصر از انتهای پشتهی $S$ حذف میشود. برای مثال اگر حافظهی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظهی مربوط به $S$ به شکل سمت راست در خواهد آمد:
![](/_media/%D8%B3%D9%88%D8%A7%D9%84%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D9%BE%DB%8C%D8%A7%D8%AF/%D9%85%D8%B1%D8%AD%D9%84%D9%87_%DB%8C_%D8%A7%D9%88%D9%84/%D8%AF%D9%88%D8%B1%D9%87_%DB%8C_%DB%B3%DB%B0/screenshot_from_2022-06-23_23-51-47.png)
در حالتی که با خالی کردن آخرین خانهی پر حافظهی مربوط به $S$ ،دست کم نیمی از خانهها خالی شود، حافظهای جدید به $S$ اختصاص داده میشود که خانههای خالی آن حذف شدهاند (مگر اینکه $S$ تنها یک خانه داشته باشد که در این صورت آن خانه حذف نمیگردد). برای مثال اگر حافظهی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظهی مربوط به $S$ به شکل سمت راست در خواهد آمد:
![](/_media/%D8%B3%D9%88%D8%A7%D9%84%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D9%BE%DB%8C%D8%A7%D8%AF/%D9%85%D8%B1%D8%AD%D9%84%D9%87_%DB%8C_%D8%A7%D9%88%D9%84/%D8%AF%D9%88%D8%B1%D9%87_%DB%8C_%DB%B3%DB%B0/screenshot_from_2022-06-23_23-51-55.png)
اجرای عمل حذف عنصر در حالاتی که تعداد خانهی حافظهی مربوط به $S$ تغییر کند (نصف شود)، به اندازهی تعداد خانههای حافظهی جدید اختصاص داده شده زمان مصرف میکند. برای نمونه در مثال بالا ۴ واحد زمان مصرف میشود. در حالاتی نیز که تعداد خانههای حافظهی مربوط به S تغییر نمیکند، یک واحد زمان مصرف خواهد شد.
عمل کپی: با دستور $copy(A, B)$ حافظهای به اندازهی حافظهی پشتهی $A$ به پشتهی $B$ اختصاص مییابد و مقادیر خانههای حافظهی $B$ نیز برابر مقادیر خانههای حافظهی $A$ خواهند شد. اجرای این عمل به اندازهی تعداد خانههای حافظهی مربوط به $A$ زمان مصرف میکند.
توجه کنید قبل از عملیات روی پشته، باید آن پشته در خطوط قبلی برنامه با دستور $create$ ساخته شده باشد.
برنامهی زیر چند واحد زمان مصرف میکند؟
$$create(X)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$pop(X)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$pop(X)$$
$$push(X, ١)$$
۱۴
۱۷
۱۹
۱۱
۱۵