شما در این ویدیو در قالب دو مثال با کاربرد پشته آشنا میشوید.
مثال اول مساله تطابق پرانتزگذاریهاست. کاربر یک عبارت ریاضی پرانتزگذاری شده وارد میکند و برنامه باید چک کند که آیا اپرانتزگذاری عبارت معتبر است یا خیر. و در مثال دوم با هم کد ماشین حساب را با هم یاد میگیریم، که در این مساله اولویت عملگرها نیز در نظر گرفته شده است.
مشاهده این آموزش در آپارات
تمرینهای جلسه چهارم و پنجم درس ساختمان داده
1- اگر اعداد زیر را به ترتیب وارد پشته کنیم کدام یک از خروجی های زیر را نمیتوان با هیچ ترتیبی به دست آورد (اعداد را از چپ به راست بخوانید)
1,2,3,4,5,6
الف) 123564 ب) 324651 ج) 432165 د) 215364
2-عبارت پسوندی معادل عبارت (A+B) * D + E / (F + A * D)
الف) AB+D*E+F/A+D* ب) AB+D*EFAD*+/+
ج) ABDEFAD+*+/+* د) AB+DE+FAD*+/
3- حداقل اندازه پشته برای تبدیل عبارت میانوندی a/(b-c*(d+e)) به معادل پسوندی کدام است؟
(اگر الگوریتم تبدیل میانوندی به پسوندی را با ورودی بالا اجرا کنیم حداکثر چند خانه از پشته اشغال میشود؟)
الف) 4 ب)5 ج) 6 د)3
4-برنامه ای بنویسید که با استفاده از پشته ها جفت بودن علامتهای { } و ( ) و [ ]در یک رشته شامل حروف و علامت بررسی کند.
مثال: رشته {AB(C)[EFG]} یک رشته قابل قبول و ({BC}} یک رشته غیرقابل قبول است.
5- برنامه ای بنویسید که با استفاده از ساختمان داده صف، محتویات یک پشته را معکوس کند.
6- در شبه کد زیر تابع push عملیات اضافه کردن به پشته، تابع pop عملیات حذف از پشته و تابع isEmpty خالی بودن پشته را چک میکند. تابع زیر چه عملی را انجام میدهد؟
void function(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty
while (!isEmpty(&S))
cout<< pop(&S)); // pop an element from S and print it
}
7- فرض کنید که میخواهیم با استفاده از آرایه A که اندازه آن MAXSIZE است به طور همزمان دو پشته را پیاده سازی کنیم. دو پشته به صورت مخالف هم رشد خواهند کرد، یعنی پشته 1 از ابتدای آرایه به سمت انتها پر میشود و پسته دوم از انتهای پشته به سمت ابتدا پر میشود. دو متغیر top1 و top2 به عناصر بالای پشته 1 و پشته 2 اشاره میکنند. (top1 < top2) بهترین شرط برای پر بودن پشته ها کدام گزینه است؟
الف)(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
ب) top1 + top2 = MAXSIZE
ج) MAXSIZE
د) top1= top2 -1
8-
8- در شبه کد زیر S پشته و Q صف حلقوی است. تابع TOP(S) مقدار بالای پشته را برمیگرداند (بدون اینکه مقدار بالای پشته را حذف کند) و تابع HEAD(Q) مقدار ابتدای صف را برمیگرداند (بدون اینکه آن مقدار را حذف کند.) همچنین توابع Enqueue و Dequeue به ترتیب به عملیات درج و حذف از صف را انجام میدهد. به طور مشابه Push و Pop به ترتیب عملیات اضافه و حذف را از صف انجام میدهند.
ابتدا مشخص کنید با فرض اینکه در ابتدای انجام الگوریتم صف Q شامل مقادیری عدد و S یک پشته خالی است، این الگوریتم چه عملی انجام میدهد و مرتبه زمانی آن چقدر است؟
راهنمایی : بهتر است الگوریتم را با یک صف 4 تایی trace کنید