آموزش ساختمان داده قسمت پنجم
سلام عرض می کنم خدمت همه ی شما دوستان عزیز ..
ضیادید هستم و با جلسه ی پنجم از سری آموزش های ساختمان داده ها در خدمت شما خواهم بود .
در این جلسه قصد داریم درباره ی دو تا از ساختار های داده ای دیگر صحبت کنیم که عبارت هستند از "پشته و صف" .
ببینید دوستان هر لیست پشت سر همی از داده ها که عمل حذف و درج در اون از یک سمت لیست انجام بگیره ، یک پشته نامیده میشه . عمل درج در پشته رو "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- هروقت بخوایم یک صف رو در صف دیگری معکوس ببینیم کافیه از پشته ی دیگری استفاده کنیم
خب دوستان برای این جلسه کافیه
در جلسه ی بعدی ، نکات بیشتری در باره ی پشته و صف و همچنین ارزشیابی عبارات خواهیم گفت .
با تشکر و خدانگهدار
نظرات کاربران