پیاده سازی پشته با استفاده از صف – به زبان ساده

در این مطلب، چگونگی پیاده سازی پشته با استفاده از صف در ساختمان داده بیان شده است. یک ساختار داده صف موجود است که از عملیات استانداردی مانند ()enqueue و ()dequeue پشتیبانی می‌کند. نیاز به پیاده‌سازی ساختار داده «پشته» (Stack) با استفاده از صف و عملیات آن است. باید توجه داشت که امکان پیاده سازی پشته با استفاده از صف، وجود دارد. برای این کار، نیاز به دو صف است. اما لازم نیست که از صف حلقوی استفاده کنیم.

راهکار اول: پر هزینه کردن عملیات

این روش، اطمینان حاصل می‌کند که عناصری که جدید به پشته وارد شده‌اند، همیشه در ابتدای q1 قرار دارند، بنابراین، از عملیات pop فقط در صف q1 استفاده می‌شود. صف q2 برای قرار دادن هر عنصر جدید در جلوی q1 مورد استفاده قرار می‌گیرد.

1. مراحل عملیات (push(s,x در ادامه بیان شده‌اند.
   • x را در صف q2 قرار بده.
   • همه چیز را یک به یک از q1 خالی کن و در q2 قرار بده.
   • نام q1 و q2 را جا به جا کن.
2. عملیات (pop(s در ادامه بیان شده است.
   • یک عنصر را از q۱ خارج کن و آن را بازگردان.

در ادامه، پیاده‌سازی رویکرد بالا، در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) انجام شده است.

پیاده سازی پشته با استفاده از صف در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

پیاده سازی پشته با استفاده از صف در جاوا

پیاده سازی پشته با استفاده از صف در پایتون ۳

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

پیاده سازی پشته با استفاده از صف در #C

خروجی قطعه کدهای بالا به صورت زیر است.

current size: 3
3
2
1
current size: 1

روش دوم: پر هزینه کردن عملیات POP

در عمل Push، عنصر جدید همیشه در صف q1 قرار می‌گیرد. در عملیات ()pop، اگر q2 خالی باشد، همه عناصر به جز آخرین عنصر، به q2 انتقال پیدا می‌کنند. در نهایت، آخرین عنصر از صف q1 خارج و بازگردانده می‌شود.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

1. عملیات (push(s, x
   • x را در صف q1 قرار بده (فرض می‌شود که سایز q1 نامحدود است).
2. عملیات (pop(s
   • یک به یک عناصر موجود در صف q1، به جز آخرین عنصر را خالی کن و در q2 قرار بده.
   • آخرین عنصر از q1 را خارج کن؛ عنصر خارج شده، نتیجه است. آن را ذخیره کن.
   • عنصر ذخیره شده در گام قبلی را بازگردان.

پیاده سازی پشته با استفاده از صف در ++C

پیاده سازی پشته با استفاده از صف در جاوا

پیاده سازی پشته با استفاده از صف در #C

فیلم آموزش کاربردی برنامه نویسی سی شارپ در فرادرس

کلیک کنید

خروجی قطعه کدهای بالا، به صورت زیر است.

current size: 4
4
3
2
current size: 2

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

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^