پشته یکی از داده ساختارهای پرکاربرد در علوم کامپیوتر است که دنباله‌ای از عناصر را ذخیره می‌کند. تغییرات در عناصر پشته فقط از دو نوع می‌تواند باشد:

• یک عضو به انتهای پشته اضافه شود.
• یک عضو از انتهای پشته حذف شود.

برای مثال فرض کنید پشته‌ای به صورت {١, ۵, ۴, ٣} باشد. با اضافه کردن عضوی با مقدار ٧ به انتها، پشته به صورت {٧, ١, ۵, ۴, ٣} خواهد شد. هم‌چنین اگر از انتهای پشته‌ی {٣, ١٠, ٢} یک عنصر را حذف کنیم، پشته به صورت {١٠, ٢} خواهد شد.

اکنون می‌خواهیم یکی از روش‌های ذخیره سازی پشته در کامپیوتر را شرح دهیم. در این روش، عمل‌های زیر را می‌توان انجام داد:

• عمل ساختن پشته: با دستور $create(S)$ پشته‌ای با نام $S$ ساخته می‌شود و یک خانه در حافظه به آن اختصاص پیدا می‌کند که در ابتدا این خانه مقداری ندارد. اجرای این عمل یک واحد زمان مصرف می‌کند.

• عمل اضافه کردن به پشته: با دستور $push(S, x)$ مقدار $x$ به انتهای پشته‌ی $S$ اضافه می‌شود. دو حالت داریم:
  • حافظه‌ی مربوط به $S$ دارای خانه‌ی خالی باشد؛ در این صورت عدد $x$ در نخستین خانه‌ی خالی حافظه‌ی مربوط به پشته‌ی $S$ قرار می‌گیرد. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 6)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد:
    اجرای عمل بالا یک واحد زمان مصرف می‌کند.
  • حافظه‌ی مربوط به $S$ دارای خانه‌ی خالی نباشد؛ در این صورت جایی جدید از حافظه با دو برابر تعداد خانه‌های حافظه‌ی فعلی به $S$ اختصاص داده شده و سپس عمل اضافه کردن انجام می‌شود. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 10)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست خواهد آمد:
    اجرای چنین عملی به اندازه‌ی تعداد خانه‌های حافظه‌ی جدید اختصاص داده شده زمان مصرف می‌کند. برای نمونه، در مثال بالا ٨ واحد زمان مصرف می‌شود.
• عمل حذف کردن از پشته: با دستور $pop(S)$ یک عنصر از انتهای پشته‌ی $S$ حذف می‌شود. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد:
  در حالتی که با خالی کردن آخرین خانه‌ی پر حافظه‌ی مربوط به $S$ ،دست کم نیمی از خانه‌ها خالی شود، حافظه‌ای جدید به $S$ اختصاص داده می‌شود که خانه‌های خالی آن حذف شده‌اند (مگر اینکه $S$ تنها یک خانه داشته باشد که در این صورت آن خانه حذف نمی‌گردد). برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد:
  اجرای عمل حذف عنصر در حالاتی که تعداد خانه‌ی حافظه‌ی مربوط به $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, ١)$$

1. ۱۴
2. ۱۷
3. ۱۹
4. ۱۱
5. ۱۵

در برنامه‌ای ابتدا با دستور $create(S)$ پشته‌ی $S$ ساخته می‌شود. در ادامه‌ی این برنامه ١٣٩٨ دستور $push(S, 1)$ وجود دارد. این برنامه چند واحد زمان مصرف می‌کند؟

1. ۵۴۹۳
2. ۴۰۹۵
3. ۵۴۸۲
4. $2^{1398} + 1397$
5. $2^{1399} + 1399$

یک برنامه حداقل چند خط باید داشته باشد تا در انتهای آن دست کم ١٠٠ واحد حافظه (در مجموع برای پشته‌ها) وجود داشته باشد؟

1. ۲۷
2. ۳۵
3. ۵۱
4. ۲۲
5. ۲۳

• سوال قبل