فرادرسساختمان داده صف در سوئیفت — به زبان ساده
شاید با خواندن عنوان این مقاله از خود بپرسید منظور از صف چیست؟ صف نوعی ساختمان داده در علوم رایانه است. در این نوشته به توضیح صف در سوئیفت می‌پردازیم. ابتدا برای درک بهتر این مفهوم به تصویر زیر توجه کنید:
همچنین شاید کنجکاو باشید که اصولاً چه نیازی به صف داریم؟ در اغلب الگوریتم‌ها نیاز داریم که آیتم‌هایی را به یک لیست اضافه کنیم و در ادامه آن‌ها را از همان لیست برداریم. اگر این روش اضافه کردن و برداشتن آیتم‌ها نیازمند یک رفتار خاص باشد می‌توانیم از صف استفاده کنیم.
یک کاربرد مهم صف به خصوص در iOS در Dispatch Queues است. این صف‌ها از یک API به نام GCD برای اجرای وظایف به ترتیب «ورودی اول، خروجی اول» (FIFO) استفاده می‌کنند. در نهایت GCD از همان قواعد کارکرد صف تبعیت می‌کند. برای درک بهتر به قیاس زیر توجه کنید.
قیاس
یک قیاس ساده بصری‌سازی صف مثالی از یک صف در دنیای واقعی است. افرادی را تصور کنید که برای دریافت آیتم مورد علاقه‌شان صف می‌بندند. نخستین کسی که وارد صف شود، نخستین کسی است که آن آیتم را دریافت خواهد کرد. هر کس که پس از او وارد صف شود، باید منتظر بماند تا فرد اول کار خود را تمام کند تا بتواند پاسخی بگیرد. این روند تا انتهای صف ادامه می‌یابد.
پیاده‌سازی
دو ساختمان داده وجود دارند که وقتی می‌خواهیم صف را پیاده‌سازی کنیم به ذهن می‌آیند. یکی «لیست پیوندی» (Linked List) و دیگری «آرایه دینامیک» (Dynamic Arrays) است. زمانی که یکی از این دو را انتخاب کردید، دیگر بر عهده شما است که کدام انتها را ابتدا یا انتهای صف در نظر بگیرید. ما در این مقاله از لیست پیوندی برای پیاده‌سازی صف استفاده می‌کنیم.
Enqueue
از آنجا که ما از لیست پیوندی برای ساخت صف در ساختمان داده استفاده کردیم، باید ابتدا آن را مقداردهی اولیه بکنیم.
کار خود را با افزودن متد Enqueue آغاز می‌کنیم. این همان تابعی است که آیتم‌ها را به لیست اضافه می‌کند. از آنجا که می‌خواهیم آن را به شکل فرم داشته باشیم، می‌توانیم آن را به سادگی به لیست اضافه کنیم. نکته مهمی که باید توجه کنیم این است که این تابع را به صورت «تغییرپذیر» (mutating) تعریف می‌کنیم ما می‌خواهیم در ادامه لیست پیوندی را با استفاده از متد Enqueue تغییر دهیم.
در این بخش تلاش می‌کنیم اتفاقی را که در برنامه و شیوه تأثیرپذیری هر عنصر در زمان اجرا رخ می‌دهد، به تصویر بکشیم. اگر فرض کنیم که چیزی را به انتهای لیست پیوندی اضافه کرده‌ایم، باید آن گره را در انتهای لیست ببینیم.
می‌توان تصور کرد که قرار دادن یک عنصر در لیست پیوندی دارای پیچیدگی زمانی O(1) است. این عملیات در زمان ثابت اجرا می‌شود، زیرا الحاق یک آیتم به ابتدای لیست پیوندی نیازمند تغییر دادن هیچ جیز دیگری نیست.
Dequeue
در این بخش روشی برای برداشتن آیتم اول از صف پیدا می‌کنیم. این کار با پیاده‌سازی تابع Dequeue صورت می‌گیرد. کار خود را با تعیین یک گزاره guard آغاز می‌کنیم تا هم مطمئن شویم که لیست خالی نیست و هم اولین عنصر آن را برداریم. سپس متد remove. را روی اولین عنصر فراخوانی می‌کنیم. مطمئن می‌شویم که عنصر انتخابی بازگشت یافته است تا صف از حالت تعادل خارج نشود.
اینک آیتم مورد نظر را از ابتدای لیست پیوندی برداشته و آن را حذف کرده‌ایم. زمان اجرای این عملیات نیز O(1) است و یک زمان ثابت محسوب می‌شود، زیرا آخرین گره در لیست پیوندی برداشته شده و نیازمند پیمایش همه لیست نیست.
Peek
اینک آموختیم که چگونه می‌توانیم آیتم‌ها را وارد صف کرده و از آن خارج کنیم، اما اگر بخواهیم صرفاً آیتم اول لیست را بازگشت دهیم چطور؟ به این منظور یک تابع خاص می‌نویسیم که تابع Peek نام دارد. این تابع ساده صرفاً مقدار اولی لیست را بازگشت می‌دهد و کاملاً گویا است.
زمان اجرای این تابع نیز برابر با O(1) است که زمان ثابتی محسوب می‌شود.
سخن پایانی
چنان که در این مقاله دیدیم صف یک ساختمان داده کاملاً ساده است که کاربردهای مختلفی دارد. چنان که احتمالاً متوجه شده‌اید، همه عملیات در این مقاله دارای زمان اجرای ثابت بودند. بنابراین استفاده از صف در این ساختار کاملاً کارآمد است. امیدواریم این مقاله مورد توجه شما قرار گرفته و بر دانش شما افزوده باشد. شایان توجه است که به علاقه‌مندان به آشنایی با ارتباط ساختمان داده و درس تحلیل و طراحی الگوریتم ها و درس الگوریتم های پیشرفته (درس نظریه الگوریتم پیشرفته)، مطالعه مطلب «درس الگوریتم های پیشرفته | مفاهیم پایه به زبان ساده» پیشنهاد می‌شود.
اگر این مطلب برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش نظریه صف (Queueing theory)
- مجموعه آموزشهای دروس علوم و مهندسی کامپیوتر
- آموزش سوئیفت (Swift) — مجموعه مقالات مجله فرادرس
- پشته (Stack)، صف (Queue) و تجزیه عبارت — ساختار داده و الگوریتم ها
==
