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

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

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

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

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

DequeUtilImpl<Integer> dequeImpl = new DequeUtilImpl<>();
for(int i=0; i<6; i++)
    dequeImpl.getDeque().push(i);

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

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

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

dequeImpl.push(11, 2);

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

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

dequeImpl.replace(11, 2);

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

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

dequeImpl.reverse(1, 4);

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

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

dequeImpl.get(1);

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

نکات:

• در متدهای 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