انواع ساختمان داده مقدماتی در تایپ اسکریپت – راهنمای جامع

ساختمان‌های داده جزء مباحث پیچیده‌ای هستند که هر برنامه‌نویسی در مسیر تبدیل شدن به یک توسعه‌دهنده نرم‌افزار در سطح بین‌المللی باید بر آن‌ها تسلط یابد. متاسفانه اغلب برنامه‌نویسان وب مهارت چندانی در این زمینه ندارند. در این راهنما با روش نوشتن سه ساختمان داده مقدماتی در تایپ اسکریپت آشنا خواهیم شد. این سه ساختمان داده شامل لیست‌های پیوندی، پشته و صف جزء مواردی هستند که هر کس یک دوره درسی علوم رایانه طی کرده باشد، با آن‌ها مواجه شده است.

تایپ اسکریپت به ما امکان می‌دهد که ساختمان‌های داده را به شکلی که عموماً در زبان‌های شیءگرا مانند ++C، جاوا و #C استفاده می‌شوند بسازیم. این شکل‌ها مشهور هستند، به خوبی مستند شده‌اند و در هر کتاب درسی یا وب سایت مربوط به ساختمان داده می‌توان آنها را یافت.

پیش‌نیازها

برای مطالعه این راهنما به یک کد ادیتور مانند ویژوال استودیو کد نیاز دارید. همچنین باید Node.js و Git را روی سیستم خود نصب کرده و با مبانی ابتدایی تایپ اسکریپت آشنا باشید.

راه‌اندازی

کد آغازین در این ریپوی گیت‌هاب (+) قرار دارد. کد کامل این راهنما را نیز می‌توانید در این ریپو (+) ببینید. یک پنجره ترمینال را باز کنید و دستورهای زیر را وارد نمایید تا کد آغازین را دریافت کرده و اجرا کنید:

git clone git@github.com:richarddprasad/ts-data-struct-starter.git
cd ts-data-struct-starter
npm install
npm start
(after a few seconds) Ctrl+C
npm start

npm اسکریپت‌های start:dev و build:dev را به صورت موازی اجرا می‌کند. این دو را می‌توانید در فایل package.json ببینید. نخستین باری که دستور npm start را اجرا کنید، کد هنوز به طور کامل بیلد نشده است و از کار خواهد افتاد. به همین جهت باید آن را kill کرده و ری‌استارت کنیم. خروجی ترمینال باید مانند زیر باشد:

می‌توانیم خطاهایی که از src/queue/queue_examples.ts می‌آیند را نادیده بگیریم. این خطاها زمانی که نخستین ساختمان داده خود را پیاده‌سازی کنیم رفع می‌شوند.

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

ساختمان‌های داده به طور کلی در مورد سازماندهی کلکسیون‌هایی از داده‌ها به روش خاصی هستند. این سازماندهی بر مبنای شیوه حذف و اضافه داده‌ها تعریف می‌شود. می‌توانی صدها نوع ساختمان داده مختلف را تعریف کرد، اما انواع خاصی از آن‌ها وجود دارند که بخشی اساسی از توسعه نرم افزار محسوب می‌شوند و این موارد شامل لیست‌های پیوندی، پشته‌ها، صف‌ها، صف‌های اولویت، جداول هش و درخت‌های دودویی هستند.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

لیست‌های پیوندی، پشته‌ها و صف‌ها جزء ضروری‌ترین موارد این ساختمان‌های داده‌ای هستند.

عملیات مقدماتی

ساختمان‌های داده بر حسب شیوه سازماندهی داده‌ها با هم تفاوت پیدا می‌کنند. ما با ارائه مجموعه‌ی از متدهای خاص، قواعدی برای این سیستم سازماندهی تعیین می‌کنیم.

1. یک متد insert برای درج یک آیتم در ساختمان داده.
2. یک متد remove برای حذف یک آیتم.
3. یک متد isEmpty برای تست این که آیا آیتمی وجود دارد یا نه.

این‌ها نام‌های ژنریک هستند. به طور معمول یک ساختمان داده خاص یک نام مخصوص برای یک عملیات معین دارد. برخی ساختمان‌های داده متدهای دیگری نیز دارند که مختص خودشان است.

صف

صف نخستین ساختمان داده‌ای است که در این راهنما پیاده‌سازی خواهیم کرد. صف به عنوان یک ساختمان داده «اولین ورودی-اولین خروجی» (FIFO) شناخته می‌شود و آن را می‌توان به صورت زیر نشان داد:

اصطلاح‌های صف

ابتدای صف به نام front و انتهای آن به نام rear شناخته می‌شود. نخستین عنصر (آیتم داده‌ای) که در صف درج شود، نخستین موردی است که حذف خواهد شد. آخرین عنصری که در صف درج شود، آخرین عنصری خواهد بود که از صف حذف می‌شود. همه عناصر بعدی که در صف درج شوند در rear قرار می‌گیرند.

عملیات صف

صف برخی عملیات ساده با نام‌های زیر را پیاده‌سازی می‌کند:

1. Enqueuer: یک عنصر در عقب (rear) صف درج می‌کند. این عنصر به rear جدید تبدیل می‌شود.
2. Dequeuer: یک عنصر در front صف درج می‌کند. عنصر بعدی به front جدید تبدیل می‌شود.
3. isEmpty: بررسی می‌کند آیا صف شامل هیچ عنصری است یا نه.

در تصویر زیر یک بصری‌سازی ساده از عملیات مرتبط با صف را می‌بینید:

عملیات dequeuer روی front صف تأثیر می‌گذارد در حالی که عملیات enqueuer روی rear صف اجرا می‌شود.

به عنوان یک نمونه از صف در دنیای واقعی می‌توان به صف نانوایی اشاره کرد. نخستین کسی که در صف قرار می‌گیرد، نخستین کسی است که نان می‌گیرد و آخرین کسی که وارد صف شود، آخرین نفری خواهد بود که نان می‌خرد. بدین ترتیب خرید نان از نانوایی به لطف وجود صف به فرایندی منظم و کارآمد تبدیل می‌شود.

سیستم‌های عامل از صف‌ها برای ردگیری هر کاراکتر که روی کیبورد تایپ می‌کنید استفاده می‌کنند. یک سرور شبکه می‌تواند درخواست‌های کلاینت را در یک صف ذخیره کند و به هر یک از آن‌ها به همان ترتیبی که وارد می‌شوند پاسخ دهد.

یک عملیات اضافی رایج دیگر صف peek نام دارد که البته می‌تواند نام‌های دیگری نیز داشته باشد.

4. peek: عنصری که در front صف قرار دارد را بدون این که حذف کند، بازیابی می‌کند.

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

5. isFull: بررسی می‌کند آیا صف به بیشینه تعداد آیتم‌هایی که می‌تواند نگه‌داری کند رسیده است یا نه.

همچنین می‌توانیم یک متد size نیز اضافه کنیم که تعداد عناصر هم اینک موجود در صف را بازیابی می‌کند. ما آن را برای صف خود پیاده‌سازی نمی‌کنیم، اما شما می‌توانید به عنوان یک تمرین این کار را انجام دهید. این کار به سادگی بازگشت دادن مقدار مشخصه length است.

پیاده‌سازی صف

پروژه را درون ویژوال استودیو کد باز کنید، سپس فایل src/queue/queue.ts را که شامل کد زیر است، باز کنید:

مشخصه queue در حال حاضر کامنت شده است. این مشکل را در ادامه رفع می‌کنیم، اما ابتدا باید کمی از مسیر منحرف شده و یک ویژگی تایپ اسکریپت به نام generics را بررسی کنیم.

بررسی مختصر ژنریک

صف ما به ذخیره‌سازی کلکسیونی از عناصر می‌پردازد. ما این عناصر را در یک آرایه (queue) ذخیره می‌کنیم. بیشترین تعداد عناصری که آرایه می‌تواند نگهداری کند را تعیین می‌کنیم و به ردگیری تعداد عناصری هم اینک در صف وجود دارد (length) می‌پردازیم.

آرایه‌های جاوا اسکریپت می‌توانند عناصری با انواع مخلوط را نگهداری کنند، اما تنها دلیل این امر آن است که آرایه‌های جاوا اسکریپت آرایه‌های معمولی نیستند، بلکه اشیای خاصی هستند که برای تقلید کارکرد یک آرایه طراحی شده‌اند. در واقع جاوا اسکریپت ابزاری برای ساخت آرایه با ماهیت متعارف ندارد. اگر علاقه‌مند هستید در این مورد اطلاعات بیشتری کسب کنید، پیشنهاد می‌کنیم این مطلب (+) را مطالعه کنید.

در زبان‌هایی که ساختمان داده آرایه واقعی وجود دارد، آرایه‌ها می‌توانند تنها عناصری از یک نوع منفرد را نگهداری کنند. ما این وضعیت را با تعیین یک نوع برای queue در جاوا اسکریپت ایجاد می‌کنیم. ما می‌توانیم انواع مختلفی مانند number یا string ایجاد کنیم. اما امکان تعیین مجموعه‌ای از انواع با استفاده از نوع union به صورت number | string | Boolean نیز وجود دارد. متاسفانه تعداد انواع بسیار زیادی است و از این رو استفاده از نوع union عملی نیست.

خوشبختانه تایپ اسکریپت این امکان را به ما داده است که از یک نوع متغیر استفاده کنیم که بعدتر مشخص می‌شود. این کار با استفاده از ژنریک انجام می‌یابد و به صورت زیر پیاده‌سازی می‌شود:

در کد فوق تعیین می‌کنیم که کلاس یک پارامتر ژنریک می‌پذیرد: <class Queue<T. استفاده از T به عنوان نام پارامتر یک سنت رایج است. اینک آرایه queue ما یک آرایه از نوع T است. درون سازنده یک آرایه queue مقداردهی می‌کنیم که یک آرایه جدید جاوا اسکریپت از نوع T خواهد بود:

بازگشت به صف

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

1. isEmpty

این عملیات در صورتی که length برابر با صفر باشد، مقدار true و در غیر این صورت مقدار false بازمی‌گرداند.

2. isFull

این عملیات در صورتی که length برابر با maxSize باشد، مقدار true و در غیر این صورت مقدار false بازمی‌گرداند.

3. Peek

این عملیات عنصر front را بدون حذف کردن بازگشت می‌دهد و در صورتی که صف خالی باشد یک استثنا ایجاد می‌کند:

4. enqueuer

در صورتی که فضا وجود داشته باشد، عنصری را در rear درج می‌کند. اگر تلاش کنید در یک صفِ پُر عنصری را درج کنیم، با خطای queue overflow مواجه خواهیم شد.

5. dequeuer

در این عملیات عنصر front حذف شده و بازگشت می‌یابد. این عملیات کمی چالش‌برانگیز است، زیرا باید همه عناصر درون صف را شیفت کنیم. اگر تلاش کنیم از یک صف خالی عنصری را حذف کنیم، موجب بروز خطای queue underflow خواهیم شد:

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

6. queueContents

این عملیات به طور رسمی بخشی از پیاده‌سازی صف است، اما می‌تواند برای مقاصد دیباگ نیز مفید باشد. این عملیات محتوای صف را پرینت می‌کند.

پیاده‌سازی کامل صف به صورت زیر است:

ایجاد صف

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

کد فوق یک صف ایجاد می‌کند که امکان نگهداری 100 عدد را دارد. همچنین می‌توانیم صفی از رشته‌ها بسازیم:

این کد صفی ایجاد می‌کند که 50 رشته را نگه می‌دارد. ما محدود به انواع داخلی جاوا اسکریپت نیستیم. در ادامه با شیوه ایجاد صفی از مشتریان آشنا می‌شوید:

در ادامه صفی از اعداد با بیشینه اندازه 100 می‌سازیم. این صف را تا انتها پر می‌کنیم تا دیگر نتوان عدد دیگری در آن درج کرد و سپس آن را تجزیه می‌کنیم:

این مثال‌ها در فایل پروژه src/queue/queue_examples.ts ارائه شده‌اند. می‌توانید کامنت خط زیر را در فایل index.ts بردارید تا کد اجرا شود:

اجرای تست‌ها

پیش از آن که به بخش بعدی برویم، باید اشاره کنیم که تست‌هایی نیز برای هر ساختمان داده ارائه شده است. اگر با تست unit آشنا باشید، می‌توانید مجموعه تست‌ها را اجرا کرده و تست‌های خود را نیز اضافه کنید. یک پنجره ثانویه ترمینال یا زبانه جدیدی را باز کنید و دستور زیر را برای اجرای مجموعه‌های تست وارد نمایید:

npx jest

پشته

پشته نیز مشابه صف است به جز این که عناصر مختلف به جای این که از دو انتهای مختلف ساختمان داده درج و حذف شوند، از مکان یکسانی اضافه و حذف می‌شوند. پشته یک ساختمان داده از نوع «آخرین ورودی-اولین خروجی» (LIFO) است.

پشته می‌تواند نقش مهمی در کارکرد داخلی سیستم‌های عامل و موتورهای جاوا اسکریپت ایفا کند. برای نمونه پشته برای ردگیری فراخوانی‌های تابع مورد استفاده قرار می‌گیرد.

تابع‌های بازگشتی که به یک حالت مبنا resolve نمی‌شوند، می‌توانند موجب بزرگ‌تر شدن پشته شوند تا این که به محدودیت اندازه‌اش برسد و موجب بروز خطای از کار افتادن پشته به صورت «سرریز پشته» (stack overflow) شود.

اصطلاح‌ها و عملیات پشته

آن انتهایی که عناصر را در پشته درج و حذف می‌کنیم، به نام top پشته نامیده می‌شود. پشته عملیات ابتدایی با نام‌های زیر را پیاده‌سازی می‌کند:

1. push برای درج.
2. pop برای حذف.
3. top برای بازیابی عنصر top بدون حذف کردن آن.

پشته نیز در صورتی که مبتنی بر آرایه باشد، یک متد isEmpty و همچنین یک متد isFull دارد. پشته را می‌توان به صورت زیر بصری‌سازی کرد:

پیاده‌سازی پشته

فایل src/stack/stack.ts را باز کنید. چارچوب کد زیر را مشاهده می‌کنید:

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

1. push

یک عنصر به ابتدای پشته اضافه می‌کند.

اگر تلاش کنیم به یک پشته که پر است، push کنیم، یک خطای stack overflow دریافت می‌کنیم. به شیوه استفاده از عملگر post-increment روی مشخصه length توجه کنید.

2. pop

این عملیات عنصری را از ابتدای پشته حذف می‌کند.

اگر از پشته خالی pop کنیم، یک خطای stack underflow دریافت می‌کنیم. به شیوه استفاده از عملگر pre-decrement روی مشخصه length توجه کنید.

3. top

عنصر ابتدای پشته را بدون حذف کردن آن بازیابی می‌کند.

به این که ابتدای پشته در length منهای یک است توجه کنید.

یک مثال مختصر از پشته

فایل src/test/stack.test.ts را باز کنید. در نزدیکی انتهای پشته، کد موجود برای معکوس کردن رشته با استفاده از پشته را مشاهده می‌کنید:

لیست‌های پیوندی

یک آرایه سنتی غیر جاوا اسکریپتی دارای اندازه ثابت است و نمی‌تواند بزرگ‌تر یا کوچک‌تر شود. تنها روش برای تغییر اندازه یک آرایه، ایجاد یک آرایه جدید با اندازه مطلوب و کپی کردن محتوای آرایه قدیمی به آرایه جدید است. برای درک دلیل این وضعیت باید با شیوه تخصیص حافظه آشنا باشیم که فراتر از حوصله این مقاله است.

لیست‌های پیوندی جایگزینی برای آرایه‌ها هستند و مزیت اصلی آن‌ها نسبت به آرایه‌ها این است که می‌توانند به سادگی بزرگ‌تر یا کوچک‌تر شوند. تنها عیب آن این است که لیست‌های پیوندی از نظر دسترسی به داده‌ها کندتر از آرایه‌ها هستند. موقعیت هر عنصر مفروض در یک آرایه را می‌توان به سادگی به صورت زیر محاسبه کرد:

عناصر در یک لیست پیوندی به صورت یک بلوک مجاور در حافظه قرار دارند، اما در سراسر آن توزیع یافته‌اند. در ادامه چگونگی این وضعیت را بررسی می‌کنیم، اما نکته اصلی که باید به خاطر داشته باشید این است که موقعیت یک عنصر در لیست پیوندی را نمی‌توانیم محاسبه کنیم. بنابراین باید کل لیست را پیمایش کنیم تا این که به دنبال عنصری که مد نظرمان است بگردیم و در بدترین حالت ممکن است عنصری که به دنبالش هستیم در انتهای لیست پیوندی قرار داشته باشد.

پوشش داده

پیش از آن که یک لیست پیوندی را پیاده‌سازی کنیم، باید یک کلاس برای پوشش داده‌ها ایجاد کنیم. این کلاس به طور معمول به نام Node شناخته می‌شود و علاوه بر نگهداری داده‌ها شامل ارجاعی به Node دیگر نیز است. فایل src/linked_list/node.ts را باز کرده و محتوای آن را بررسی کنید:

در ادامه به توضیح کد فوق می‌پردازیم:

1. کلاس Node را درون یک فضای نام به نام DS قرار می‌دهیم. یک شیء Node از قبل در دامنه سراسری قرار دارد، از این رو باید Node خود را در یک فضای نام مجزا قرار دهیم تا تداخلی ایجاد نشود.
2. کلاس Node ما یک پارامتر ژنریک از نوع T می‌پذیرد.
3. مشخصه item داده‌های ما را نگهداری می‌کند. درصورتی که هیچ آرگومانی ارائه نشده باشد، سازنده یک مقدار پیش فرض null ارائه می‌کند. این کار صرفاً به منظور سهولت کار است.
4. مشخصه next یک Node را به دیگری لینک می‌کند.
5. هر دو مشخصه‌های item و next به صورت public هستند. به طور معمول مشخصه‌های درون یک کلاس به صورت private یا protected هستند و getters و setters امکان دسترسی به این مشخصه‌ها را فراهم می‌سازند. در این بخش یک استثنا ایجاد می‌کنیم. یک لیست پیوندی می‌تواند میلیون‌ها گره داشته باشد و سربار استفاده از getters و setters بسیار زیاد خواهد بود. بهتر است به این مشخصه‌ها مستقیماً دسترسی پیدا کنیم تا شاهد بهبود عملکرد باشیم.
6. item و next می‌توانند null نیز باشند. می‌توانیم از undefined نیز به جای null استفاده کنیم. در ادامه دلیل این که در زمان پیاده‌سازی لیست پیوندی به مقادیر null یا undefined نیز اجازه وجود می‌دهیم را توضیح خواهیم داد.

اصطلاح‌ها و عملیات لیست پیوندی

لیست پیوندی را می‌توان به روش‌های مختلفی پیاده‌سازی کرد. برای نمونه می‌توان آن را به روش تک پیوندی که ما عمل می‌کنیم پیاده‌سازی کرد. همچنین می‌توان آن را به صورت دو پیوندی پیاده‌سازی کرد که معنی آن این است علاوه بر اشاره‌گر next یک اشاره‌گر prev نیز خواهیم داشت.

ما از نسخه‌ای می‌خواهیم استفاده کنیم که از گره‌های مرده یا قراول (sentinel) برای نشان دادن ابتدا و انتهای لیست استفاده می‌کند. گره‌های قراول به ما امکان می‌دهند که کد کمتری برای مدیریت درج و حذف عناصر از لیست بنویسیم.

ابتدای لیست به نام سر (head) و انتهای آن به نام دم (tail) خوانده می‌شود. یک لیست پیوندی خالی شامل دو گره قراول به نام‌های سر و دم است که گره سر به گره دم لیست اشاره می‌کند.

لیست پیوندی عملیات insert و remove را پیاده‌سازی می‌کند، اما چندین گزینه برای این دو عملیات می‌توان پیاده‌سازی کرد. می‌توان بیش از یک پیاده‌سازی برای هر یک ارائه کرد و ما نیز چنین خواهیم کرد.

لیست پیوندی ما شامل متدهای زیر خواهد بود:

1. insertFirst – عنصری را در ابتدای لیست درج می‌کند.
2. insertLast – عنصری را در انتهای لیست درج می‌کند.
3. removeFirst – عنصری را از ابتدای لیست حذف می‌کند.
4. Remove – عنصری را با کلید مفروض حذف می‌کند.
5. Contains – بررسی می‌کند آیا عنصری با کلید مفروض در لیست موجود است یا نه.
6. isEmpty – بررسی می‌کند آیا لیست شامل هیچ گرهی به جز سر و دم است یا نه.
7. getFirst – نخستین عنصر لیست را بدون حذف کردن آن بازیابی می‌کند.

پیاده‌سازی‌های لیست پیوندی بر حسب عملیات مقدماتی که ارائه می‌کند و همچنین نام این عملیات می‌تواند متفاوت باشد. برای نمونه remove گاهی اوقات به نام delete نامیده می‌شود. دلیل این که برخی از این متدهای خاص را انتخاب کرده‌ایم در ادامه روشن‌تر خواهد شد.

پیاده‌سازی لیست پیوندی

فایل src/linked_list/linked_list.ts را باز کنید. به چارچوب کد ارائه شده نگاه کنید. یک متد به نام listContents برای کمک به دیباگ کردن ارائه شده است.

لیست پیوندی ما تنها شامل دو مشخصه است که گره‌های قراول head و tail هستند. سازنده روابط زیر را تنظیم می‌کند:

گره‌های قراول ما هرگز هیچ داده‌ای را نگهداری نمی‌کنند، به همین جهت است که به مشخصه item اجازه داده‌ایم که null باشد.

گره دم (tail) به گره دیگری اشاره نمی‌کند، از این رو اجازه می‌دهیم که مشخصه next نیز null باشد. می‌توانیم کاری کنیم که گره دم به گره سر اشاره کند و به این ترتیب یک لیست مدور ایجاد کنیم. در ادامه عملیات دیگر را پیاده‌سازی می‌کنیم.

1. isEmpty

درصورتی که head.next به tail اشاره کند مقدار true بازگشت می‌دهد:

2. insertFirst

یک گره جدید به ابتدای لیست اضافه می‌کند:

رسم نمودار حالت لیست پیوندی موجب می‌شود که با سادگی بیشتری کارهایی که باید انجام دهیم را مشاهده کنیم:

3. getFirst

نخستین عنصر را بدون حذف کردن آن بازیابی می‌کند:

در یک لیست غیر تهی، this.head.next هرگز نمی‌تواند null باشد. با این حال تایپ اسکریپت این را نمی‌داند و از این رو باید برخی منطق شرطی در گزاره بازگشتی خود وارد کنیم. آخرین متدی که پیاده‌سازی می‌کنیم remove است. راه حل‌های متدهای دیگر نیز ارائه شده‌اند.

4. Remove

یک گره را در کلید مفروض حذف می‌کند:

برای حذف یک گره خاص باید از یک گره ثالث cur کمک بگیریم.

کد کامل لیست پیوندی با راه‌حل‌های متدهای باقیمانده به صورت زیر است:

به عنوان تمرین می‌توانید تلاش کنید راه‌حل‌های خود را پیاده‌سازی کنید.

صف و پشته مبتنی بر لیست

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

صف مبتنی بر لیست

پشته مبتنی بر صف

در کدهای فوق دیدیم که دیگر به متد isFull برای هیچ کدام از ساختمان‌های داده نیاز نداریم. پشته‌ها و صف‌های مبتنی بر لیست می‌توانند تا اندازه نامحدودی افزایش یابند. صف ما دیگر محبور به جابجا کردن همه عناصر پس از عملیات dequeuer نیست، اما در یک عملیات enqueuer باید همه لیست را تا انتها پیمایش کنیم تا یک عنصر حدید را درج کنیم. ما می‌توانستیم پشته و صف خود را با استفاده از شیء Array داخلی جاوا اسکریپت نیز پیاده‌سازی کنیم.

لیست پیوندی ما یک بازسازی جزئی از شیء Array داخلی جاوا اسکریپت محسوب می‌شود. البته این بدان معنی نیست که آرایه‌های جاوا اسکریپت در عمل با استفاده از لیست پیوندی پیاده‌سازی شده‌اند. پیاده‌سازی زیرین ممکن است بسته به هر موتور متفاوت باشد.

سخن پایانی

امیدواریم این راهنما برای شما مفید و اگاهی بخش بوده باشد. اگر می‌خواهید در مورد ساختمان‌های داده اطلاعات بیشتری کسب کنید، پیشنهاد می‌کنیم مطالبی که در ادامه آمده است را نیز مطالعه کنید:

• مجموعه آموزش‌های برنامه‌‌نویسی
• مجموعه آموزش ساختمان داده و طراحی الگوریتم
• مجموعه آموزش‌های JavaScript (جاوا اسکریپت)
• انواع پیشرفته در TypeScript — با مثال های کاربردی
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

==