مفاهیم پایه پشته (تعریف اولیه)

پشته یا stack نوعی از ساختمان داده است که همانند آرایه ها توانایی ذخیره سازی لیستی از داده های هم جنس را دارد، با این تفاوت که دیگر توانایی دسترسی به تک تک داده های آن را نداریم. بلکه فقط آخرین عنصر ذخیره شده قابل دسترسی ما خواهد بود. اصطلاحا به نحوه ذخیره سازی آنLIFO یا "Last In First Out" می گویند. به این معنی که آخرین داده ای که به پشته وارد شده، اولین داده ای است که از آن خارج می شود.

به عنوان مثال دسته ای از CD ها را که بر روی همدیگر قرار گرفته اند را تصور کنید. برای برداشتن یک CD تنها می*توانید بالاترین CD را بردارید و برای قرار دادن CD به این دسته، می*توانید آن را روی آخرین قرار دهید.
پس مسلماً برای برداشتن پایین*ترین CD باید ابتدا تمام CD های روی آن را برداریم؛ یا برای اضافه کردن یکی در وسط، باید تمام CD ها تا وسط را برداشته، CD جدید را قرار داده و سپس آن ها را سر جای خود برگردانیم.

نمونه پشته در دنیای اطراف ما زیاد دیده می شود.


تعداد زیادی بشقاب که بر روی هم قرار گرفته اند؛ به راحتی می توان گفت که همیشه بالاترین بشقاب ها تمیزتر هستند. زیرا همیشه برای هر وعده غذایی از بالاترین بشقاب ها استفاده می کنیم. و همچنین پایین ترین بشقاب ممکن است بیشتر از یک سال دست نخورده بماند.
کوهی از کتاب که برای برداشتن کتابی از وسط نتوانیم آن را کشویی بیرون بکشیم، پس مجبوریم کتاب های روی آن را در مکانی دیگر قرار دهیم تا باعث سرنگون شدن این کوه نشویم.
یک تاکسی که سرنشینان عقب مجبورند فقط از یک در وارد و خارج شوند. در صورتی که مسافری زودتر پیاده می شود، باید نزدیکتر به در بنشیند. در غیر این صورت بقیه مسافران باید برای پیاده شدن آن فرد، یک بار پیاده و دوباره سوار شوند.


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

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

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


متد Pop: که به معنی حذف کردن آخرین عنصر از پشته است.(اشاره به اولین عکس این مطلب)
IsEmpty: که در صورت خالی بودن پشته مقدار True را بر می گرداند.
[متد IsFull : که در صورت پر بودن پشته مقدار True را بر می گرداند.

در مطلب بعدی به نحوه پیاده سازی پشته در کامپیوتر خواهیم پرداخت.

پاسخ با نقل قول پاسخ با نقل قول
02-24-2012, 03:16 PM #3
matinlotfali
غریبه
پیاده سازی پشته (با استفاده از آرایه)

حال به پیاده سازی یک پشته می پردازیم.
فرض می کنیم جنس پشته از عدد صحیح (int) باشد.

1
2
3
4
5
6

class Stack
{
private int[] array;
private int top;
}


همانطور که گفته شد، پشته از یک آرایه (array) و یک اشاره گر به آخرین عنصر (top) ساخته می شود که هر دو برای اعمال encapsulation باید private تعریف شوند.

پس برای کار با private ها توابع را تعریف می کنیم.


تابع سازنده (constructor) برای مقدار دهی اولیه



1
2
3
4
5

public Stack (int length)
{
array = new int[length];
top = -1;
}



این تابع برای فضای آرایه به طول (length) نیاز دارد. این باعث می شود که پشته محدود به تعداد شود. برای رفع این مشکل در مطالب بعدی پیاده سازی با لیست پیوندی خواهیم پرداخت.
همچنین در اشاره گر top مقدار اولیه ۱- را قرار می دهیم. به این معنی که هیچ آخرین عنصری در پشته وجود ندارد و پشته خالی است.
در بعضی پیاده سازی ها در اشاره گر top مقدار اولیه ۰ را قرار می دهند. در این صورت می توان گفت این اشاره گر تعداد عناصر موجود در پشته را هم نشان می دهد و از آن می توان استفاده کرد.
در کتبی مثل Fundamental of Data Structures - Horowits Sahni و جزوه استاد شاهپریان مقدار اولیه 1- است و کتبی مثل Algorithms -Cormen معروف به CLRS مقدار اولیه 0 قرار گرفته، اما اولین عنصر آرایه با 1 شروع شده است.


تابع IsEmpty برای برسی خالی بودن

1
2
3
4
5
6
7
8
9
10

public bool IsEmpty ()
{
if (top == -1)
return true;
else
return false;
}

این تابع مقدار اشاره گر top را بررسی می کند، مسلما در صورتی که اشاره گر top با مقدار اولیه خود برابر باشد، یعنی پشته خالی است.
می توان این نتیجه را گرفت که پس از ساخته شدن یک پشته همیشه این تابع نتیجه true را بر می گرداند.


تابع IsFull برای بررسی پر بودن



1
2
3
4
5
6
7
8
9

public bool IsFull ()
{
if (top == array.Length - 1)
return true;
else
return false;
}

این تابع مقدار اشاره گر top را بررسی می کند، در صورتی که اشاره گر top به آخرین عنصر آرایه اشاره کند، یعنی پشته پر است.
در پیاده سازی هایی که مقدار اولیه اشاره گر top صفر باشد، پس پشته در حالتی پر است که top برابر طول آرایه شده باشد.
در پیاده سازی توسط لیست های پیوندی این تابع دیگر وجود نخواهد داشت. به همین دلیل در کتاب Algorithms - Cormen CLRS هیچ اشاره ای به این تابع نشده است.


تابع Push برای درج عنصر

1
2
3
4
5
6
7
8
9

public void Push (int a)
{
top++;
array[top] = a;
}

این تابع یک عنصر را پشته ذخیره می کند.
شکل زیر را در نظر بگیرید:



برای اضافه کردن یک عنصر به این پشته، ابتدا باید اشاره گر را یک خانه به جلو ببریم:




سپس خانه ای که اشاره گر به آن اشاره می کند را با مقدار ارسال شده به این تابع (a)، پر کنیم:





در صورت اجرای مجدد این تابع همین روند ادامه پیدا خواهد کرد:




مسلما تا ابد نمی توان این تابع را اجرا کرد زیرا فضای مورد استفاده در پشته محدود است.
پس باید این شرایط را در این تابع اضافه کرد. و شرطی اضافه کرد که پر شدن پشته را بررسی کند، در غیر این صورت خطا ایجاد کند.
1
2
3
4
5
6
7
8
9
10
11

public void Push (int a)
{
if (!IsFull ()) {
top++;
array[top] = a;
} else
throw new Exception ("Stack is full!");
}




تابع Pop برای حذف عنصر

1
2
3
4
5
6
7
8
9

public int Pop ()
{
int temp = array[top];
top--;
return temp;
}

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


[

ابتدا در فضایی محتویات آخرین عنصر را ذخیره می کنیم:




اشاره گر top را یک واحد کم می کنیم، با این کار دیگر آخرین عنصر در دسترس نخواهد بود و همانند این است که حذف شده باشد:


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



اما لازم است باز شرایطی را در نظر بگیریم. در صورتی که پشته خالی باشد، مقداری وجود نخواهد داشت تا از تابع خارج و یا حذف شود.
پس لازم است در این تابع بررسی کنیم که پشته خالی نباشد. و در غیر این صورت خطا ایجاد کند.
1
2
3
4
5
6
7
8
9
10
11
12

public int Pop ()
{
if (!IsEmpty) {
int temp = array[top];
top--;
return temp;
} else
throw new Exception ("Stack is empty!");
}


با این ۴ تابع، پیاده سازی کامل می شود.
در بعضی از کتب ممکن است توابع دیگری به اسم Count برای شمارش تعداد عناصر داخل پشته و یا ToArray برای تبدیل پشته به آرایه دیده شود. اما در پیاده سازی نقش مهمی ندارند.
و همچنین در بعضی کتب جدید که با زبان سی شارپ هم سو هستند، توابع IsFull و IsEmpty به شکل یک خصیصه (property) دیده می شوند. که به این شکل هستند:
نکته: در کتبی قدیمی مثل Fundamental of Data Structures in C - Horowits Sahni این توابع به صورت یک تابع مستقل و مهم مطرح شد. زیرا در آن زمان خصیصه ها (property) وجود نداشتند.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Stack
{
private int[] array;
private int top;

public Stack (int length)
{
array = new int[length];
top = -1;
}

public void Push (int a)
{
if (!IsFull) {
top++;
array[top] = a;
} else
throw new Exception ("Stack is full!");
}

public int Pop ()
{
if (!IsEmpty) {
int temp = array[top];
top--;
return temp;
} else
throw new Exception ("Stack is empty!");
}

public bool IsEmpty {
get {
if (top == -1)
return true;
else
return false;
}
}

public bool IsFull {
get {
if (top == array.Length - 1)
return true;
else
return false;
}
}