پشته ها (LIFO)

پشته ها (LIFO)

پشته مجموعه ای از اشیاء است که از آخرین ورودی، اولین خروجی سریع پشتیبانی می کند (LIFO) معناشناسی برای درج و حذف. بر خلاف لیست ها یا آرایه ها، پشته ها معمولاً اجازه دسترسی تصادفی به اشیاء موجود در آنها را نمی دهند. یک قیاس مفید در دنیای واقعی برای ساختار داده پشته، پشته ای از است بشقاب ها: عملیات درج و حذف اغلب فشار و پاپ نیز نامیده می شود. صفحات گرانبها و سنگین هستند، فقط بالاترین صفحه است می تواند جابجا شود (آخرین ورود، اولین خروج). برای رسیدن به بشقاب هایی که در پشته پایین تر هستند، بالاترین صفحات باید باشند صفحات جدید به بالای پشته اضافه می شوند. و چون پشته ها و صف ها مشابه هستند. هر دو مجموعه ای خطی از آیتم ها هستند، و تفاوت در ترتیب دسترسی به موارد است: یکی یکی حذف شد با یک صف، آیتمی که اخیراً اضافه شده را حذف می‌کنید (اول وارد، اولین خروج یا FIFO). اما با یک پشته، آیتم را اخیراً حذف می کنید از نظر عملکرد، انتظار می رود پیاده سازی پشته مناسب انجام شود O(1) زمان برای عملیات درج و حذف. اضافه شده (آخرین ورود، اولین خروج یا LIFO). پشته ها طیف وسیعی از کاربردها در الگوریتم ها دارند، به عنوان مثال، در تجزیه زبان و مدیریت حافظه زمان اجرا (“پشته تماس”). آ بر روی یک ساختار داده درختی یا نموداری. الگوریتم کوتاه و زیبا با استفاده از پشته جستجو در عمق (DFS) پایتون با چندین پیاده سازی پشته که هر کدام دارند عرضه می شود ویژگی های آنها را مقایسه کنید.

لیست – پشته های ساده و داخلی ویژگی های کمی متفاوت اکنون نگاهی به آنها خواهیم داشت

و نوع لیست داخلی پایتون ساختار داده پشته مناسبی را ایجاد می کند از عملیات فشار و پاپ در زمان استهلاک O(1) پشتیبانی می کند.30 لیست های پایتون به صورت آرایه های پویا در داخل پیاده سازی می شوند که به این معنی که آنها گاهی اوقات نیاز به تغییر اندازه فضای ذخیره سازی عناصر دارند هنگامی که عناصر اضافه یا حذف می شوند در آنها ذخیره می شود. فهرست بیش از حد، فضای ذخیره سازی پشتیبان خود را به گونه ای اختصاص می دهد که هر فشار یا پاپ نیازی به آن نداشته باشد تغییر اندازه، و در نتیجه، پیچیدگی زمانی O(1) مستهلک شده دریافت می کنید نقطه ضعف این است که این باعث می شود عملکرد آنها کمتر سازگار باشد از O(1) پایدار ارائه شده توسط یک لیست پیوندی مبتنی بر درج و حذف پیاده سازی (مانند collections.deque، زیر را ببینید). از سوی دیگر فهرست‌ها دسترسی تصادفی سریع O(1) را به عناصر موجود در آن فراهم می‌کنند پشته، و این می تواند یک مزیت اضافی باشد. برای این عملیات در اینجا یک هشدار عملکرد مهم است که باید از زمان آن آگاه باشید برای دریافت عملکرد O(1) مستهلک شده برای درج و حذف، جدید موارد باید با متد append() به انتهای لیست اضافه شوند و دوباره با استفاده از pop() از انتها حذف شد. برای عملکرد بهینه، پشته‌های مبتنی بر فهرست‌های پایتون باید به سمت بالاتر در دکس‌ها و به سمت پایین‌تر کوچک شوند. افزودن و حذف از جلو بسیار کندتر است و O(n) طول می کشد. زمان، زیرا عناصر موجود باید جابجا شوند تا فضا ایجاد شود برای عنصر جدید این یک ضدالگوی عملکردی است که شما دارید باید تا حد امکان اجتناب کرد.استفاده از لیست ها به عنوان پشته: