ساختمان های داده در c (پشته)

[shirin71]

در اينجا به تعريف ساختمان داده پشته پرداخته، كاربردهايي از آن را مطرح خواهيم كرد. پشته ساختمان داده اي است كه عمل حذف و اضافه كردن عناصر آن،از طرف بالاي پشته انجام مي شود. به همين دليل آن را ساختمان داده lifo مي نامند كه به معناي خروج به ترتيب عكس ورود است.

[shirin71]

نوع داده انتزاعي پشته


با توجه به عملكرد پشته، مي توان آن را به صورت يك نوع داده انتزاعي تعريف كرد:




adt پشته


مجموعه اي از عناصر داده ها:


مجموعه اي از عناصر مرتب كه از يك طرف قابل دستيابي اند و اين طرف، بالاي پشته نام دارد.


عمليات اصلي:


•ايجاد پشته:پشته خالي را ايجاد مي كند.


•تست خالي بودن پشته: خالي بودن پشته را تست مي كند.


•افزودن عنصر به بالاي پشته:عنصري را به بالاي پشته اضافه مي كند.


•حذف عنصر از بالاي پشته: عنصري را از بالاي پشته حذف مي كند.


•بازيابي عنصر بالاي پشته: عنصري را از بالاي پشته بازيابي مي كند، ولي حذف نمي كند.

[shirin71]

پياده سازي پشته


براي پياده سازي پشته،راجع به پشته اي از كتاب ها فكر كنيد كه دريك قفسه ي كتاب روي هم قرار دارند. مي توان كتابي را در بالاي پشته قرار داد يا كتابي را از بالاي پشته برداشت.

[shirin71]

اين مفهوم پشته را به دو شكل مي توان پياده سازي كرد:




1.پياده سازي خطي (Linear)


2.پياده سازي پيوندي (Linked)

[shirin71]

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

در اين روش، براي ذخيره عناصر پشته از آرايه استفاده مي كنيم و براي مدل سازي اين نوع پشته از متغيري به نام myTop براي نگهداري بالاي پشته استفاده خواهيم كرد.


بنابراين، داده هاي مورد نياز براي پشته عبارتند از:


• آرايه اي كه عناصر پشته را نگهداري كند.


• يك متغير صحيح كه بالاي پشته را مشخص نمايد.

[shirin71]

تعريف پشته براساس آرايه


باتوجه به اين كه آرايه را به عنوان بستر نمايش پشته انتخاب كرديم، پشته اي از نوع صحيح را مي توان به صورت زير تعريف كرد:

#define SIZE 100
struct stack {
int myTop;
int items[SIZE];
}

[shirin71]

پياده سازي عمل ايجاد پشته


عمل ايجاد پشته، بايد يك آرايه و يك متغير نشان دهنده بالاي پشته را تعريف كند و پشته خالي را ايجاد نمايد. متغير نشان دهنده بالاي پشته، myTop است، كه در پشته خالي، برابر با 1_ است. بنابراين، عمل ايجاد پشته به صورت زير پياده سازي مي شود:


#define SIZE 100
struct stack {
int myTop;
int items[SIZE];
};
stack s;
s.myTop = -1;

[shirin71]

پياده سازي عمل تست خالي بودن پشته


اگر sپشته موردنظر و myTopنشان دهنده عنصر بالاي پشته باشد، s.myTOP درپشته خالي برابر با 1- است. بنابراين، درطول اجراي برنامه مي توان براي تست خالي بودن پشته، از شرط s.myTop == -1 استفاده كرد:

if(s.myTop == -1)
/*پشته خالي است */
else
/*پشته خالي نيست */


عمل empty() را مي توان به صورت زير پياده سازي كرد:

int empty(stack *s)
{
if(s -> myTop == -1)
/* مقدار 1 ارزش درستي دارد */ return 1;
else
/* مقدار 0 ارزش درستي دارد */ return 0;
}

[shirin71]

پياده سازي عمل حذف از پشته


pop() سه وظيفه زير را انجام مي دهد:



1.اگر پشته خالي باشد، پيام اخطار را چاپ كرده اجراي برنامه را خاتمه مي دهد.


2.عنصر بالاي پشته را حذف مي كند.


3.عنصر بالاي پشته را به برنامه فراخوان برمي گرداند.



اين تابع را مي توان به صورت زير پياده سازي كرد (براي پشته نوع صحيح):

int pop(stack *s)
{
if(empty(s))
{
printf("Stack underflow");
exit(1); /* exit from program*/
}
return s -> items[(s -> myTop)--];
}



در حين اجراي برنامه، پس از تشخيص وضعيت خالي بودن پشته، نيازي به توقف اجراي برنامه نيست،بلكه بهتر است تابع pop() سيگنالي به برنامه ي فراخوان بفرستد و برنامه براساس اين سيگنال تصميمات لازم را اتخاذ نمايد سيگنال مي تواند مقداري باشد كه از طريق پارامتر مبادله مي شود. چنين تابعي را popAndTest() ناميده به صورت زير مي نويسيم:

void popAndTest(stack *s, int *x, int *underflow)
{
if(empty(s))
*underflow = 1;
else
{
*x = s -> items[(s -> myTop) --];
*underflow = 0;
}
}


در اين تابع، s پشته و x مقداري است كه توسط تابع برگردانده مي شود و پارامتر underflow به عنوان سيگنال عمل مي كند. برنامه نويس پس از فراخواني تابع، بايد به صورت زير عمل كند:

popAndTest (&s, &x, &underflow);
if(underflow)
/* پشته خالي است كه بايد عمل مناسبي انجام شود */
else
/* x برگردانده مي شود كه مي تواند از آن استفاده كند */

[shirin71]

پياده سازي عمل افزودن به پشته


اين عمل به صورت زير نوشته مي شود:

void push(stack *s, int x)
{
s -> items[++(s -> myTop)] = x;
}


تابع push() را مي توان طوري نوشت كه در صورت بروز حالتسرریز پيام مناسبي صادر نموده اجراي برنامه را خاتمه دهد:


void push(stack *s, int x)

{

if(s -> myTop == SIZE-1)

{

printf("Stack overflow.");

exit(1);

}

else

s -> items[++(s -> myTop)] = x;

}


اين وضعيت چندان مناسب نيست، اما بهتر از وضعيتي است كه تلاش شود عنصري از پشته در آرايه ي پر قرار گيرد. بهترين حالت اين است كه تابعي به نام pushAndTest() نوشته شود تادرصورت بروز سرريز،سيگنالي به برنامه فراخوان بفرستد وبرنامه براساس آن تصميم گيري كند. اين تابع را مي توان به صورت زير نوشت:

void pushAndTest(stack *s, int x, int *overflow)
{
if(s -> myTop == SIZE - 1)
*overflow = 1;
else
{
*overflow = 0;
s -> items[++(s -> myTop)] = x;
}
}

[shirin71]

پياده سازي عمل بازيابي از پشته


عمل بازيابي از پشته، عنصر بالاي پشته را بازيابي مي كند، ولي آن را از پشته حذف نمي كند.


اين تابع را مي توان به صورت زير نوشت:

int top(stack *s)
{
if(empty(s))
{
printf("Stack underflow.");
exit(1);
}
else
return(s -> items[s -> myTop]);
}


اين تابع را مي توان به صورت زير نوشت:

void topAndTest(stack *s, int *x, int *underflow)
{
if(empty(s))
*underflow = 1;
else
{
*x = s -> items[s -> myTop];
*underflow = 0;
}
}