آخرین اخبار:

نمایش پروفایل

0			0

تعريف
پشته ليست خطی است كه عمليات حذف و اضافه تنها از يك طرف آن به نام Top صورت می‌ گيرد. در هر لحظه فقط عنصر بالائی پشته قابل دسترس است.

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

می توان پشته را ساختمان داده (first in, last out) FILO هم ناميد زيرا اولين داده ای که در پشته ذخيره می شود آخرين داده ای است که خارج می شود.

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

--------------------------------------------------------------------------------

مثال. در زير پشته ای از اعداد صحيح نشان داده شده است. عدد 34 به بالای آن اضافه شده است.

نمایش پروفایل

0			0

نمايش پشته
پياده‌سازی پشته با آرايه
ساده‌ترين روش پياده‌سازی پشته استفاده از يك آرايه يك بعدی و يک متغير Top است.

کد: 

const int MaxSize = 100;

ItemType Stack[MaxSize];

int Top;

Top انديس عنصر بالای پشته Stack را نگه می دارد. Top=0 دلالت بر خالی بودن پشته دارد.

برای Push کردن يک داده جديد به پشته، Top يکی اضافه می شود و داده جديد در آرايه در انديس Top درج می کند.

کد: 

void Push( const ItemType &Item)

{

if (Top == MaxSize){

  cerr << "ERROR: Cannot insert -- Stack is full" << endl;

  exit(1);

  }

else{

  Top++;

  Stack[top] = Item;

  }

}

برای Pop کردن از پشته، داده ای که در انديس Top قرار دارد برگردانده می شود و Top يک واحد کم می شود.

کد: 

void Pop(ItemType & Item)

{

if (IsEmpty()){

  cerr << "ERROR: Cannot remove -- Stack is empty" << endl;

  exit(1);

  }

else{

  Item = Stack[Top];

  top--;

  }

}

نمایش پروفایل

0			0

پشته چندگانه
اگر نياز به دو پشته در برنامه باشد از يك آرايه يك بعدی استفاده می ‌شود كه Top[1]‌ ابتدای پشته اول و Top[2]‌ ابتدای پشته دوم است. پشته ها به سمت همديگر رشد می‌كنند.

وقتی به n پشته احتياج داريم. آرايه به n قسمت تقسيم می شود که هر قسمت به يک پشته اختصاص داده می شود. برای هر پشته b[i] پايين ترين مکان پشته و t[i] بالای پشته i را نشان می دهد. اگر t[i]=b[i] باشد يعنی پشته i خالی است و اگر t[i]=b[i+1] يعنی پشته i ام پر شده است.

پياده سازی پشته با ليست پيوندی
چون پشته دنباله ای از عناصر داده ای است می توان آنرا در ليست پيوندی ذخيره کرد. اعمال درج و حذف از ابتدای ليست صورت می ‌گيرند. Top آدرس اولين عنصر ليست را نگه می دارد.

معکوس کردن ترتيب عناصر ليست
چون عناصر عکس ترتيب ورود از پشته خارج می شود پشته روش مناسبی برای معکوس کردن ترتيب عناصر يک ليست است. برای اين کار کافی است ابتدا کليه عناصر به ترتيب در پشته Push شوند سپس يکی يکی از پشته حذف می شوند. ليست خروجی حاصل عکس ليست اوليه است.

مثال. الگوريتم زير ترتيب عناصر آرايه List با n عنصر را عکس می کند.

کد: 

for (i:=1 to n)

Push(List[i])

end for

for (i:=1 to n)

Pop(List[i])

end for

حالت موضوعی \| حالت خطی پشته
نویسنده	پیام