ساختمان داده صف Queue

ساختمان داده صف Queue

در فرهنگ لغت، صف به معنای "خط انتظار" است، مثل صفی که مردم برای گرفتن نان در گرفتن نان در جلوی نانوایی تشکیل میدهند.

در ساختمان داده، صف مجموعه ای از عناصر مرتب است که هر عنصر از یک طرف بنام جلوی صف از آن حذف میشود و از طرف دیگر به نام انتهای صف در صف قرار میگیرد. به همین دلیل آن را ساختمان داده FIFO (خروج به ترتیب ورود) می نامند.

 

عملیات های صف :

چون صف مجموعه ای از عناصر است که عناصر از یک طرف به نام آخر صف به آن اضافه و از طرف جلوی صف از آن حذف میشوند، میتوان عملیات هایی بر اساس این تعریف برای صف در نظر گرفت. عملیات های صف عبارتنداز:

• Enqueue : عنصری را به انتهای صف اضافه میکند.
• Dequeue : عنصر جلوی صف را حذف میکند.
• Peek : عنصر جلوی صف را بازیابی میکند ولی حذف نمیکند.
• QueueEmpty : خالی بودن صف را بررسی میکند.
• Clear  : تمام عناصر صف را حذف میکند.
• Contains : مشخص میکند که عنصر خاصی در صف وجود دارد یا خیر.
• CopyTo : محتویات صف را درآرایه ای از نوع Object کپی میکند.
• ToArray : محتویات صف را در آرایه ای از نوع معین کپی میکند.

 

کلاس Queue :

در C# کلاسی بنام Queue  در فضای نام Collections وجود دارد که ساختمان داده ی صف را با توجه به ویژگی هایی که مطرح شد پیاده سازی میکند. یعنی این کلاس تمام عملیات و متدهایی که برای صف تعریف کردیم به همراه فعالیتهای دیگری، فراهم میسازد. این کلاس برای ذخیره عناصر صف از یک ArrayList استفاده میکند. چون اندازه ArrayList بطور پویا در زمان اجرا تغییر میکند، برای پیاده سازی ساختمان داده پویایی مثل Queue مفید است. همتای کلی آن در فضای نام Collections.Generic قرار دارد.

 

متدهای سازنده کلاس Queue :

برای استفاده از کلاس Queue باید اشیایی از آن را ایجاد و از آنها استفاده کرد. به چند روش میتوان اشیایی از کلاس Queue را ایجاد کرد.

• سازنده پیش فرض، صفی بنام myQueue ایجاد میکند که اندازه اولیه آن 32 عنصر است. وقتی صف پر شد، ظرفیت آن با ضریب دو افزایش می یابد. سازنده ی پیش فرض بصورت زیر فراخوانی میشود:

Queue  myQueue =  new  Queue ();

• در روش دوم برای ایجاد شیء صف اندازه اولیه آن را تعیین کرده ضریب افزایش طول صف را نیز مشخص میکنیم. در مثال زیر صفی با اندازه 32 عنصر ایجاد میشود. هر وقت صف پر شد، اندازه آن سه برابر میشود:

  Queue  myQueue =  new  Queue (32, 3);

 

• در روش سوم میتوان صف را با استفاده از اشیایی از کلکسیون دیگر ایجاد کرد. مثلا اگر اشیایی از یک آرایه داشته باشید میتوانید با استفاده از این آرایه بسازید.

 

خاصیت Count در کلاس Queue تعداد عناصر موجود در صف را تعیین میکند. در صف خالی مقدار آن صفر است. از این خاصیت برای تشخیص خالی بودن صف استفاده میکنند و در نتیجه در بعضی از پیاده سازی های صف ، متد Queue Empty را پیاده سازی نمیکنند.

 

متدهای کلاس  Queue :

در این بخش بعضی از متدهای کلاس Queue را که عملیات های صف را پیاده سازی میکنند، بررسی میکنیم:

• EnQueue : این متد، عنصری را به انتهای صف اضافه میکند و بصورت زیر بکار میرود :

EnQueue (  item);

• DeQueue : این متد عنصر جلوی صف را حذف میکند و آن عنصر را در متغیر item قرار میدهد.

item = Dequeue();

 

• Peek : این متد، عنصر جلوی صف را برمیگرداند ولی آنرا حذف نمیکند.

item = Peek;

این عملیات معادل یک عمل EnQueue  و سپس یک عمل DeQueue  برای همان عنصر است.

 

• Clear  : این متد، کلیه عناصر صف را حذف میکند و خاصیت Count را برابر صفر قرار میدهد. یک کاربرد خوب این متد وقتی است که خطایی در پردازش صف وجود داشته باشد و بخواهیم تمام عناصر آنرا حذف کنیم:

 Clear();

 

• Contains : مشخص میکند که آیا عنصرخاصی در صف وجود دارد یا خیر. اگر وجود داشته باشد، مقدار true وگرنه   false برمیگرداند. از این متد برای جست وجوی عنصری در صف استفاده میکنیم که در جلوی صف نیست.

Contains ( item);

 

• CopyTo : این متد محتویات صف را درآرایه ای از نوع Object کپی میکند. این متد بصورت زیر بکار برده میشود:

CopyTo (array ,  index);

  array  آرایه ای است که محتویات صف باید در آن کپی شوند و index مشخص میکند محتویات صف با شروع از چه اندیسی در آرایه array کپی شوند، عناصر صف به ترتیب FIFO در آرایه کپی میشوند.

 

• ToArray : این متد نیز محتوای صف را در آرایه کپی میکند با این تفاوت که نیاز به مشخص کردن اندیس شروع کپی در آرایه مقصد نیست زیرا از اندیس صفر شروع به کپی میکند و باید آنرا در دستور انتساب بکار برد.