stack چیست ؟
برای شروع یک تعریف مختصر از استک می کنم . استک یا پشته ذخیرگاه ی یکطرفه است به این معنا که اطلاعات فقط از یک طرف می تواند وارد شود و مسلماً از همان طرف هم خارج می شود پس اطلاعاتی که آخر می آیند زودتر خارج می شوند.استک در سیستم برنامه نویسی به چه کاری می آید؟ جواب آن در برنامه های بازگشتی می باشد. به این صورت که ما اگر برای هر خط برنامه شماره ای در نظر بگیریم در جایی که زیر برنامه در داخل خودش دوباره صدا می شود.شماره آخرین دستور که اجرا شده بود در داخل استک قرا می گیرد پس بالای استک همیشه خط آخرین دستور اجرا شده است و کامپیلر می داند برای ادامه باید به شماره خطی که بالای استک دوباره برگردد.
ولی شکل های پیاده سازی استک :
۱- با لیست ها معمولی( که آسان ترین روش است)
۲- با لیست های پیوندی .
در زیر من پیاده سازی استک را با لیست های معمولی را آورده ام:
const maxlength=10;
type
stack=record
elements:array[1..maxlength]of elementype;
top:integer;
end;
function full(s:stack):boolean;
begin
full:=(s.top=1);
end;
procedure makenull(var s:stack);
begin
s.top:=maxlength+1;
end;
procedure push(x: elementype; var s:stack);
begin
if not full(s) then
begin
s.top:=s.top-1;
s.elements[s.top]:=x;
end
else
writeln(‘stack if full’);
end;
function empty(s:stack):boolean;
begin
empty:=(s.top=maxlength+1);
end;
procedure pop(var s:stack);
begin
if not empty(s) then
s.top:=s.top+1
else
writeln(‘stack is empty’);
end;
توضیح روندکار:
۱-در قسمت const مقدار اولیه به متغیر maxlength داده شده است این متغیر پایین استک است.(البته در استک های رو بالا) یعنی استک ما ظرفیت ۱۰ تا عدد را دارد . لازم به ذکر است که نوع داده های که در استک قرار می گیرد را من elementype تعریف کرده ام که به جای آن از داده های استاندارد پاسکال قرار دهید.
۲-در قسمت بعد استک یک record تعریف شده است که دو قسمت دارد یکی از آنها یک آرایه است که عناصر در آن قرار می گیرد و بعدی بالای استک را نشان می دهد.
۳- تابع full پر بودن استک را نشان می دهد . در پیاده سازی استک می توان استک را روبه بالا یا رو به پایین در نظر گرفت که نشان دهنده این است که استک از کدام طرف پر می شود. در اینجا استک رو بالا است و استکه از بالا به پایین پر می شود. پس پایین ترین نقطه استک همان maxlength یعنی ۱۰ است و پر استک ۱ بودن top است. همانند شکل روبرو :
۴- پروسیجر makenull یک استک خالی ایجاد می کند برای این کار فقط کافی است بالای استک مساوی با maxlenght قرار دهیم البته چون همان خانه را نیاز داریم با اضافه یک کردن یک خانه پایین می رویم.
۵- پروسیجر push یک عدد یا کاراکتر را وارد یک سلول می کند برای این کار اول چک می کنیم که استک ما پر نشده باشد. بعد بالا استک را یکی کم می کنیم تا بالا برود و آنجایی کهtop قرار دارد عنصر را قرار می دهیم . ولی اگر استک پر بود یک پیام به ما نشان می دهد.
۵- تابع empty خالی بودن استک را به ما نشان می دهد. طبق شکل وقتی استک خالی است که بالا استک با یکی بیشتر از maxlength مساوی شود.
۶-پروسیجر pop یک عنصر از بالا استک حذف می کند. برای این کار فقط کافی است بالا ی استک را یکی پایین بیاوریم پس یک به آن اضافه می کنیم.
این استک رو بالا بود اگر روبه پایین باشد تمام این روند برعکس می شود.البته شکل های دیگری برای پیاده سازی استک وجود دارد که مهمترین آن با لیست های پیوندی است .
