پشته و پیاده سازی در پایتون

پشته (Stack) : یک ساختمان داده ای است که عمل حذف و اضافه از بالای ان انجام میشود . یعنی در یک پشته موقعی که میخوایم یه عنصر حذف کنیم میایم اخرین عنصری که وارد پشته شده را حذف میکنیم.

پشته از سیاست LIFO(last in first out) پیروی میکنه یعنی در واقع اخرین عنصری که وارد میشه اولین عنصری میشه که حذف میشه .

به عمل اضافه کردن به پشته push میگن و به عمل حذف کردن از پشته pop میگن و top مشخص کننده عنصر بالایی پشته است (اخرین عنصری که push شده در کدام خانه است )

خب حالا میخوایم با پایتون با روش های زیر پشته رو پیاده سازی کنیم :

• list :

با استفاده از لیست ها میتونیم یه پشته پیاده سازی کنیم به این صورت که عمل push با استفاده از append و عمل pop با استفاده از همون pop انجام میشه و خب اینجا سیاست LIFO که گفتیم داره کامل پیاده سازی میشه . به این صورت که append میاد به اخر پشته یه عنصر درج میکنه و pop میاد اخرین عنصر و حذف میکنه

• Collections.deque :
• پشته را می توانیم با استفاده از کلاس deque از ماژول Collections پیاده سازی کنیم .همان متد هایی که در لیست داشتیم اینجا هم استفاده میشه append و pop

• queue.LifoQueue :
• ماژول queue دارای LIFO Queue است که اساساً Stack است. داده ها با استفاده از put وارد می شوند و با استفاده از get خارج می شوند.

همانطور که مشاهده می کنید در خط اخر براش همیشه منتظر میمونه تا عنصری در دسترس شه میتونیم به جاش ازget_nowait استفاده کنیم که در صورت خالی بودن پشته به ما error میده.

خب حالا چه کنیم با این ۳ تا پیاده سازی :))))))))

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

حالا تو روش دوم deque بر اساس doubly linked list(لیست پیوند دوگانه) ساخته شده. توی ساختار لیست پیوندی ، هر ورودی در بلوک حافظه خودش ذخیره می شه و دارای reference (مرجع )برای ورودی بعدی در لیست است. حالاdoubly linked list(لیست پیوند دوگانه) مثل همینه ، با این تفاوت که هر ورودی دارای reference (مرجع ) برای ورودی قبلی و بعدی در لیست است. واسه همین به راحتی میتونین گره ها را به هر دو انتهای لیست اضافه کنید.برای اضافه کردن ورودی جدید به ساختار لیست پیوندی فقط لازمه مرجع ورودی جدید به بالای پشته اشاره کنه و مشکلی که تو لیست داشتیم حل میشه و اینکه اینجا پیچیدگی زمانی O (1) و در لیست O (n) است .

اگه بخواین از پشته توی multi-threaded programs استفاده کنیم از روش سوم استفاده میکنیم .LifoQueue ساختارش thread-safe است . حالا این ویژگی thread-safe یه هزینه ای داره که باعث میشه هر عملیات یک زمان بیشتری صرف کنه که ولی این زمان اونقدری اهمیتی نداره ولی اگه دیدین نه اهمیت داره میتونین از deque استفاده کنید ولی چرا کلا نرفتیم سراغ اون چون که : توی deque عملیات appendو pop هر ۲ تاشون atomic هستند یعنی یه thread دیگه نمیتونه بیاد قطعشون کنه ولی توی این کلاس یه سری متد دیگه هست که atomic نیستن خب همین موضوع باعث میشه احتمال خطر باشه و سعی کنیم سراغ این راه نریم .لیستم که کلا توی multi-threaded programs برای پیاده سازی پشته سراغش نمیریم .

ولی در کل شد لیست تو پشته های بزرگ حافظه میخواد ولیdeque حل میکنه پس در حالت کلی از deque استفاده میکنیم و توی threading از LifoQueue .

امیدوارم خوشتون اومده باشه و برای توضیح بهتر و کامل تر میتونین به این سایت برین .