From Wikipedia, the free encyclopedia
پشته[1][2] (به انگلیسی: stack) یکی از انواع دادهساختارها[3] (ساختمان داده) است و برای ذخیره و بازیابی دادهها کاربرد دارد. پشته در طراحی و پیادهسازی سیستمهای نرمافزاری و سختافزاری، فراوان به کار میرود. شیوهٔ عملکرد پشته بر اساس سیاست LIFO است.
ساختارهای خطی دادهها |
---|
آرایه |
پشته (stack) ساختمان داده ای است که از لیست یا فهرست برای سازماندهی داده ها استفاده میکند و در عین حال از انتزاع نیز پشتیبانی میکند و یک نوع داده انتزاعی را فراهم میسازد. در پشته عمل اضافه کردن و حذف عنصر، فقط در یک طرف آن، بنام بالای پشته انجام میشود. یعنی عنصری که از همه دیرتر وارد پشته شد، از همه زودتر از پشته حذف میگردد. بهمین دلیل گفته میشود که پشته از سیاست خروج به ترتیب عکس ورود (LIFO) پیروی میکند.
عملیات های پشته در ساختمان داده ها: از آنجایی که عناصر پشته فقط از یک طرف (بالای پشته) قابل دستیابی اند. پس عملیات های متعددی را میتوان روی پشته انجام داد که چند عملیات زیر بهعنوان عملیات اصلی پشته مطرح اند:
در حقیقت پشته، یکی از سه بخش تخصیص یافته به یک برنامه در حال اجرا در حافظه (RAM) میباشد. پس از اجرای هر برنامه کاربردی آن برنامه برای پردازش توسط پردازشگر، به سه بخش در حافظه تقسیم و ذخیره میگردد تا در دسترس پردازشگر قرار بگیرد. این سه بخش شامل موارد زیر هستند:
LIFO کوتاهشدهٔ عبارت Last In First Out (آخرین ورودی از همه زودتر خارج میشود) است. این سیاست اساس کار پشتهها را تشکیل میدهد و به مفهوم آن است که آخرین دادهٔ ذخیره شده در پشته، نخستین دادهای است که بازیابی میشود.
FIFO کوتاهشدهٔ عبارت First In First Out (اولین ورودی از همه زودتر خارج میشود) است. این سیاست اساس کار صفها را تشکیل میدهد و به مفهوم آن است که اولین دادهٔ ذخیره شده در صف، نخستین دادهای نیز هست که بازیابی میشود.
با توجه به آنچه گفته شد، روشن است که در سیاست LIFO، ورود و خروج دادهها، از یک سمت صورت میگیرد (در واقع تنها یک سمت تودهٔ دادهها باز است) در حالی که در سیاست FIFO، ورود و خروج دادهها، از دو سمت صورت میگیرد (یک سمت برای ورودی و یک سمت برای خروجی) و ما به دو سر تودهٔ دادهها دسترسی خواهیم داشت (یکی برای ورود و دیگری برای خروج).
پشتهها ممکن است با هر یک از انواع دادهساختارهایی مثل آرایه،[4] لیست پیوندی[5] و… پیادهسازی شوند. صرفنظر از اینکه از کدامیک استفاده میکنیم، پیادهسازی دو تابع Push (برای گذاشتن داده) و Pop (برای برداشتن داده) بسیار مهم است. نکتهٔ مهم دیگر در پیادهسازی پشته، نگهداشتن اشارهگری به آخرین داده است که اصطلاحاً به آن Top گفته میشود. اگر فرض کنیم که پشته با آرایه پیادهسازی شده باشد، شبهکد[6] تابعهای Push و Pop به صورت زیر خواهد بود:
procedure Push(data d)
begin
stack[top]:=d; //here "stack" is the array that stores data
top:=top+1; //here "top" is a pointer to above of top element
end;
function Pop: data
begin
top:=top-1; //here "top" is a pointer to above of top element
result:=stack[top]; //here "stack" is the array that stores data
end;
پیچیدگی زمانی[7] اضافه کردن یک عنصر به یک پشته یا برداشتن یک عنصر از روی یک پشته با پیادهسازی آرایهای، از (O(1 است. این موضوع با توجه به شبهکد نمونهای که در قسمت قبل برای پیادهسازی با آرایه طرح شدهاست، کاملاً قابل توجیهاست.
میبینیم که در پیادهسازی آرایهای، پیچیدگی زمانی افزودن و برداشتن عنصرها از پشته و به پشته، با هم متفاوت است. با این وجود اگر پشته را با لیستهای پیوندی پیادهسازی کنیم، به علت ساختار خاص این لیستها، هردوی این اعمال برای پشته (و به همین شکل برای صف)، دارای پیچیدگی زمانی از (O(1 خواهد بود.
هنگام پیادهسازی پشته، باید حالتهای خاص زیر را هم در نظر گرفت:
پشتهها در زمینههای بسیاری به کار میروند که البته در هر زمینه کارایی مشابهی هم دارند. پشتهها برای محاسبهٔ یک عبارت ریاضی به طوری که ابتدا عملوند[11]ها و سپس عملگر[12]ها در پشته قرار میگیرند، به کار میروند. علاوه بر این، برای مدیریت حافظهٔ موردنیاز برنامه، نگهداری روند فراخوانی تابعهای مختلف در برنامه، برای پیادهسازی الگوریتم[13] جستجوی عمق اول[14] و… نیز از پشتهها استفاده میشود.
در سیستمهایی که به شدت به پشتهها وابستهاند، علاوه بر تابعهایی که گفته شد، تابعهای دیگری نیز برای آسانتر شدن کار پیادهسازی میشوند و به این ترتیب پشتهها توسعه پیدا میکنند. برخی از این اعمال را در زیر شرح میدهیم:
علاوه بر اینها، از ترکیب صف و پشته، دادهساختار جدیدی[19] هم ایجاد شدهاست که هم امکان افزودن عنصرها را از دوسوی تودهٔ دادهها میدهد و هم امکان برداشتن آنها را.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.