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

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

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

آنچه از این جلسه باید بدانید: آشنایی و توانایی استفاده از انواع ظرف‌ها و ساختمان‌های داده در جاوا

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

 

رفتار متد
کالکشن تعریف‌شده از جنس 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 چه کاری بر روی این صف انجام می‌دهند.

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

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

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

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

 

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

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

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

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

نکات:

  • در متدهای 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 به نحوی که در بالا گفته شد، بارگذاری کنید.

با ما همراه باشید:

آدرس کانال تلگرام: IranianJavaDevelopers@

آدرس صفحه اینستاگرام: javacup.ir

آدرس گروه لینکدین: Iranian Java Developers

 


درباره سردبیر

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

کنترل ترافیک

نام و تاریخ مسابقه: جی‌کل ۸ – ۲۱ اردیبهشت ۱۳۹۷ مباحث: Collections و Generics  

پاسخ دهید

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