خانه / آموزش / تمرین‌های آموزشی / صف دوطرفه (تا پایان جلسه چهاردهم)

صف دوطرفه (تا پایان جلسه چهاردهم)

سطح سوال: متوسط

قصد داریم برای راحتی استفاده از واسط Deque چند رفتار پرکاربرد را در یک کلاس utility پیاده‌سازی کنیم. Deque کوتاه‌شده‌ی عبارت Double Ended Queue یعنی صف دوطرفه است. در یک صف یک‌طرفه‌ی عادی، اشیا از یک سر صف وارد شده و از سر دیگر خارج می‌شوند. یعنی اولین شی‌ای که به صف وارد می‌شود، اولین شی‌ای خواهد بود که از سر صف خارج می‌شود (FIFO). در پشته نیز به این صورت است که اشیا فقط از یک سر صف می‌توانند وارد و خارج شوند. یعنی آخرین شی‌ای که به صف وارد می‌شود، اولین شی‌ای خواهد بود که از سر صف خارج می‌شود (LIFO). اما Deque همانطور که گفته‌شد، یک صف دوطرفه است و اشیا از هر دو سمت می‌توانند وارد و یا خارج شوند. بنابراین می‌توان هم به عنوان صف عادی و هم به عنوان پشته از آن استفاده کرد. به راحتی می‌توانید لیستی از رفتارهایی که این واسط در اختیارمان می‌گذارد را مشاهده کنید. ما می‌خواهیم طبق نیازهایمان، چند رفتار پرکاربرد را به این واسط اضافه کنیم. به این منظور، ابتدا بسته‌ی ir.javacup.dq را دانلود کنید. در این بسته یک واسط با نام DequeUtil وجود دارد. شما کلاس DequeUtilImpll را به گونه‌ای تکمیل کنید که این واسط را طبق جدول زیر پیاده‌سازی کند:

 

رفتار متد
کالکشن تعریف‌شده از جنس Deque را، برمی‌گرداند. Deque<T> getDeque();
شی موجود در اندیس index را بدون اینکه حذف کند، برمی‌گرداند. T get(int index);
شی element را در اندیس index به کالکشن اضافه می‌کند. boolean push(T element, int index);
شی element را با شی موجود در اندیس index جایگزین می‌کند. boolean replace(T element, int index);
ترتیب اشیای بین اندیس‌های first و second را برعکس می‌کند. boolean reverse(int first, int second);

 

پس از اجرای کد زیر:

 

وضعیت صف دوطرفه‌ی ما به شکل زیر خواهد بود:

وضعیت اولیه‌ی صف دوطرفه

حال نشان می‌دهیم که هر یک از متدهای تعریف‌شده در واسط DequeUtil چه کاری بر روی این صف انجام می‌دهند.

با اجرای دستور زیر:

وضعیت صف دوطرفه‌ی ما به شکل زیر خواهد بود:
null
با اجرای دستور زیر:

وضعیت صف دوطرفه‌ی ما به شکل زیر خواهد بود:

null

و با اجرای دستور زیر:

وضعیت صف دوطرفه‌ی ما به شکل زیر خواهد بود:

وضعیت صف دوطرفه پس از reverse

هم‌چنین با اجرای دستور زیر:

مقدار ۴ برگردانده می‌شود.

نکات:

  • در متدهای push ،replace و reverse اگر اندیس(های) داده‌شده به عنوان پارامتر مقادیر معتبری داشتند، رفتار مورد نظر بر روی صف اعمال شده و متد مقدار true برمی‌گرداند. در غیر این صورت هیچ کاری روی صف انجام نگرفته و مقدار false برگردانده می‌شود. بدیهی است که اندیس‌ها زمانی معتبرند که کوچکتر از اندازه‌ی صف و بزرگتر مساوی صفر باشند.
  • در متد reverse اندیس first باید کوچکتر مساوی second باشد.
  • در متد get اگر اندیس داده‌شده در ورودی معتبر نبود، یک استثنا با پیام: “index should be between 0 and size-1” پرتاب می‌شود.

آنچه باید آپلود کنید:

یک فایل زیپ شامل بسته‌ی ir.javacup.dq است. به صورتی که وقتی فایل زیپ را باز می‌کنیم، دقیقا شاخه‌ی ir را ببینیم که درون آن شاخه‌ی javacup و درون آن نیز شاخه‌ی dq قرار دارد. در داخل شاخه‌ی dq فقط فایل DequeUtilImpl.java وجود دارد.

برای داوری تمرین، می‌توانید پاسخ خود را در سایت Quera به نحوی که در بالا گفته شد، بارگذاری کنید.

 


درباره مهناز خورسندی

همچنین بررسی کنید

ماشین‌سازی (تا پایان جلسه ششم)

سطح سوال: ساده آنچه از این جلسه باید بدانید: فرآیند مقداردهی اولیه اشیا سازنده ترتیب …

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *