با توجه به موارد خلاصه شده بالا، موقعی از لیست اضافه میکنیم که عملیات درج و حذف زیادی نداریم و بیشتر برای افزودن مقدار به انتها و دسترسی به المانها بر اساس اندیس باشد.
یک کلاس از پیش آماده در دات نت که لیستهای پیوندی دو طرفه را پیاده سازی میکند. هر المان یا گره یک متغیر جهت ذخیره مقدار دارد و یک اشاره گر به گره قبل و بعد.
- افزودن به انتهای لیست به خاطر این که همیشه گره آخر در tail وجود دارد بسیار سریع است.
- عملیات درج insert در هر موقعیتی که باشد اگر یک اشاره گر به آن محل باشد یک عملیات سریع است یا اینکه درج در ابتدا یاانتهای لیست باشد.
- جست و جوی یک مقدار چه بر اساس اندیس باشد و چه مقدار، کار جست و جو کند خواهد بود. چرا که باید تمامی المانها از اول به آخر اسکن بشن.
- عملیات حذف هم به خاطر اینکه یک عمل جست و جو در ابتدای خود دارد، یک عمل کند است.
استفاده از این کلاس موقعی خوب است که عملیاتهای درج و حذف ما در یکی از دو طرف لیست باشد یا اشارهگری به گره مورد نظر وجود داشته باشد. از لحاظ مصرف حافظه به خاطر داشتن فیلدهای اشارهگر به جز مقدار، زیادتر از نوع List میباشد. در صورتی که دسترسی سریع به دادهها برایتان مهم باشد استفاده از List باز هم به صرفهتر است.
پشته Stack
یک سری مکعب را تصور کنید که روی هم قرار گرفته اند و برای اینکه به یکی از مکعبهای پایینی بخواهید دسترسی داشته باشید باید تعدادی از مکعبها را از بالا بردارید تا به آن برسید. یعنی بر خلاف موقعی که آنها روی هم میگذاشتید و آخرین مکعب روی همه قرار گرفته است. حالا همان مکعبها به صورت مخالف و معکوس باید برداشته شوند.
یک مثال واقعیتر و ملموستر، یک کمد لباس را تصور کنید که مجبورید برای آن که به لباس خاصی برسید، باید آخرین لباسهایی را که در داخل کمد قرار دادهاید را اول از همه از کمد در بیاورید تا به آن لباس برسید.
در واقع پشته چنین ساختاری را پیاده میکند که اولین عنصری که از پشته بیرون میآید، آخرین عنصری است که از آن درج شده است و به آن LIFO گویند که مخفف عبارت Last Input First Output آخرین ورودی اولین خروجی است. این ساختار از قدیمیترین ساختارهای موجود است. حتی این ساختار در سیستمهای داخل دات نت CLR هم به عنوان نگهدارنده متغیرها و پارامتر متدها استفاده میشود که به آن
Program Execution Stack میگویند.
پشته سه عملیات اصلی را پیاده سازی میکند: Push جهت قرار دادن مقدار جدید در پشته، POP جهت بیرون کشیدن مقداری که آخرین بار در پشته اضافه شده و Peek جهت برگرداندن آخرین مقدار اضافه شده به پشته ولی آن مقدار از پشته حذف نمیشود.
این ساختار میتواند پیاده سازیهای متفاوتی را داشته باشد ولی دو نوع اصلی که ما بررسی میکنیم، ایستا و پویا بودن آن است. ایستا بر اساس آرایه است و پویا بر اساس لیستهای پیوندی. شکل زیر پشتهای را به صورت استفاده از پیادهسازی ایستا با آرایهها نشان میدهد و کلمه Top به بالای پشته یعنی آخرین عنصر اضافه شده اشاره میکند.
استفاده از لیست پیوندی برای پیاده سازی پشته:
لیست پیوندی لازم نیست دو طرفه باشد و یک طرف برای کار با پشته مناسب است و دیگر لازم نیست که به انتهای لیست پیوندی عمل درج انجام شود؛ بلکه مقدار جدید به ابتدای آن اضافه شده و برای حذف گره هم اولین گره باید حذف شود و گره دوم به عنوان head شناخته میشود. همچنین لیست پیوندی نیازی به افزایش ظرفیت مانند آرایهها ندارد.
ساختار پشته در دات نت توسط کلاس Stack از قبل آماده است:
Stack<string> stack = new Stack<string>();
stack.Push("A");
stack.Push("B");
stack.Push("C");
while (stack.Count > 0)
{
string letter= stack.Pop();
Console.WriteLine(letter);
}
//خروجی
//C
//B
//A
صف Queue
ساختار صف هم از قدیمیترین ساختارهاست و مثال آن در همه جا و در همه اطراف ما دیده میشود؛ مثل صف نانوایی، صف چاپ پرینتر، دسترسی به منابع مشترک توسط سیستمها. در این ساختار ما عنصر جدید را به انتهای صف اضافه میکنیم و برای دریافت مقدار، عنصر را از ابتدا حذف میکنیم. به این ساختار FIFO مخفف First Input First Output به معنی اولین ورودی و اولین خروجی هم میگویند.
ساختار ایستا که توسط آرایهها پیاده سازی شده است:
ابتدای آرایه مکانی است که عنصر از آنجا برداشته میشود و Head به آن اشاره میکند و tail هم به انتهای آرایه که جهت درج عنصر جدید مفید است. با برداشتن هر خانهای که head به آن اشاره میکند، head یک خانه به سمت جلو حرکت میکند و زمانی که Head از tail بیشتر شود، یعنی اینکه دیگر عنصری یا المانی در صف وجود ندارد و head و Tail به ابتدای صف حرکت میکنند. در این حالت موقعی که المان جدیدی قصد اضافه شدن داشته باشد، افزودن، مجددا از اول صف آغاز میشود و به این صفها، صف حلقوی میگویند.
عملیات اصلی صف دو مورد هستند enqueue که المان جدید را در انتهای صف قرار میدهد و dequeue اولین المان صف را بیرون میکشد.
پیاده سازی صف به صورت پویا با لیستهای پیوندی
برای پیاده سازی صف، لیستهای پیوندی یک طرفه کافی هستند:
در این حالت عنصر جدید مثل سابق به انتهای لیست اضافه میشود و برای حذف هم که از اول لیست کمک میگیریم و با حذف عنصر اول، متغیر Head به عنصر یا المان دوم اشاره خواهد کرد.
کلاس از پیش آمده صف در دات نت <Queue<T است و نحوهی استفاده آن بدین شکل است:
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Message One");
queue.Enqueue("Message Two");
queue.Enqueue("Message Three");
queue.Enqueue("Message Four");
while (queue.Count > 0)
{
string msg = queue.Dequeue();
Console.WriteLine(msg);
}
}
//خروجی
//Message One
//Message Two
//Message Thre
//Message Four