تماس درباره   صفحه اصلی
  ساختمان داده > پشته  
 
 

پشته


پشته ليست خطی است که تنها از يک انتهای آن می توان به عناصر دسترسی پيدا کرد. پشته برای نگهداری موقت داده ها در بسياری از نرم افزارها کاربرد دارد.

تعريف
نمايش پشته
پشته چندگانه
کاربردهای پشته


تعريف

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

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

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

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


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

Stack

نمايش پشته

پياده‌سازی پشته با آرايه

ساده‌ترين روش پياده‌سازی پشته استفاده از يك آرايه يك بعدی و يک متغير 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--;
  }
}


پياده سازی پشته توسط آرايه در C++


پشته چندگانه

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

n-Stack

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


پياده سازی پشته با ليست پيوندی

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

n-Stack

پياده سازی پشته توسط ليست پيوندی در C++


کاربردهای پشته

پشته در حل مسائل مختلفی کاربرد دارد که از جمله می توان به موارد زير اشاره کرد:

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


معکوس کردن ترتيب عناصر ليست

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

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

for (i:=1 to n)
Push(List[i])
end for
for (i:=1 to n)
Pop(List[i])
end for

مسير پرپيچ و خم

ماز (maze) مسير پرپيچ و خمی است که حل کننده مسئله بايد راهی را به بيرون پيدا کند. مسير و موانع در ماز از قبل تعريف شده است. يکی از ساده ترين روش ها برای پياده سازی ماز استفاده از کامپيوتر است؛ توسط يك آرايه دوبعدی n×m كه صفر بودن سلولی در آن به معني بازبودن مسير و يک بودن به معنی مانع است.

Maze

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

برج هانوی

معمای برج هانوی (Tower of Hanoi) توسط رياضيدان فرانسوی Edouard Lucas در سال 1883 اختراع شد. سه ميله A، Bو C را درنظربگيريد که روی ميله A تعداد n ديسک با اندازه های مختلف از بزرگ به کوچک روی هم قرار داده شده اند. هدف بازی برج هانوی اين است که ديسک ها با استفاده از ميله کمکی B به ميله C منتقل شوند.

Tower of Hanoi

قوانين بازی به صورت زير است:

• درهربار تنها يک ديسک را می توان انتقال داد
• تنها ديسک بالائی هر ميله را می توان به ميله ديگر منتقل کرد.
• درهيچ زمانی نمی توان ديسک بزرگ تر را روی ديسک کوچک تر قرار داد

مثال. اگر تعداد ديسک ها 3 باشد. ترتيب جابه جائی ديسک ها به صورت زير می شود.

A->C, A->B, C->B, A->C, B->A, B->C, A->C

پياده سازی با توابع بازگشتی

Tower ( n,A,B,C)
If (n=0)
  exit
else
  Tower(n-1,A,C,B)
  A->C
  Tower(n-1,B,A,C)
end if


سوالات چندگزينه ای درباره پشته


 


 


صفحه اصلی| PDF| درباره| تماس