صف

نوع ديگري از ساختمان داده‌ها، صف (Queue) است. صف شبيه به يك صف انتظار (نوبت) در يك فروشگاه است، كه در آن ابتدا به اولين شخص در سر صف، سرويس داده مي‌شود و مشترهاي بعدي بايد در انتظار رسيدن نوبت خود باقي بمانند. در صف گره‌ها از ابتدا يا سر صف (head) حذف مي‌شوند و اضافه كردن گره به صف از انتهاي (tail) آن صورت مي‌گيرد، به همين دليل به ساختمان داده صف، اولين ورودي–اولين خروجي (FIFO) گفته مي‌شود. به عمل افزودن گره به صف enqueue و حذف گره از صف dequeue گفته مي‌شود.

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

در شبكه‌هاي كامپيوتري بسته‌هاي اطلاعاتي در صف‌هاي انتظار قرار مي‌گيرند و در هر زمان يك بسته به عنوان گره به شبكه ارسال مي‌شود و اگر نياز باشد تا رسيدن به مقصد اين بسته جابجا مي‌شود.