صف (queue) : یک ساختمان داده ای است که عمل حذف از ابتدا و اضافه یا درج به انتهای ان انجام میشود . یعنی در یک صف موقعی که میخوایم یه عنصر حذف کنیم میایم اولین عنصری که وارد صف شده را حذف میکنیم.
صف از سیاست FIFO(first in first out) پیروی میکنه یعنی در واقع اولین عنصری که وارد میشه اولین عنصری میشه که حذف و خارج میشه.
توی صف ۲ تا تعریف داریم :
front : مشخص کننده نفر اوله (ابتدای صف)
rear : مشخص کننده نفر اخره (اشاره کننده به اخر صف )
Enqueue: (O(1))اضافه کردن به صف پیچیدگی زمانی
Dequeue : (O(1))حذف کردن از صف پیچیدگی زمانی
خب حالا میخوایم با پایتون با روش های زیر صف رو پیاده سازی کنیم :
با استفاده از لیست ها میتونیم یه صف پیاده سازی کنیم به این صورت که عمل Enqueue با استفاده از append و عمل Dequeue با استفاده از pop انجام میشه و خب لیست خیلی برای این کار کند هستند چون برای عمل حذف و اضافه از ابتدا نیازه که خمه عنصر ها یکی یکی شیفت پیدا کنند اون ور که یه زمان O(n) نیازه براش ولی کلا روش لیست برای کار با تعداد ایتم کم خوبه .
صف را می توانیم با استفاده از کلاس deque از ماژول Collections پیاده سازی کنیم . عمل Enqueue با استفاده از append و عمل Dequeue با استفاده از popleft انجام میشه . در مواردی که نیاز به عملیات سریعتر حذف و اضافه و پاپ از دو طرف ظر داریم ، Deque بهتر از لیسته ، زیرا deque پیچیدگی زمانی O (1) را برای عملیات درج و حذف فراهم می کند. (چون deques حذف و اضافه عناصر از هر دو طرف پشتیبانی می کند ، می تواند هم به عنوان صف و هم به عنوان پشته عمل کند.)
اینجا Queue ماژول داخلی پایتون است که برای پیاده سازی صف استفاده می شود.این صف از قانون FIFO پیروی می کند. عمل Enqueue با استفاده از put و عمل Dequeue با استفاده از get انجام میشه.
همانطور که مشاهده می کنید در خط اخر براش همیشه منتظر میمونه تا عنصری در دسترس شه میتونیم به جاش ازget_nowait استفاده کنیم که در صورت خالی بودن پشته به ما error میده.
امیدوارم دوست داشته باشید برای توضیحات بیشتر به این سایت و این سایت میتونین برین .
