تبلیغات
فناوری اطلاعات و ارتباطات - پشته
به وبلاگ آموزشی فناوری اطلاعات و ارتباطات خوش آمدید ....... امید است که از مطالب آموزشی نهایت استفاده را برده باشید با نظرات پر بارتان من را در اداره و سر و سامان دادن به وبلاگ یاری نمایید .......... با تشکر ...... مدیریت بلاگ

تبلیغات پیامکی


بازدید : مرتبه
تاریخ : یکشنبه 28 فروردین 1390

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

 

جهت مشاهده ادامه به ادامه مطلب مراجعه نمایید ...

تعریف

پشته لیست خطی است كه عملیات حذف و اضافه تنها از یك طرف آن به نام 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++




طبقه بندی: ساختمان داده ها، 
ارسال توسط عباس غلامی
آرشیو مطالب
نظر سنجی
نظرتون در مورد وبلاگ چیه ....





پیوند های روزانه
امکانات جانبی

قالب وبلاگ

پیامک عاشقانه