حل تشریحی سوال شماره 40 دروس مشترک

فرض کنید یک پشته با اعمال اساسی push و pop داریم. تابع mypush را به‌صورت زیر به پشته اضافه می‌کنیم:

mypush(S,x):

while stack S is not empty:

y=S.pop()

if x < y:

exit the while loop

end while

S.push(x)

اگر با شروع از یک پشته خالی، دنباله‌ای از n تابع push و pop و mypush را با ترتیب دلخواه روی پشته اجرا کنیم، هزینه اجرای این توابع به‌صورت سرشکن کدام است؟ (بهترین کزینه را انتخاب کنید.)