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

صفحه 1:
ان داده ها و الگوریتمها 

صفحه 2:
‎٩‏ صف نیز مانند پشته براي نگهداري مجموعه هاي پویا استفاده مي شود © هر صف يك ابتدا و يك انتها دارد © عناصر جدید به انتهاي صف اضافه مي شوند ‎G‏ 6۱ 0۱ ‎٩‏ عناصر قديمي از ابتداي صف توت عدم حذف مي شوند * صف براي پیاده سازي نوبت بندي استفاده مي شود و سا ختار آن ‏است. ‎ ‎ ‎ ‎ ‎ 

صفحه 3:
- ابتداي صف(ج): محلي است که عضو موجود در آن كانديداي حذف است. - انتهاي صف(ا): محلي است که عضو جديدي که وارد صف مي شود در آن قرار مي كيرد * هر صف ظرفیت محدودي دارد © هر صف مي توان در يكي از وضعيتهاي پر نیمه پر یا خالي باشد - اگر ابتدا و انتهاي صف يكي باشنده صف خالي است - اگر ابتداي صف بلافاصله بعد از انتهاي آن باشد» صف پر است. ‎٩‏ مشابه پشته مي توان صف را براحتي با استفاده از آرایه پیاده سازي کرد 

صفحه 4:
۱0۳۰۶ 9 8: 1 6 که 48 23 2 1 ) 2 ۱594 | 1 1 ۸۰۸/۲۵ <7 ۰۰. ۵1-2 1 ۵ 3 ۸ ‏گر‎ 8 68 9 BML © 51 151 6191814 ]17[ tail[Q\=3 ۵۱۵1-27 123 45 6 7 8 9 ۰10۰11 2 © 13151 9814 117( t ۱ tail[Q] =3 head{Q] =8 

صفحه 5:
prblc toterPuce Queue { publ bovkeos iBorpty(); public Objevt ce(Proa(Bekeweni(); publ Objevt et RearBeleweni(); publiz void pui(Objert theObiet); publ ‏زاس اسان‎ 

صفحه 6:
© جاهايي كه نمي توان از صف به جاي پشته استفاده کرد: - Poeuhesrs watchicg. - Towers oP Wadi. — Oetkod evocation ced returc. - ‏تومیر‎ icopleswectaiocd. جاهايي که مي توان از صف به جاي پشته استفاده کرد: ‎waz.‏ 5 و ‎in Pirdkay shortest puts to ex.‏ یج © 

صفحه 7:
لا ‎end pin‏ Label all reachable squares 1 unit from ctart. 

صفحه 8:
I start pin ‏م‎ Label all reachable unlabeled squares 2 units from start. 

صفحه 9:
I start pin ‏م‎ Label all reachable unlabeled squares 3 units from start. 

صفحه 10:
I start pin ‏م‎ ادت‌ات| صان ایب ادت‌ات اد |دت| ان Label all reachable unlabeled squares 4 units from start. 

صفحه 11:
I start pin 4 1B ‏و م‎ ‏فاك‎ ‎3434 ‎4 Label all reachable unlabeled squares 5 units from start. 

صفحه 12:
5 ‎I start pin 45‏ 1 و مم هدك كه 2 2 اد 4۱ اد 4 اد 45 دا اد Label all reachable unlabeled squares 6 units from start. 

صفحه 13:
5/6 [6 ‎start pin 45‏ _ | 5 12 مم هدك كه )6 ]5 ]3/4 ]3/4 ۵ [د 41 )6 ]5 ]6 ]5 6 End pin reached. Traceback. 

صفحه 14:
۱ start pin De) ee) SS ea) ‏ات‎ انت‌آت|ان‌ادت| | 5 اه صنم م اباه| (9 ‎[ons‏ ‏للك لدعا End pin reached. Traceback. 

صفحه 15:
0 1 2 34 56 اگر ببس انتهاي سمت چپ و وم انتهاي سمت راست لیست باشد: روتسد تسس ۰ ‎O(0) toe‏ - ‎e€ProBlewreci() => oD)‏ © ‎te‏ )00 = ‎cpARrcr(Blrma() => cp(otz() - 0(‏ © ‎O0) te‏ = ‎pri(heObjer!) => odd(stze(), heObiert)‏ © ‎O0) te‏ = (0 )سس << زاس ۰ - O(size) toe 

صفحه 16:
214228 2 03 - اكر سح انتهاي سمت راست و محر انتهاي سمت چپ لیست باشد: ره همه << )بط سص 6 () 0)0( - wetProciBleweri() => oet(stze() - (۶ OW) - ‏اطعا‎ => cei((D) ® OW) - ‏,)نی >= ونان‎ theObert) © O(stze) toe - repve() => rewove(stze() - 0( * 00( ۰ - 

صفحه 17:
- اگر بخواهیم تمام عملیات را با (0)0 انجام دهیم؛ لازم است نمایش ویژه اي براي آرایه تعریف کنیم در ادامه همین درس نمونه اي از اين تمایش ویژه را خواهیم دید 

صفحه 18:
‎firstNode 7‏ ‎front rear‏ اگر برس انتهاي سمت چپ و ‎rear‏ انتهاي سمت راست ليست باشد: ‎Queue.isEmpty() => super.isEmpty()‏ ‎O(1) time‏ - ‎* getFrontElement() => get(0) - C911) ma 

صفحه 19:
firstNode lastNode 5 511 front rear * getRearElement() => getLast() ... new metho - O(1) time * put(theObject) => append(theObject) - O(1) time * remove() => remove(0) - O(1) time 

صفحه 20:
7 نت ‎rear front‏ ‎Proot JS)‏ انتهاي سمت راست و جح انتهاي سمت جب ليست باشد: * Queue.isEmpty() => super.isEmpty() - O(1) time * getFrontElement() => getLast() 

صفحه 21:
firstNode rear * getRearElement() => get(0) - O(1) time * put(theObject) => add(0, theObject) - O(1) time * remove() => remove(size-1) - O(size) time 

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

صفحه 23:
استفاده از آرایه يك بعدي براي نمایش صف queuel [ESS 1 * نمایش چرخشي آرایه 

صفحه 24:
* چیدن سه عضو در يك آرایه چرخشي: [3] 

صفحه 25:
. ۲ * ترتیب دیگر چیدن سه عضو 

صفحه 26:
۰ استفاده از متغيرهاي صحیح ۲627 ,8۳01 براي نمايش ابتدا و انتهاي صف ۰ 1 به محلي‌از آرلیه لشاره مي‌کند که یکوقبل از اولین‌عضو آرلیه - در جهتساعتگرد - قرار دارد ‎٠‏ 76۲ به آخرین عضو آرایه اشاره مي کند 

صفحه 27:


صفحه 28:
ر جهتساعتگرد يك‌ولحد جلو مي‌بريم : ضو جديد را در محل [11611©]1621). قرار مي دهيم 

صفحه 29:


صفحه 30:
را یك‌ولحد جلو مييريم ‎queue[front]‏ را مي خرانيم ‎[3] ‎rear ‎ 

صفحه 31:
* rear++; if (rear = = queue.length) rear = 0; * rear = (rear + 1) % queue.length; 

صفحه 32:


صفحه 33:


صفحه 34:


صفحه 35:


صفحه 36:


صفحه 37:


صفحه 38:


صفحه 39:
* بعد از افزودن چند عضوء صف ير مي شود و در نتیجه :۲661 = ‎front‏ ‏* چگونه صف پر را از خالي تشخیص دهیم ؟ 

صفحه 40:
9 صف اولویت دار - کاربرد: ببزلموراا مر) - پیاده سازی: درخت مور" Oeque / Ovuble Gaded Queue 488 33 ‏صف‎ ٩ ‏کاربرد: شبیه سازی سیستمهای موازی و همروند‎ - ‏پیاده سازی: لیست پیوندی دوطرفه‎ - 

صفحه 41:
‎epbourd 0۳ ©‏ - هر حرفي را که با استفاده از صفحه ‎aS‏ تایپ مي کنید در حافظه اي قرار مي گیرد که به (() لسمسارج) معروف است. - سیستم عامل به طور مرتب این حافظه را تحت نظر دارد و حرف موجود در ابتداي این فا برداشته و به مصرف مي :رسائم - اگر تایپ شما آنقدر سریع باشد که اين حافظه ير شودء:كامبيوتن با بوق كوتاهي شما را مطلع مي سازد ‎٩‏ این حالت» در سیستم عامل عبم(0)» که بافر آن گنجایش حداکثر 0 حرف را دارد؛ خيلي اتفاق مي افتد(مي لفتاد!؟) ۶ مج ‎Oindows Cvect‏ - در سیستم عامل ویندوز» هر واقعه(فشار دادن کلید؛ كليك ماووس» ۲ فرارسيدن زماني خاص و...) در يك صف واقعه مختص هر برنامه قرار مي كيرد 

صفحه 42:
پروژه0 - حل مساله موش و پنیر با استفاده از صف @ اين مساله در درس پشته ها و همچنین صفها بررسي شد * این مساله را با استفاه از صف حل کنید - توضیحات بیشتر در سایت درس