پاورپوینت پشته و صف

بخشی از پاورپوینت

اسلاید 1 :

پشته و صف

اسلاید 2 :

پشته ها و صف ها
پشته ها به عنوان يک نوع داده مجرد
صف ها به عنوان يک نوع داده مجرد
چند کاربرد از پشته
تطبيق پرانتزهاي يک عبارت
بازي Maze
ارزيابي عبارات
تبديل عبارتهاي ميانوندي به پسوندي
دانشگاه کاشان- دانشکده مهندسی برق و کامپیوتر

اسلاید 3 :

پشته
پشته ها حالت خاصي از ليست هاي مرتب شده مي باشند که جايگذاري و حذف از يک سمت آن که top (بالا) ناميده مي شود ، صورت مي گيرد.
پشته يک ليست LIFO (Last-In-First-Out) نيز ناميده مي شود.

اسلاید 4 :

پشته

اسلاید 5 :

پشته ها به عنوان يک نوع داده مجرد

اسلاید 6 :

پشته ها به عنوان يک نوع داده مجرد
پياده سازي: با کمک ارايه

اسلاید 7 :

پشته ها به عنوان يک نوع داده مجرد
stack
Top
item
stack
item
Top

اسلاید 8 :

Rear
Rear
Front
صفها حالت خاصي از ليست هاي مرتب شده مي باشند که جايگذاري از يک سمت آن که front (ابتدا) ناميده مي شود و حذف از سمت ديگر که rear (انتها) ناميده مي شود صورت مي گيرد.
صف يک ليست FIFO (First-In-First-Out) نيز ناميده مي شود.
Front

اسلاید 9 :

front
rear
rear
rear
rear
rear
صف اتوبوس

اسلاید 10 :

front
rear
rear
rear
صف اتوبوس

اسلاید 11 :

front
rear
rear
صف اتوبوس

اسلاید 12 :

front
rear
rear
صف اتوبوس

اسلاید 13 :

صف ها به عنوان يک نوع داده مجرد

اسلاید 14 :

صف ها به عنوان يک نوع داده مجرد
پياده سازي: با کمک آرايه يک بعدي و دو متغير front و rear

اسلاید 16 :

مشکل ممکن است با وجود آنکه در صف جاي خالي وجود دارد IsFullQ برابر true شود.
مثال
صف به تدريج به سمت راست شيفت پيدا مي کند
در اين حالت queue_full بايد تمام صف را به چپ شيفت دهد به گونه اي که عنصر اول صف در مکان صفر ارايه قرار گيرد front برابر -1 و rear به صورت مناسب تصحيح شود.
شيفت زمان گير پيچيدگي زماني queue_full برابر O(MAX_QUEUE_SIZE)

اسلاید 17 :

پياده سازي 2
از يک ارايه 1D استفاده کرده و آن را به صورت حلقوي در نظر بگيريم

صف حلقوي

اسلاید 18 :

يک صف حلقوي دلخواه با 3 عنصر