آموزش ساختمان داده قسمت پنجم

1395/1/23 سعید ضیادید 2792

سلام عرض می کنم خدمت همه ی شما دوستان عزیز ..
ضیادید هستم و با جلسه ی پنجم از سری آموزش های ساختمان داده ها در خدمت شما  خواهم بود .

در این جلسه قصد داریم درباره ی دو تا از ساختار های داده ای دیگر صحبت کنیم که عبارت هستند از "پشته و صف" .
ببینید دوستان هر لیست پشت سر همی از داده ها که عمل حذف و درج در اون از یک سمت لیست انجام بگیره ، یک پشته نامیده میشه . عمل درج در پشته رو "push" عمل حذف از پشته رو "pop" و اون سمتی که تغییرات داره روش انجام میشه "top" نامگذاری می کنند .

ساختمان داده

شکل بالا نمونه ای از یک پشته هست
ببینید دوستان پس از هر عمل درج مقدار top یک واحد افزایش خواهد یافت و پس هر عمل حذف یک واحد کاهش از مقدار top خواهیم داشت .
اگر خانه های موجود در پشته ی خودمون رو از 1 تا n درنظر بگیریم ، شرایط مرزی برای پشته ی ما به دو صورت تعریف خواهند شد :
1- top=1 که نشان دهنده ی خالی بودن پشته هست .
2- top =n که نشان دهنده ی پر بودن پشته هست .

الگوریتم عمل درج در یک پشته

procedure  push(item);
     begin
         if  top=n      then
 write ("Stack is FULL")
else
 begin
top = top +1;
stack[top]=item;
end;


الگوریتم حذف از پشته

procedure    pop(item);
     begin
          if   top=0   then
              write("Stack is EMPTY")
       else
        begin
           item=stack[top];
         top=top-1;
     end;


یک نکته ی دیگه هم اینه که آخرین عنصری که به پشته وارد میشه ، اولین عنصری خواهد بود که از اون خارج میشه . به همین دلیل به پشته ها LIFO هم میگن (Last In First Out).

بیاید یک مثال ببینیم با هم .

مثال : فرض کنید یک پشته داشته باشیم که به ترتیب از پایین به بالا دارای عناصر 1 و 2 و 3 باشه . حالا وضعیت این پشته رو بعد از اعمال زیر با هم ببینیم :
 

pop x
pop y
push x
pop z
pop x
push y
push z

پاسخ این مثال رو در تصویر زیر خواهید دید :


 

آموزش ساختمان داده


کاربرد پشته ها :
1- ارزیابی عبارات محاسباتی (پیشوندی ، پسوندی و میانوندی)
2- استفاده در توابع بازگشتی (برج هانوی - دنباله ی فیبوناچی - محاسبه ی فاکتوریل یک عدد)
3- الگوریتم مسیر حرکت (Mazing)
4- پیمایش عمقی درختان و گراف ها
5- استفاده در الگوریتم های مرتب سازی مانند مرتب سازی ادغامی و سریع

صف لیستی هست که عمل افزودن داده‌ها توی اون از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام میشه .
دقیقا مثل صف نانوایی هست و مشخص هست که چون اولین داده ی ورودی به یک صف اولین داده ی خروجی از همون صف خواهد بود ، به یک صف FIFO هم میگن .
(First In First Out)

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

الگوریتم اضافه کردن در صف

Void Addqueue(int x )
{
rear=(rear+1) mode n;
if (front==rear)
Cout"the queue is empty";
else
queue[rear]=x;
}

الگوریتم حذف از یک صف

Void Delqueue(int x )
{
if (front==rear)
{
Cout"the queue is empty";
return 0;
}
else
front=(front+1) mode n;
x=queue[front];
}


چند تا نکته هم از پشته و صف میگیم :

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

ساختمان داد ها

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

آموزش ساختمان داده

3- اگه بخوایم یک پشته رو در پشته ی دیگری بدون تغییر ببینیم کافیه از یک پشته استفاده کنیم به صورت زیر

آموزش ساختمان داده

4- هروقت بخوایم یک صف رو در صف دیگری معکوس ببینیم کافیه از پشته ی دیگری استفاده کنیم


 

آموزش ساختمان داده


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