[نکات] آرایه - صف و پشته - نسخه‌ی قابل چاپ

[نکات] آرایه - صف و پشته - Masoud05 - 29 آبان ۱۳۸۹ ۱۲:۳۳ ق.ظ

عمل push , pop درپشته پیاده سازی شده با لیست پیوندی همانند حذف و درج از اول لیست می باشد (بر عکسش هم پس درسته یعنی با یه لیست و نگه داری آدرس اولین عنصر براحتی در زمان (O(1 کارهای پشته رو انجام میدین)

صف دو سره - hamidi66 - 04 مهر ۱۳۹۰ ۱۱:۲۱ ب.ظ

اصطلاحات معادل:
صف دو طرفه، Deque، Dequeue، Double-Ended Queue

تعریف:
یک لیست خطی است که داده های آن را می توان از هر دو طرف اضافه یا حذف کرد، ولی درج و حذف داده از وسط آن امکان پذیر نمی باشد.
دقت کنید که هیچ شباهتی به صف معمولی نداره. علاوه بر این، دقت کنید که عملکردش می تونه با پشته دو طرفه متفاوت باشه.

با اضافه کردن محدودیت هایی تو اضافه کردن یا حذف عناصر جدید در ابتدا یا انتهای صف دو طرفه، می تونیم ساختارهای صف معمولی و پشته معمولی رو باهاش پیاده سازی کنیم.

[نکات] آرایه - صف و پشته - yaser_ilam_com - 01 اردیبهشت ۱۳۹۱ ۰۹:۴۸ ب.ظ

پیچیدگی زمانی در پیاده‌سازی آرایه‌ای

پیچیدگی زمانی اضافه کردن یک عنصر به یک پشته یا برداشتن یک عنصر از روی یک پشته با پیاده‌سازی آرایه‌ای، از (O(1 است. این موضوع با توجه به شبه‌کد نمونه‌ای که در قسمت قبل برای پیاده‌سازی با آرایه طرح شده‌است، کاملاً قابل توجیه‌است.

می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از پشته و به پشته، با هم متفاوت است. با این وجود اگر پشته را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای پشته (و به همین شکل برای صف)، دارای پیچیدگی زمانی از (O(1 خواهد بود.

چند حالت نامطلوب

هنگام پیاده‌سازی پشته، باید حالت‌های خاص زیر را هم در نظر گرفت:

هنگام صداکردن تابع Push در پشته‌ها، در صورتی که پشته پر باشد، خطای سرریز رخ خواهد داد. البته این اتفاق در صورتی می‌افتد که ظرفیت پشته تعیین‌شده باشد و نتوانیم آن را افزایش دهیم. برای مثال، خطای Stack Overflow در زمانی که حافظهٔ در نظرگرفته شده برای برنامه کافی نباشد، از طرف سیستم‌عامل تولید می‌شود.
هنگام صداکردن تابع Pop در پشته‌ها، در صورتی که پشته خالی باشد، خطای پاریز رخ می‌دهد.
هنگام صداکردن تابع Enqueue در صف، اگر صف پر باشد، خطای سرریز رخ خواهد داد. البته این خطا در صورتی اتفاق می‌افتد که ظرفیت پشته تعیین‌شده و محدود باشد و نتوانیم آن را افزایش دهیم.
هنگام صداکردن تابع Dequeue در صف، اگر صف خالی باشد، خطای پاریز اتفاق می‌افتد.

روند توسعه

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

مشابه‌سازی: با یک بار Pop کردن و دوبار Push کردن بالاترین دادهٔ پشته، این داده به دو دادهٔ مشابه تبدیل می‌شود (به عبارت دیگر تکثیر می‌شود).
برداشت: بالاترین داده Pop می‌شود ولی اشاره‌گر Top تغییر نمی‌کند؛ به عبارت دیگر، داده به دست ما می‌رسد ولی کماکان در پشته هم وجود دارد.
جابه‌جایی: بالاترین دو دادهٔ پشته، با هم جابه‌جا می‌شوند.
جابه‌جایی کلی: همه عناصر پشته یکی به سمت پایین جابه‌جا می‌شوند و پایین‌ترین داده در جای بالاترین داده قرار می‌گیرد.
علاوه بر این‌ها، از ترکیب صف و پشته، داده‌ساختار جدیدی هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.

منبع : به نظر ویکی پدیا

[نکات] آرایه - صف و پشته - yaser_ilam_com - 02 اردیبهشت ۱۳۹۱ ۰۱:۴۳ ق.ظ

صف اولویت‌دار

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است.
در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی، اولین داده خروجی نیز خواهد بود.
اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.
به عنوان مثال، فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:

صف انتظار CPU یک صف اولویت‌دار است. در نتیجه CPU در اولین فرصت ممکن ابتدا پردازش شماره ۳ را انجام می‌دهد. سپس پردازش شماره ۲ و ...
تذکر: روش‌های زمانبندی CPU جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم عامل است. بررسی تمامی روش‌های زمانبندی و مزایا و معایب آنها خارج از بحث فعلی ما است.
برای پیاده‌سازی صف اولویتی عموما از آرایه استفاده می‌شود. من در اینجا سه روش مختلف را شرح می‌دهم.

۱/ پیاده‌سازی با استفاده از آرایه نامرتب:
در این روش زمانی که داده‌ای وارد صف می‌شود، همچون صف عادی در انتهای آن قرار می‌گیرد. به عنوان نمونه، داده‌های مثال زمانبندی CPU به صورت زیر در آرایه قرار می‌گیرند:

هر عنصر آرایه ساختمانی مرکب از دو عنصر شماره پردازش و اولویت آن است. هر پردازش جدید به انتهای صف اضافه می‌شود، که از مرتبه ( O( 1 است:

اما زمانی که قرار است پردازشی از آن خارج شود، باید تک تک عناصر بررسی شوند، تا پردازشی با بیشترین اولویت انتخاب شود. این فرآیند از مرتبه ( O( n است.

۲/ پیاده‌سازی با استفاده از آرایه مرتب:
در این روش بر خلاف روش قبل، آرایه بر اساس اولویت‌ها مرتب شده است.

زمانی که داده‌ای وارد صف می‌شود، بر اساس اولویت خود در محل مناسب قرار می‌گیرد:

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

۳/ پیاده‌سازی با استفاده از آرایه نیمه‌مرتب (درخت heap):
در این روش داده‌ها بر اساس اولویت آنها در یک درخت min-heap وارد می‌شوند:

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

در یک درخت min-heap عنصری با کوچکترین کلید همواره در ریشه قرار دارد. در نتیجه عمل حذف گره ریشه از درخت min-heap، کوچکترین عنصر آن را به ما می‌دهد. این عمل بر اساس بحث‌های پیشین از مرتبه ( O( log n است. عمل درج نیز در min-heap از همین مرتبه است.
عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد، روی هم رفته از مرتبه اجرایی n هستند. اما در روش آرایه نیمه‌مرتب این مرتبه به log n کاهش می‌یابد. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارآیی بسیار بهتری دارد.

منبع :به نظر ویکی پدیا