پشته و صف پیوندی

پشته و صف پیوندی

اسلاید 1: پشته و صف پیوندی

اسلاید 2: رئوس مطالبمشکل: چه کار کنیم که لیستهای پیوندی کارآمدتر شوند؟لیستهای دو پیوندیپیاده‌سازی لیست پیوندی پشتهپیاده‌سازی لیست پیوندی صفدقت کنید که قبلاً نسخه ی آرایه ای صف و پشته را دیده‌ایم.

اسلاید 3: مشکلات لیست تک پیوندیnode1 node2 node3 headtailفقط در یک جهت می توان حرکت کرد.در هنگام حذف یا اضافه کردن باید نود قبلی را به خاطر داشته باشیم. در کدنویسی باید حواسمان به ابتدا و انتهای لیست باشد که منجر به تولید if های زیادی می شود.

اسلاید 4: یک نود در لیست دوپیوندیprev nextvalueNodeهر نود دو ارجاع دارد.previousNode following Node

اسلاید 5: نود ساختگیاعمال حذف و افزودن راحتتر خواهند بود. چون همیشه در وسط لیست اتفاق می افتند. dummy head nodenullvalue nullnullnulldummy tail node

اسلاید 6: ایجاد یک لیست پیوندی دوپیوندینودهای head و tail را ایجاد کنید. آنها را به هم پیوند دهید. tNode.prev = hNodehNode.next = tNodenullnullnullnullnullnullhNodetNodenullnullnullnullhNodetNode

اسلاید 7: ادامه ... (ایجاد لیست دو پیوندی))مقدار head را برابر hNode و tail را برابر tNode قرار دهید. headtailnullnull null nullhNodetNode

اسلاید 8: افزودن یک نود جدیداضافه کردن نود جدید بعد از نود p.node nullnullnullheadtailpnullnullitemNew node

اسلاید 9: ادامه ... (افزودن یک نود جدید)مقدار پیوند prev نود جدید را برابر p قرار دهید. nullitemNew nodenode nullnullnullheadtailp

اسلاید 10: ادامه ... (افزودن یک نود جدید)مقدار next نود جدید را برابر p.next قرار دهید.tailpNew nodenode nullnullnullheaditem

اسلاید 11: ادامه ... (افزودن یک نود جدید)مقدار p.next.prev را برابر نود جدید قرا دهید. node nullnullnullheadtailpitem

اسلاید 12: ادامه ... (افزودن یک نود جدید)مقدار p.next را برابر نود جدید قرار دهید. node nullnullnullheadtailpitem

اسلاید 13: کد مربوط به افزودن نود جدید public void Insert(DNode p, Object item){DNode newNode = new Dnode(p, p.next, item);newNode.next.prev = newNode;p.next = newNode;count ++;}

اسلاید 14: حذف یک نودحذف نود pnode nullnullnullheadtailp

اسلاید 15: ادامه ... (حذف یک نود)مقدار p.next.prev را برابر p.prev قرار دهید. node nullnullnullheadtailp

اسلاید 16: ادامه ... (حذف یک نود)مقدار p.prev.next را برابر p.next قرار دهید. node nullnullnullheadtailp

اسلاید 17: ادامه ... (حذف یک نود)حال می توانید نود p را حذف کنید. nullnullnullheadtail

اسلاید 18: کد حذف نودObject remove(DNode p){Object item = p.value;p.next.prev = p.prev;p.prev.next = p.next;count --;return item;}

اسلاید 19: لیست مدورآخرین لینک به اولین لینک بر می گردد. یعنی پیوند آخرین لینک به اولین نود اشاره می کند. currentnode1node2node3

اسلاید 20: پیاده سازی لیست پیوندی پشتهD…BAtopE0stackpushpopپشته همراه با افزودن یا حذف بزرگ و کوچک می شود.دیگر نیازی به دانستن حداکثر اندازه ی پشته نداریم. هر جا لازم شد به نود جدید حافظه تخصیص می دهیم.

اسلاید 21: پیاده‌سازی لیست پیوندی پشتهنودها به ابتدا اضافه می شوند. نودها از ابتدا برداشته می شوند. topabcnullpushpop

اسلاید 22: عمل Push اضافه کردن یک عنصر به ابتدای پشتهtopabcnull

اسلاید 23: عمل Push (ادامه ...)ایجاد نود جدید با مقدار d. پیوند دادن نود جدید به ابتدای پشته. New nodednulltopabcnullNew noded

اسلاید 24: عمل Push (ادامه ...)مقدار top باید به نود جدید اشاره کند. topabcnullNew nodedtopabcnulld

اسلاید 25: عمل Pop حذف یک عنصر از پشتهtopabcnullatopabcnull

اسلاید 26: LinkedStack Implementationpublic class LinkedStack implements StackPT{//instance variables//private methods, classes//public methods//…}

اسلاید 27: پیاده سازی لیست پیوندی صفدو عملکرد اساسی:Enqueue: اضافه کردن به tail صف.Dequeue: حذف از head صف. عملکردهای دیگر:isEmptyisFull نداریم. Size

اسلاید 28: خلاصه لیست پیوندیحافظه ی مصرفی به اندازه ی مورد نیاز است. کار با داده ها (مثل افزودن و حذف) کارآمدتر است. از آرایه بهتر است. کار با لیست دوپیوندی راحتتر است. می توان پشته و صف را با لیست پیوندی پیاده کرد.