ساختمان داده ها و الگوریتم ها (صف)

ساختمان داده ها و الگوریتم ها (صف)

اسلاید 1: صف Queueساختمان داده ها و الگوريتمها

اسلاید 2: 2صف Queueصف نيز مانند پشته براي نگهداري مجموعه هاي پويا استفاده مي شودهر صف يك ابتدا و يك انتها داردعناصر جديد به انتهاي صف اضافه مي شوندعناصر قديمي از ابتداي صف حذف مي شوندصف براي پياده سازي نوبت بندي استفاده مي شود و سا ختار آن First In First Out (FIFO) است.outin

اسلاید 3: 3صف Queueهر صف ابتدا و انتهايي داردابتداي صف(head): محلي است كه عضو موجود در آن كانديداي حذف است.انتهاي صف(tail): محلي است كه عضو جديدي كه وارد صف مي شود در آن قرار مي گيردهر صف ظرفيت محدودي داردهر صف مي توان در يكي از وضعيتهاي پر، نيمه پر يا خالي باشداگر ابتدا و انتهاي صف يكي باشند، صف خالي استاگر ابتداي صف بلافاصله بعد از انتهاي آن باشد، صف پر است.مشابه پشته مي توان صف را براحتي با استفاده از آرايه پياده سازي كرد

اسلاید 4: 4مثال صف

اسلاید 5: The Interface Queuepublic interface Queue{ public boolean isEmpty(); public Object getFrontEelement(); public Object getRearEelement(); public void put(Object theObject); public Object remove();}

اسلاید 6: بازنگري كاربردهاي پشتهجاهايي كه نمي توان از صف به جاي پشته استفاده كرد:Parentheses matching.Towers of Hanoi.Method invocation and return.Try-catch-throw implementation.جاهايي كه مي توان از صف به جاي پشته استفاده كرد:Rat in a maze.Results in finding shortest path to exit.

اسلاید 7: Lee’s Wire Routerstart pinend pinLabel all reachable squares 1 unit from start.

اسلاید 8: Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 2 units from start.11

اسلاید 9: Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 3 units from start.1122222

اسلاید 10: Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 4 units from start.11222223333

اسلاید 11: Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 5 units from start.1122222333344444

اسلاید 12: Lee’s Wire Routerstart pinend pinLabel all reachable unlabeled squares 6 units from start.1122222333344444555555

اسلاید 13: Lee’s Wire Routerstart pinend pinEnd pin reached. Traceback.112222233334444455555566666666

اسلاید 14: Lee’s Wire Routerstart pinend pin4End pin reached. Traceback.1122222333344444555555666666663521

اسلاید 15: Derive From ArrayLinearListاگر front‌ انتهاي سمت چپ و rear انتهاي سمت راست ليست باشد:Queue.isEmpty() => super.isEmpty()O(1) timegetFrontElement() => get(0)O(1) timegetRearElement() => get(size() - 1)O(1) timeput(theObject) => add(size(), theObject)O(1) timeremove() => remove(0)O(size) time0123456abcde

اسلاید 16: Derive From ArrayLinearListاگر front‌ انتهاي سمت راست و rear انتهاي سمت چپ ليست باشد:Queue.isEmpty() => super.isEmpty()O(1) timegetFrontElement() => get(size() - 1)O(1) timegetRearElement() => get(0)O(1) timeput(theObject) => add(0, theObject)O(size) timeremove() => remove(size() - 1)O(1) time0123456edcba

اسلاید 17: Derive From ArrayLinearListاگر بخواهيم تمام عمليات را با O(1) ‌ انجام دهيم؛ لازم است نمايش ويژه اي براي آرايه تعريف كنيمدر ادامه همين درس نمونه اي از اين نمايش ويژه را خواهيم ديد

اسلاید 18: Derive From ExtendedChainabcdenullfirstNodelastNodefrontrear اگر front‌ انتهاي سمت چپ و rear انتهاي سمت راست ليست باشد: Queue.isEmpty() => super.isEmpty() O(1) time getFrontElement() => get(0) O(1) time

اسلاید 19: Derive From ExtendedChainabcdenullfirstNodelastNodefrontrear getRearElement() => getLast() … new method O(1) time put(theObject) => append(theObject) O(1) time remove() => remove(0) O(1) time

اسلاید 20: Derive From ExtendedChainedcbanullfirstNodelastNoderearfront اگر front‌ انتهاي سمت راست و rear انتهاي سمت چپ ليست باشد: Queue.isEmpty() => super.isEmpty() O(1) time getFrontElement() => getLast() O(1) time

اسلاید 21: Derive From ExtendedChainabcdenullfirstNodelastNoderearfront getRearElement() => get(0) O(1) time put(theObject) => add(0, theObject) O(1) time remove() => remove(size-1) O(size) time

اسلاید 22: ليست پيوندي ويژه صفكلاس ليست پيوندي ويژه اي براي نمايش صف تعريف كنيد تا كارايي بالاتري را نسبت به استفاده از كلاسهاي موجود داشته باشيد

اسلاید 23: نمايش چرخشي آرايهاستفاده از آرايه يك بعدي براي نمايش صفqueue[]نمايش چرخشي آرايه[0][1][2][3][4][5]

اسلاید 24: نمايش چرخشي آرايهچيدن سه عضو در يك آرايه چرخشي:[0][1][2][3][4][5]ABC

اسلاید 25: نمايش چرخشي آرايهترتيب ديگر چيدن سه عضو[0][1][2][3][4][5]ABC

اسلاید 26: نمايش چرخشي آراياستفاده از متغيرهاي صحيح front, rear براي نمايش ابتدا و انتهاي صف front به محلي از آرايه اشاره مي كند که يكی قبل از اولين عضو آرايه – در جهت ساعتگرد – قرار دارد rear به آخرين عضو آرايه اشاره مي كند[0][1][2][3][4][5]ABCfrontrear[0][1][2][3][4][5]ABCfront rear

اسلاید 27: افزودن يك عضو[0][1][2][3][4][5]ABCfrontrearrear‌ را در جهت ساعتگرد يك واحد جلو مي بريم :

اسلاید 28: افزودن يك عضوrear‌در جهت ساعتگرد يك واحد جلو مي بريم :[0][1][2][3][4][5]ABCfrontrearعضو جديد را در محل queue[rear]. قرار مي دهيمD

اسلاید 29: حذف يك عضو[0][1][2][3][4][5]ABCfrontrearfront‌ را يك واحد جلو مي بريم

اسلاید 30: حذف يك عضو[0][1][2][3][4][5]ABCfrontrearfront‌ را يك واحد جلو مي بريم عضو queue[front]. را مي خوانيم

اسلاید 31: حركت rear‌در جهت ساعتگرد [0][1][2][3][4][5]ABCfrontrearrear++; if (rear = = queue.length) rear = 0;rear = (rear + 1) % queue.length;

اسلاید 32: صف خالي[0][1][2][3][4][5]ABCfront rear

اسلاید 33: صف خالي[0][1][2][3][4][5]BCfront rear

اسلاید 34: صف خالي[0][1][2][3][4][5]Cfront rear

اسلاید 35: صف خاليبعد از حذف چندين عضو، صف خالي مي شود و front = rear.هنگام ساخت اوليه، صف خالي است بنابراين در ابتداي ساختن صف بهتر است :front = rear = 0.[0][1][2][3][4][5]front rear

اسلاید 36: صف پر[0][1][2][3][4][5]ABCfront rear

اسلاید 37: صف پر[0][1][2][3][4][5]ABCfront rearD

اسلاید 38: صف پر[0][1][2][3][4][5]ABCfront rearDE

اسلاید 39: صف پر[0][1][2][3][4][5]ABCfront rearDEFبعد از افزودن چند عضو، صف پر مي شود و در نتيجه :front = rear.چگونه صف پر را از خالي تشخيص دهيم ؟

اسلاید 40: صفهای ویژهصف اولویت دارکاربرد: Event Handlingپیاده سازی: درخت Heapصف دوطرفه Deque / Double Ended Queueکاربرد: شبیه سازی سیستمهای موازی و همروندپیاده سازی: لیست پیوندی دوطرفه40

اسلاید 41: 41صف هاي مهمKeyboard Bufferهر حرفي را كه با استفاده از صفحه كليد تايپ مي كنيد در حافظه اي قرار مي گيرد كه به Keyboard Buffer معروف است.سيستم عامل به طور مرتب اين حافظه را تحت نظر دارد و حرف موجود در ابتداي اين صف را برداشته و به مصرف مي رسانداگر تايپ شما آنقدر سريع باشد كه اين حافظه پر شود، كامپيوتر با بوق كوتاهي شما را مطلع مي سازداين حالت، در سيستم عامل Dos، كه بافر آن گنجايش حداكثر 16 حرف را دارد، خيلي اتفاق مي افتد(مي افتاد!؟)Windows Event Queueدر سيستم عامل ويندوز، هر واقعه(فشار دادن كليد، كليك ماووس، فرارسيدن زماني خاص و...) در يك صف واقعه مختص هر برنامه قرار مي گيرد.

اسلاید 42: 42پروژه2 – حل مساله موش و پنير با استفاده از صفاين مساله در درس پشته ها و همچنين صفها بررسي شداين مساله را با استفاه از صف حل كنيدتوضيحات بيشتر در سايت درس