از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
سرفصلهای مطلب
معرفی
در حالی که برخی از ساختارهای داده همه کاره هستند و می توانند در طیف گسترده ای از برنامه ها استفاده شوند، برخی دیگر تخصصی هستند و برای رسیدگی به مشکلات خاص طراحی شده اند. یکی از این ساختارهای تخصصی که به دلیل سادگی و در عین حال کاربرد قابل توجه آن شناخته شده است، این است پشته.
بنابراین، پشته چیست؟ در هسته خود، پشته یک ساختار داده خطی است که از آن پیروی می کند LIFO اصل (Last In First Out). آن را به عنوان یک پشته بشقاب در یک کافه تریا در نظر بگیرید. شما فقط صفحه ای را می گیرید که در بالا قرار دارد، و هنگام قرار دادن یک صفحه جدید، به بالای پشته می رود.
آخرین عنصر اضافه شده اولین عنصری است که حذف می شود
اما، چرا درک پشته بسیار مهم است؟ در طول سال‌ها، پشته‌ها کاربردهای خود را در زمینه‌های زیادی پیدا کرده‌اند، از مدیریت حافظه در زبان‌های برنامه‌نویسی مورد علاقه‌تان گرفته تا عملکرد دکمه‌های پشتی در مرورگر وب شما. این سادگی ذاتی، همراه با کاربرد گسترده آن، پشته را به ابزاری ضروری در زرادخانه توسعه دهندگان تبدیل می کند.
در این راهنما، مفاهیم پشته‌ها، پیاده‌سازی آنها، موارد استفاده و موارد دیگر را عمیقاً بررسی خواهیم کرد. ما تعریف می‌کنیم که پشته‌ها چیست، چگونه کار می‌کنند، و سپس، نگاهی به دو تا از رایج‌ترین روش‌های پیاده‌سازی ساختار داده پشته در پایتون خواهیم داشت.
مفاهیم اساسی یک ساختار داده پشته
در اصل، یک پشته به طرز فریبنده ای ساده است، اما دارای تفاوت های ظریفی است که به آن برنامه های کاربردی همه کاره در حوزه محاسباتی می دهد. قبل از اینکه به پیاده سازی و کاربردهای عملی آن بپردازیم، بیایید از درک کاملی از مفاهیم اصلی اطراف پشته ها اطمینان حاصل کنیم.
اصل LIFO (Last In First Out).
LIFO اصل راهنمای پشته است. به این معنی است که آخرین موردی که وارد پشته می شود اولین موردی است که خارج می شود. این مشخصه پشته ها را از سایر ساختارهای داده خطی، مانند صف، متمایز می کند.
توجه داشته باشید: مثال مفید دیگری که به شما کمک می کند سر خود را در مورد نحوه عملکرد پشته ها بپیچید این است که تصور کنید افراد وارد و خارج می شوند. آسانسور – آخرین کسی که وارد آسانسور می شود اولین کسی است که از آن خارج می شود!
عملیات اساسی
هر ساختار داده با عملیاتی که پشتیبانی می کند تعریف می شود. برای پشته ها، این عملیات ساده اما حیاتی هستند:
- فشار دادن – یک عنصر را به بالای پشته اضافه می کند. اگر پشته پر باشد، این عملیات ممکن است منجر به سرریز پشته شود.
- ترکیدن – بالاترین عنصر پشته را حذف و برمی گرداند. اگر پشته خالی باشد، تلاش برای پاپ می‌تواند باعث پایین‌رفتن پشته شود.
- زیرچشمی (یا بالا) – بالاترین عنصر را بدون حذف آن مشاهده می کند. این عملیات زمانی مفید است که بخواهید عنصر بالای فعلی را بدون تغییر وضعیت پشته بررسی کنید.
در حال حاضر، اهمیت ساختار داده پشته و مفاهیم اساسی آن باید مشهود باشد. همانطور که به جلو می رویم، به پیاده سازی آن می پردازیم و چگونگی تبدیل این اصول اساسی به کدهای عملی را روشن می کنیم.
چگونه یک پشته را از ابتدا در پایتون پیاده سازی کنیم
با درک اصول اساسی پشت پشته ها، وقت آن رسیده است که آستین ها را بالا بزنیم و به جنبه عملی کارها بپردازیم. پیاده‌سازی یک پشته، در عین سادگی، می‌تواند به روش‌های متعددی انجام شود. در این بخش، دو روش اصلی برای پیاده سازی یک پشته – با استفاده از آرایه ها و لیست های پیوندی را بررسی خواهیم کرد.
پیاده سازی پشته با استفاده از آرایه ها
آرایه ها، بودن مکان های حافظه پیوسته، یک وسیله بصری برای نشان دادن پشته ها ارائه می دهد. آنها پیچیدگی زمانی O(1) را برای دسترسی به عناصر بر اساس شاخص، تضمین می کنند که عملیات فشار سریع، پاپ و زیرچشمی را تضمین می کند. همچنین، آرایه‌ها می‌توانند حافظه کارآمدتری داشته باشند، زیرا هیچ سربار اشاره‌گر مانند لیست‌های پیوندی وجود ندارد.
از طرف دیگر، آرایه های سنتی اندازه ثابتی دارند، به این معنی که پس از مقداردهی اولیه، نمی توان اندازه آنها را تغییر داد. این می تواند منجر به الف شود سرریز پشته اگر نظارت نشود این را می توان با آرایه های پویا (مانند پایتون) غلبه کرد list) که می تواند اندازه را تغییر دهد، اما این عملیات بسیار پرهزینه است.
با تمام این مشکلات، اجازه دهید شروع به پیاده سازی کلاس پشته خود با استفاده از آرایه ها در پایتون کنیم. اول از همه، بیایید خود یک کلاس ایجاد کنیم، با سازنده ای که اندازه پشته را به عنوان پارامتر می گیرد:
class Stack:
def __init__(self, size):
self.size = size
self.stack = (None) * size
self.top = -1
همانطور که می بینید، ما سه مقدار را در کلاس خود ذخیره کردیم. این size اندازه دلخواه پشته است stack آرایه واقعی مورد استفاده برای نمایش ساختار داده پشته است و top شاخص آخرین عنصر در است stack آرایه (بالای پشته).
از این به بعد، یک روش برای هر یک از عملیات پشته اصلی ایجاد و توضیح خواهیم داد. هر یک از این روش ها در داخل موجود خواهد بود Stack کلاسی که به تازگی ایجاد کرده ایم.
بیایید با شروع کنیم push() روش. همانطور که قبلاً بحث شد، عملیات فشار یک عنصر را به بالای پشته اضافه می کند. اول از همه، بررسی می کنیم که آیا پشته برای عنصری که می خواهیم اضافه کنیم، فضای خالی باقی مانده است یا خیر. اگر پشته پر باشد، آن را بالا می بریم Stack Overflow استثنا. در غیر این صورت، ما فقط عنصر را اضافه می کنیم و آن را تنظیم می کنیم top و stack بر این اساس:
def push(self, item):
if self.top == self.size - 1:
raise Exception("Stack Overflow")
self.top += 1
self.stack(self.top) = item
اکنون می‌توانیم روش حذف یک عنصر از بالای پشته – the را تعریف کنیم pop() روش. حتی قبل از اینکه یک عنصر را حذف کنیم، باید بررسی کنیم که آیا عناصری در پشته وجود دارد یا خیر، زیرا تلاش برای بیرون آوردن یک عنصر از یک پشته خالی فایده ای ندارد:
def pop(self):
if self.top == -1:
raise Exception("Stack Underflow")
item = self.stack(self.top)
self.top -= 1
return item
در نهایت، ما می توانیم تعریف کنیم peek() روشی که فقط مقدار عنصری را که در حال حاضر در بالای پشته قرار دارد برمی‌گرداند:
def peek(self):
if self.top == -1:
raise Exception("Stack is empty")
return self.stack(self.top)
و بس! اکنون کلاسی داریم که رفتار پشته ها را با استفاده از لیست ها در پایتون پیاده سازی می کند.
پیاده سازی یک پشته با استفاده از لیست های پیوندی
لیست های مرتبط، بودن ساختارهای داده پویا، می تواند به راحتی رشد کرده و کوچک شود، که می تواند برای اجرای پشته ها مفید باشد. از آنجایی که لیست های پیوندی حافظه را در صورت نیاز تخصیص می دهند، پشته می تواند به صورت پویا رشد کرده و بدون نیاز به تغییر اندازه صریح کاهش یابد. یکی دیگر از مزایای استفاده از لیست های پیوندی برای پیاده سازی پشته ها این است که عملیات فشار و پاپ فقط به تغییرات ساده اشاره گر نیاز دارند. نقطه ضعف آن این است که هر عنصر در لیست پیوند شده دارای یک اشاره گر اضافی است که در مقایسه با آرایه ها حافظه بیشتری مصرف می کند.
همانطور که قبلاً در مقاله “فهرست های پیوندی پایتون” بحث کردیم، اولین چیزی که باید قبل از لیست پیوندی واقعی پیاده سازی کنیم یک کلاس برای یک گره است:
class Node:
def __init__(self, data):
self.data = data
self.next = None
این پیاده سازی تنها دو نقطه داده را ذخیره می کند – مقدار ذخیره شده در گره (data) و ارجاع به گره بعدی (next).
اکنون می‌توانیم به خود کلاس پشته واقعی برویم. سازنده کمی متفاوت از قبلی خواهد بود. فقط یک متغیر خواهد داشت – ارجاع به گره بالای پشته:
class Stack:
def __init__(self):
self.top = None
همانطور که انتظار می رفت، push() متد یک عنصر جدید (در این مورد گره) به بالای پشته اضافه می کند:
def push(self, item):
node = Node(item)
if self.top:
node.next = self.top
self.top = node
این pop() متد بررسی می کند که آیا عناصری در پشته وجود دارد یا خیر و اگر پشته خالی نباشد، بالاترین عنصر را حذف می کند:
def pop(self):
if not self.top:
raise Exception("Stack Underflow")
item = self.top.data
self.top = self.top.next
return item
در نهایت، peek() متد به سادگی مقدار عنصر را از بالای پشته می خواند (در صورت وجود):
def peek(self):
if not self.top:
raise Exception("Stack is empty")
return self.top.data
توجه داشته باشید: رابط هر دو Stack کلاس ها یکسان است – تنها تفاوت در پیاده سازی داخلی متدهای کلاس است. این بدان معناست که شما به راحتی می توانید بین پیاده سازی های مختلف بدون نگرانی در مورد داخلی کلاس ها جابجا شوید.
انتخاب بین آرایه ها و لیست های پیوندی به الزامات و محدودیت های خاص برنامه بستگی دارد.
نحوه پیاده سازی یک پشته با استفاده از ساختارهای داخلی پایتون
برای بسیاری از توسعه دهندگان، ساختن پشته از ابتدا، اگرچه آموزشی است، ممکن است کارآمدترین راه برای استفاده از پشته در برنامه های کاربردی دنیای واقعی نباشد. خوشبختانه، بسیاری از زبان های برنامه نویسی محبوب مجهز به ساختارهای داده داخلی و کلاس هایی هستند که به طور طبیعی از عملیات پشته پشتیبانی می کنند. در این بخش، پیشنهادات پایتون را در این زمینه بررسی خواهیم کرد.
پایتون که یک زبان همه کاره و پویا است، کلاس پشته اختصاصی ندارد. با این حال، ساختارهای داده داخلی آن، به ویژه لیست ها و کلاس deque از collections ماژول، بدون زحمت می تواند به عنوان پشته خدمت کند.
استفاده از لیست های پایتون به عنوان پشته
لیست های پایتون به دلیل ماهیت پویا و وجود روش هایی مانند این، می توانند یک پشته را به طور کاملاً مؤثر تقلید کنند append() و pop().
-
عملیات فشار – افزودن یک عنصر به بالای پشته به سادگی استفاده از آن است
append()روش:stack = () stack.append('A') stack.append('B') -
عملیات پاپ – حذف بالاترین عنصر را می توان با استفاده از
pop()روش بدون هیچ آرگومانی:top_element = stack.pop() # This will remove 'B' from the stack -
عملیات زیرچشمی دسترسی به بالا بدون پاپ می تواند با استفاده از نمایه سازی منفی انجام شود:
top_element = stack(-1) # This will return 'A' without removing it
استفاده کردن دکه کلاس از مجموعه ها مدول
این deque کلاس (مخفف صف دو پایانی) ابزار همه کاره دیگری برای پیاده سازی پشته است. برای ضمیمه‌های سریع و باز شدن از هر دو طرف بهینه‌سازی شده است، که باعث می‌شود برای عملیات پشته‌ای نسبت به فهرست‌ها کارآمدتر باشد.
-
مقداردهی اولیه:
from collections import deque stack = deque() -
عملیات فشار – مشابه لیست ها،
append()روش استفاده می شود:stack.append('A') stack.append('B') -
عملیات پاپ – مانند لیست ها،
pop()روش کار را انجام می دهد:top_element = stack.pop() # This will remove 'B' from the stack -
عملیات زیرچشمی – رویکرد مانند لیست ها است:
top_element = stack(-1) # This will return 'A' without removing it
چه زمانی از کدام استفاده کنیم؟
در حالی که هر دو لیست و deque را می توان به عنوان پشته استفاده کرد، اگر در اصل از ساختار به عنوان پشته استفاده می کنید (با ضمائم و باز شدن از یک انتها)، deque به دلیل بهینه سازی آن می تواند کمی سریعتر باشد. با این حال، برای اکثر اهداف عملی و به جز مواردی که با برنامه های کاربردی حیاتی سروکار داریم، فهرست های پایتون کافی است.
توجه داشته باشید: این بخش به پیشنهادات داخلی پایتون برای رفتار پشته مانند می پردازد. وقتی چنین ابزار قدرتمندی در دست دارید، لزوماً نیازی به اختراع مجدد چرخ (با اجرای پشته از ابتدا) ندارید.
مشکلات بالقوه مرتبط با پشته و نحوه غلبه بر آنها
در حالی که پشته ها بسیار متنوع و کارآمد هستند، مانند هر ساختار داده دیگری، از دام های احتمالی مصون نیستند. تشخیص این چالش ها هنگام کار با پشته ها و داشتن استراتژی هایی برای رفع آنها ضروری است. در این بخش، به برخی از مشکلات رایج مرتبط با پشته می پردازیم و راه هایی برای غلبه بر آنها را بررسی می کنیم.
سرریز پشته
این زمانی اتفاق می افتد که تلاش می شود یک عنصر را روی پشته ای که به حداکثر ظرفیت خود رسیده است فشار دهید. این مشکل به ویژه در محیط هایی که اندازه پشته ثابت است، مانند برخی از سناریوهای برنامه نویسی سطح پایین یا فراخوانی تابع بازگشتی، یک مشکل است.
اگر از پشته‌های مبتنی بر آرایه استفاده می‌کنید، به آرایه‌های پویا یا پیاده‌سازی‌های لیست پیوندی که اندازه خودشان را تغییر می‌دهند تغییر دهید. گام دیگر در جلوگیری از سرریز پشته، نظارت مداوم بر اندازه پشته، به ویژه قبل از عملیات فشار دادن، و ارائه پیام های خطا یا اعلان های واضح برای سرریز شدن پشته است.
اگر سرریز پشته به دلیل تماس های بازگشتی بیش از حد اتفاق می افتد، راه حل های تکراری را در نظر بگیرید یا اگر محیط اجازه می دهد، حد بازگشت را افزایش دهید.
پشته Underflow
این زمانی اتفاق می‌افتد که تلاشی برای بیرون آوردن یک عنصر از پشته خالی وجود دارد. برای جلوگیری از این اتفاق، همیشه قبل از اجرای عملیات pop یا peek بررسی کنید که پشته خالی است یا خیر. یک پیغام خطای واضح را برگردانید یا بدون از کار افتادن برنامه، زیر جریان را به خوبی مدیریت کنید.
در محیط‌هایی که قابل قبول است، هنگام بیرون آمدن از یک پشته خالی، مقدار خاصی را برای نشان دادن بی اعتباری عملیات در نظر بگیرید.
محدودیت های حافظه
در محیط‌های محدود به حافظه، حتی تغییر اندازه پویا پشته‌ها (مانند آنهایی که بر اساس لیست‌های پیوندی هستند) ممکن است منجر به فرسودگی حافظه در صورت بزرگ شدن بیش از حد آنها شود. بنابراین، مراقب میزان استفاده از حافظه کلی برنامه و رشد پشته باشید. شاید یک کلاهک نرم در اندازه پشته معرفی کنید.
نگرانی های ایمنی موضوع
در محیط‌های چند رشته‌ای، عملیات همزمان روی یک پشته مشترک توسط رشته‌های مختلف می‌تواند منجر به ناهماهنگی داده‌ها یا رفتارهای غیرمنتظره شود. راه حل های بالقوه برای این مشکل ممکن است:
- Mutexes و Locks – از mutexes (اشیاء حذف متقابل) یا قفل استفاده کنید تا مطمئن شوید که فقط یک رشته می تواند در یک زمان معین عملیات روی پشته انجام دهد.
- عملیات اتمی – از عملیات اتمی، اگر توسط محیط پشتیبانی می شود، برای اطمینان از سازگاری داده ها در طول عملیات فشار و پاپ استفاده کنید.
- پشته های موضوعی محلی – در سناریوهایی که هر thread به پشته خود نیاز دارد، استفاده از حافظه محلی thread را در نظر بگیرید تا به هر thread نمونه پشته جداگانه خود بدهید.
در حالی که پشته ها واقعا قدرتمند هستند، آگاهی از مشکلات بالقوه آنها و اجرای فعال راه حل ها، برنامه های کاربردی قوی و بدون خطا را تضمین می کند. شناخت این تله ها نیمی از نبرد است – نیمی دیگر اتخاذ بهترین شیوه ها برای رسیدگی موثر به آنهاست.
نتیجه
پشته ها، علی رغم ماهیت به ظاهر ساده شان، زیربنای بسیاری از عملیات های اساسی در دنیای محاسبات هستند. از تجزیه عبارات پیچیده ریاضی گرفته تا مدیریت فراخوانی توابع، کاربرد آنها گسترده و ضروری است. همانطور که ما در درون و برون این ساختار داده سفر کرده ایم، واضح است که قدرت آن نه تنها در کارایی بلکه در تطبیق پذیری آن نهفته است.
با این حال، مانند همه ابزارها، اثربخشی آن به نحوه استفاده از آن بستگی دارد. فقط مطمئن شوید که درک کاملی از اصول، مشکلات احتمالی و بهترین شیوه‌های آن دارید تا مطمئن شوید که می‌توانید از قدرت واقعی پشته‌ها استفاده کنید. چه از ابتدا یکی را پیاده سازی کنید یا از امکانات داخلی در زبان هایی مانند پایتون استفاده کنید، این استفاده آگاهانه از این ساختارهای داده است که راه حل های شما را متمایز می کند.
منتشر شده در 1402-12-26 03:20:02
