بایگانی برچسب‌ها : زیرریز

صف Queue

صف یا Queue چیست؟

صف (Queue) عنوان ساختمان داده‌ای است که مجموعه‌ای از المان‌ها (عناصر) را بر اساس اصل FIFO (خروج به ترتیب ورود) در خود نگه‌داری می‌کند.

برای Queue دو عمل اصلی تعریف می‌شود. عمل Enqueue که عنصر جدیدی را به انتهای آن (که rear نامیده می‌شود) اضافه می‌کند و عمل Dequeue که عنصری را از ابتدای آن (که front نامیده می‌شود) حذف می‌کند. به این ترتیب اولین عنصری که به یک Queue افزوده می‌شود اولین عنصری خواهد بود که از آن حذف خواهد شد. از این رو، صف‌ها را نوعی ساختمان داده‌ی FIFO به شمار می‌آورند. در برخی از پیاده‌سازی‌ها، عملی به نام Front یا Peek نیز تعریف می‌شود که مقدار المان اول را بدون حذف آن برمی‌گرداند.

هنگامی که می‌خواهیم داده یا المانی را برای مدتی نگه‌داری و در آینده مورد پردازش قرار دهیم به کاربردن صف از جمله بهترین راهکارهایی به شمار می‌رود که برای این منظور استفاده می‌شود. در چنین حالتی صف، نقش یک بافر را ایفا می‌کند. یکی از مهم‌ترین کاربردهای این ساختمان داده در الگوریتم‌های زمان بندی می‌باشد.

پیاده‌سازی صف

هرچند از نظر تئوری می‌توان صف‌ها را به صورت نامتناهی و بدون محدودیت در ظرفیت تجسم نمود اما در صورتی که صف را توسط آرایه‌ای با طول ثابت پیاده سازی کنیم ظرفیت آن ثابت خواهد بود. با درنظر گرفتن این آرایه به صورت یک دایره می‌توان یک صف حلقوی ایجاد نمود. در این نوع Queue لزوما انتهای آرایه، انتهای صف نیست بلکه می‌توان از فضای خالی به وجود آمده در ابتدای آرایه (به دلیل اعمال Dequeue)، برای افزودن عناصر جدید استفاده نمود. در صورتی که Queue پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ می‌دهد. به طور مشابه در صورتی که بخواهیم روی یک Queue خالی، عمل Dequeue را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد.

استفاده از لیست‌های پیوندی (Linked List) برای پیاده‌سازی صف می‌تواند محدودیت تعداد عناصر قابل نگه‌داری در این ساختمان داده را از میان بردارد. به عبارت بهتر در این نوع پیاده سازی برخلاف حالتی که از آرایه برای انجام این کار استفاده می‌شود نیازی به مشخص نمودن ظرفیت صف هنگام ایجاد آن وجود ندارد.

اعمال حذف و اضافه روی یک صف
اعمال حذف و اضافه روی یک Queue

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا

پشته Stack

پشته یا Stack چیست؟

پشته (Stack) در علوم رایانه، به ساختمان داده‌ای گفته می‌شود که مجموعه‌ای از المان‌ها را براساس اصل LIFO (اولویت خروج با عناصر تازه وارد) در خود نگه‌داری می‌کند و از دو عمل Push (برای افزودن آیتم) و Pop (برای حذف آیتم) پشتیبانی می‌کند.

اعمال افزودن و حذف در Stack را می‌توان مشابه وضعیت ظروف کثیفی در نظر گرفت که به منظور شسته شدن در آشپزخانه روی یکدیگر انباشته شده‌اند، عنصر (ظرف کثیف) جدید بر روی عناصر قبلی قرار می‌گیرد و هنگام حذف یک عنصر (برداشتن ظرف برای شسته شدن)، جدیدترین عنصری که به پشته اضافه شده است زودتر حذف می‌شود. از این رو به پشته، ساختمان داده‌ی LIFO نیز گفته می‌شود.

کاربرد پشته‌ها و نحوه‌ی پیاده‌سازی

دو کاربرد رایج از پشته‌ها در رایانه عبارتند از ارزیابی عبارات و فراخوانی توابع. به عنوان نمونه‌ای ملموس و ساده می‌توان گفت هنگام فراخوانی تابع، نام تابع همراه با پارامترهای آن به عنوان عنصری جدید وارد یک پشته می‌شوند. در صورتی که در این تابع، تابعی دیگر فراخوانی شود تابع دوم نیز به همین صورت وارد پشته می‌شود. به محض اینکه اجرای دستورات تابع دوم به پایان می‌رسد عمل Pop از پشته انجام می‌شود و تابع دوم از آن خارج می‌شود. به این ترتیب تابع کنونی که در حال اجراست همیشه در بالای این پشته قرار می‌گیرد.

می‌توان استک را با ظرفیت ثابت (Fixed) و یا به صورت پویا (Dynamic) پیاده‌سازی نمود. در حالت اول، تعداد بیشینه‌ی المان‌هایی که می‌تواند در استک قرار بگیرد ثابت می‌باشد، در صورتی که پشته پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ می‌دهد. به طور مشابه در صورتی که بخواهیم روی یک پشته‌ی خالی، عمل Pop را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد. در پیاده‌سازی پویای Stack، متناسب با تعداد المان‌ها ظرفیت استک تغییر می‌کند.

با توجه به محدودیت اعمالی که روی پشته‌ها قابل انجام است، Stack در زمره‌ی ساختمان‌داده‌های محدود (Restricted) طبقه‌بندی می‌شود.

نمونه ای از اعمال Push و Pop روی یک پشته
نمونه ای از اعمال Push و Pop روی یک Stack