ساختمان داده پشته stack

ساختمان داده پشته stack 

پشته (stack) ساختمان داده ای است که از لیست برای سازماندهی داده ها استفاده میکند و در عین حال از انتزاع نیز پشتیبانی میکند و یک نوع داده انتزاعی را فراهم میسازد. در پشته عمل اضافه کردن وحذف عنصر، فقط در یک طرف آن، بنام بالای پشته انجام میشود. یعنی عنصری که از همه دیرتر وارد پشته شد، از همه زودتر از پشته حذف میگردد. بهمین دلیل گفته میشود که پشته از سیاست خروج به ترتیب عکس ورود (LIFO) پیروی میکند.

عملیات های پشته:

از آنجایی که عناصر پشته فقط از یک طرف (بالای پشته) قابل دستیابی اند. پس عملیات های متعددی را میتوان روی پشته انجام داد که چند عملیات زیر بعنوان عملیات اصلی پشته مطرح اند:

• Push : که عنصری را به بالای پشته اضافه میکند.
• Pop : که عنصر بالای پشته را حذف میکند.
• Peek : که عنصر بالای پشته را بازیابی میکند ولی حذف نمیکند.
• StackEmpty : که خالی بودن پشته را تست میکند.
• Clear  : تمام عناصر پشته را حذف میکند.
• Contains : مشخص میکند که عنصری در پشته وجود دارد یا خیر.
• CopyTo : محتویات پشته را درآرایه ای از نوع Object کپی میکند.

 

کلاس Stack :

در C# کلاسی بنام Stack برای استفاده از ساختمان داده ی پشته فراهم شده است که تمام عملیات ها و خواص بالا را دارد. این کلاس برای ذخیره سازی عناصر پشته از یک بافر حلقوی استفاده میکند که موجب میشود، حافظه مورد نیاز برای ذخیره ی عنصری که در پشته قرار میگیرد بطور پویا تخصیص یابد. این کلاس در فضای نام Collections وجود دارد.

 

متدهای سازنده کلاس Stack :

برای استفاده از کلاس Stack باید اشیایی از آن ایجاد کرد. به سه روش میتوان شیء پشته را ایجاد کرد.

• سازنده پیش فرض، پشته ای خالی ایجاد میکند که ظرفیت آن 10 مقدار است. سازنده ی پیش فرض بصورت زیر فراخوانی میشود:

Stack   muStack  =  new  Stack();

• روش دوم برای ایجاد شیء پشته این است که آنرا از شیء کلکسیون دیگری ایجاد کنید. برای مثال میتوانید آرایه ی موجود را بعنوان پارامتر به سازنده پشته بفرستید تا پشته ای از عناصر آن آرایه ایجاد شود:
• روش سوم برای ایجاد شیء پشته این است که ظرفیت اولیه آن را تعیین کنید. از این روش وقتی استفاده میشود که تعداد عناصر پشته از قبل مشخص است. این روش کارایی برنامه را افزایش میدهد.

 

خاصیت Count در کلاس Stack تعداد عناصر موجود در پشته را مشخص میکند. در پشته خالی مقدار آن صفر است. از این خاصیت برای تشخیص خالی بودن پشته استفاده میکنند و در نتیجه در بعضی از پیاده سازی های پشته، متد StackEmpty را پیاده سازی نمیکنند.

 

متدهای کلاس  Stack:

• Push : این متد، برای پشته ای از نوع صحیح بصورت زیر بکار میرود:

Push (int  item);

       item به بالای پشته اضافه میشود.

 

• Pop : این متد عنصر بالای پشته را حذف میکند و آن عنصر را برمیگرداند. برای پشته صحیح بصورت زیر بکار میرود:

int  Pop();

 

• Peek : این متد، که عنصر بالای پشته را برمیگرداند برای پشته نوع صحیح بصورت زیر بکار میرود:

int  Peek ();

این عملیات معادل یک عمل Pop و سپس یک عمل Push برای همان عنصر است.

 

• Clear  : این متد، تمام عناصر پشته را حذف میکند و احتمالا ظرفیت آنرا به ظرفیت اولیه برمیگرداند. یک کاربرد خوب این متد وقتی است که خطایی در پردازش پشته وجود داشته باشد:

Void  Clear();

 

• Contains : مشخص میکند که آیا عنصرخاصی در پشته وجود دارد یا خیر. اگر وجود داشته باشد، مقدار true وگرنه   false برمیگرداند. از این متد برای جست وجوی عنصری در پشته استفاده میکنیم که در بالای پشته نیست. این متد برای پشته صحیح بصورت زیر بکار برده میشود:

Contains (int  item);

 

• CopyTo : این متد محتویات پشته را درآرایه ای از نوع Object کپی میکند. این متد بصورت زیر بکار برده میشود:

CopyTo (array ,  index);

        array  آرایه ای است که محتویات پشته باید در آن کپی شوند و index مشخص میکند محتویات پشته با شروع از چه اندیسی در آرایه array کپی شوند، عناصر پشته به ترتیب LIFO در آرایه کپی میشوند بطوریکه گویی از پشته Pop شده اند و در آرایه قرار گرفته اند.

 

• ToArray : این متد نیز محتوای پشته را در آرایه کپی میکند با این تفاوت که نمیتوان اندیس شروع کپی را در آرایه مقصد تعیین کرد.