(۰۵ مرداد ۱۳۹۲ ۰۴:۵۲ ب.ظ)afshin.dam نوشته شده توسط:  ۱ – وقتی که می خواهیم یک صف رو توسط دو پشته پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟

۲ – وقتی که می خواهیم یک پشته رو توسط دو صف پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟

تحلیل خودم واسه سوال اول این است که چون دو پشته داریم برای ساخت یک صف : پشته اول هم Push و هم Pop در زمان O(1) انجام می شود و هم در پشته دوم هر دوی عملیات Push و Pop در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.
واسه سوال دوم چون دو صف داریم برای ساخت یک پشته : صف اول هم درج و هم حذف در زمان O(1) انجام می شود و هم در صف دوم هر دوی عملیات درج و حذف در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.

راستش مطمئن نیستم که حرفی که می زنم درسته ولی با تحلیل شما هم موافق نیستم
به نظرم برای پیاده سازی یک صف توسط دو پشته باید این گونه عمل کرد که یکی از پشته ها(پشته اول) حاوی تمامی عناصر صف (به این ترتیب که عنصری که در سر صف قرار دارد در بالای پشته و عناصر میانی صف بعد از ان تا اخرین عنصر صف که ته پشته قرار دارد) و پشته دوم خالی باشد
حالا در اینجا دو موضوع مطرح میشه
اولی حذف از صف که چون همواره عنصر سر صف بالای پشته قرار دارد این کار در مرنبه O(1) انجام میشه
دومی درج در صف. برای اولین باری که صف خالیه فقط کافیه با یک عملیات push عنصر جدید را یه پشته اضافه کرد ولی اگر صف خالی نیست برای این کار باید عنصری که اضافه می شود در ته پشته اول قرار گیرد. برای این کار تمام عناصر موجود در پشته اول را با pop و push کردن های متوالی به پشته دوم منتقل می کنیم تا پشته اول خالی شود سپس عنصر جدید را با یک push به پشته اول اضافه می کنیم و بعد دوباره با pop و push کردن های متوالی تمام بقیه عناصر صف را از پشته دوم به اول منتقل می کنیم پس از این کار دوباره عناصر صف به ترتیبی که عنصری که در سر صف قرار دارد در بالای پشته و عناصر میانی صف بعد از ان تا اخرین عنصر صف در ته پشته مرتب می شوند که تعداد pop و push این کار مجموعا ۲n+1 تا است یعنی مرتبه زمانی ان O(n) است توجه کنید که n برابر طول صف قبل از درج عنصر جدید می باشد
تحلیل مشابه ای را هم می توان برای پیاده سازی پشته با دو صف نیز بیان کرد
اگر اشتباه می کنم یا منظورتون بد فهمیدم لطفا جواب بدید

ممنونم از هر دو دوست عزیز

درسته به قول آقا فرید من به جزئیات توجه نکردم ....

ممنونم