حل تشریحی سوال شماره 16 طراحی الگوریتم

یک ساختمان داده را در نظر بگیرید که از دو پشته $S_1$ و $S_2$ تشکیل شده است این ساختمان داده دو عمل درج و استخراج را پشتیبانی می‌کند. به هنگام درج عنصر x در این ساختمان داده $pu\mathrm{sh}\left(S_1,x\right)$ را اجرا میکنیم به هنگام اسخراج اگر $S_2$ خالی نبود، $Pop\left(S_2\right)$ را اجرا می‌کنیم در غیر این صورت همه عناصر داخل $S_2$ را پاپ و داخل S پوش میکنیم و بعد دستور $Pop\left(S_2\right)$ را اجرا و به عنوان خروجی دستور استخراج در نظر می‌گیریم اگر دو پشته در ابتدا خالی باشد و n عمل درج و استخراج به ترتیب دلخواه انجام شود هزینه سرشکن این عمل‌ها کدام است و ساختمان داده فوق چه ساختمان داده ای را پیاده سازی می‌کند؟