درس ساختمان داده - درس ششم صف و انواع آن

صف لیست خطی مرتبی از عناصر است که در آن عمل درج از یک طرف و عمل حذف از طرف دیگر انجام می شود.به ساختار صف fifo نیز گفته می شود. در صف از دو متغیر اشاره گر به نام front که به عنصر قبل از عنصر ابتدایی اشاره می کند و دیگری به نام rear که همیشه به اخرین عنصر اشاره می کند. کاربرد مهم صف در زمان بندی برنامه ها در سیستم عامل است.نمایش صف با دو ساختار لیست پیوندی و آرایه ای می باشد. ساده ترین راه نمایش صف استفاده از آرایه ی یک بعدی به طول n است. نکته:مشکل اصلی صف معمولی آن است که یک بار قابل استفاده است و هنگامی که rear به انتها می رسد نمی توان در صف چیزی را ذخیره کرد برای حل این مشکل از صف حلقوی استفاده می کنیم. صف حلقوی: آرایه انتخابی ۰ تا۱ Q[0 , …. , n-1] را می توان به صورت صف حلقوی در نظر گرفت به طوری که در این صف زمانی که rear برابر n-1 می شود عنصر بعدی در خانه شماره ۰ قرار می گیرد.