پشته چندگانه:
اگر فقط نیاز به دو پشته در برنامه داشته باشیم راه حل ساده است. برای این منظور از یک آرایه n خانه ای استفاده می کنیم. s[1] ابتدای پشته اول و s[n] ابتدای پشته دوم را نشان می دهد و پشته ها به سمت همدیگر می توانند رشد کنند. بدین ترتیب از حافظه موجد به صورت بهینه استفاده می شود.
ولی اگر بخواهیم بیش از دو پشته داشته باشیم، روش فوق قابل استفاده نیست. در این حال برای نمایش n پشته حافظه s[1..n] را به n قسمت تقسیم می کنیم. تقسیم بندی آرایه ها متناسب با نیازها باشد. در این حالت مقادیر به صورت زیر خواهد بود:
b[i]=t[i]=[m/n](i-1)+1
که در آن n تعداد پشته ها و m حد بالای آرایه است.
مثال: اگر در آرایه s[1..495] بخواهیم 4 پشته به وجود آوریمآدرس ابتدای هرپشته را بدست آورید. اندازه پشته ها یکسان است.
پاسخ:
m=495 , m=4
b[1]=1
b[2] [495/4](2-1)+1=124
b[3]= [495/4](3-1)+1=247
b[4]=[495/4](4-1)+1=370
در حالت پشته های چندگانه (n>2) ممکن است یکی از پشته ها سریع تر از بقیه پر شود و به همین دلیل استفاده از حافظه بهینه نخواهد بود. برای رفع این مشکل باید عناصر شیفت داده شوند تا در انتهای پشته پشته پر شده فضای خالی تولید شود و این عمل در بدترین حالت o(m) خواهد بود. در پشته های چند گانه (n=2) استفاده از حافظه بهینه است و زمان پردازش نیز از مرتبه o(1) است.
از همه کسانی که این مطلب رو خوندند می پرسم چرا این مرتبه o(1) است؟ لطفاً جواب رو مکتوب تو سایت قرار بدید!!!!!!!!!
زیر برنامه های اضافه و حذف از پشته های چند گانه و صف ها رو در پست بعدی قرار می دهم. فعلاً خداحافظ!
پاسخ با نقل قول
