صف ها (FIFO)

در این بخش نحوه پیاده‌سازی ساختار داده‌های صف FIFO را با استفاده از انواع داده‌های داخلی و کلاس‌های کتابخانه استاندارد پایتون خواهید دید. اما ابتدا، بیایید دوباره مرور کنیم که صف چیست:
صف مجموعه ای از اشیاء است که از ورود سریع، اولین خروجی پشتیبانی می کند
(FIFO) معناشناسی برای درج و حذف. عملیات Insert و Delete را گاهی اوقات enqueue و dequeue می نامند. بر خلاف لیست ها یا
آرایه ها، صف ها معمولاً اجازه دسترسی تصادفی به اشیاء را نمی دهند
آنها حاوی.
در اینجا یک قیاس در دنیای واقعی برای صف اول ورود و خروج وجود دارد:
تصور کنید یک سری از Pythonistas منتظر دریافت نشان کنفرانس خود در روز اول ثبت نام PyCon هستند. جدید
اضافه شده به خط به پشت صف به عنوان ساخته شده است
افراد جدید وارد محل کنفرانس می شوند و به آن «صف می شوند».
نشان های خود را دریافت کنند. حذف (سرویس) در
جلوی صف، زمانی که توسعه دهندگان نشان های خود را دریافت می کنند و
کنفرانس کوله باری و ترک صف.
راه دیگری برای به خاطر سپردن ویژگی های ساختار داده صف
این است که آن را به عنوان یک لوله در نظر بگیریم:
آیتم های جدید (مولکول های آب، توپ های پینگ پنگ و …) قرار داده می شود
در یک انتها وارد شوید و به طرف دیگر سفر کنید، جایی که شما یا شخص دیگری دوباره آنها را حذف می کند. در حالی که اقلام در
صف (یک لوله فلزی جامد) که نمی توانید به آنها برسید. تنها
راه برای تعامل با آیتم های موجود در صف، افزودن موارد جدید است
آیتم ها در پشت (صف) یا برای حذف آیتم ها در
جلو (dequeue) لوله.
صف ها شبیه به پشته ها هستند و تفاوت بین آنها در این است
چگونه موارد حذف می شوند:
با یک صف، آیتمی که اخیراً اضافه شده را حذف می‌کنید (اول وارد، اولین خروج یا FIFO). اما با یک پشته، آیتم را اخیراً حذف می کنید
اضافه شده (آخرین ورود، اولین خروج یا LIFO).
از نظر عملکرد، انتظار می رود اجرای صف مناسب انجام شود
O(1) زمان برای عملیات درج و حذف. این دو مورد اصلی هستند
عملیات انجام شده در یک صف و در اجرای صحیح،
آنها باید سریع باشند
صف ها طیف وسیعی از کاربردها در الگوریتم ها دارند و اغلب کمک می کنند
حل مسائل زمان بندی و برنامه نویسی موازی. کوتاه و
الگوریتم زیبا با استفاده از صف، جستجوی وسعت اول (BFS) در یک است
ساختار داده درختی یا نموداری
الگوریتم های زمان بندی اغلب از صف های اولویت داخلی استفاده می کنند. اینها هستند
صف های تخصصی: به جای بازیابی عنصر بعدی با درج
زمان، یک صف اولویت، عنصر با بالاترین اولویت را بازیابی می کند. اولویت هر یک از عناصر توسط صف، بر اساس یا درنگ اعمال شده به کلیدهای آنها تعیین می شود. نگاهی دقیق تر به صف های اولویت خواهیم داشت
و نحوه پیاده سازی آنها در پایتون در فصل بعدی.
با این حال، یک صف معمولی، اقلامی را که حمل می کند دوباره سفارش نمی دهد. فقط
مانند مثال لوله، “شما آنچه را که در آن قرار داده اید دریافت خواهید کرد” و دقیقاً در آن
آن دستور
پایتون با چندین اجرای صف که هر کدام دارند ارسال می شود
ویژگی های کمی متفاوت آنها را مرور کنیم.