الـ Queues في لغة C

السلام عليكم و رحمة الله و بركاته

كنا قد تحدثنا في الجزء الأول من هذه السلسلة عن القوائم المتصلة البسيطة و تحدثنا في الجزء الثاني عن القوائم المزدوجة و انتقلنا بعد ذلك إلى الجزء الثالث لنشرح المكدسات و يسرني أن أبدأ معكم في شرح الجزء الرابع الذي يتعلق بالطوابير (Queues).

الفهرس

• تعريف
• المحاكاة باستخدام المصفوفات
• المحاكاة باستخدام القوائم البسيطة
• المحاكاة باستخدام القوائم المزدوجة
• اختبر قدراتك

تعريف

الطابور أو الــ Queue مُشابه جدا للمكدس (Stack) فقط الفرق الوحيد بينهما يكمن في أن الإضافة في الطابور تكون في النهاية بينما تكون في البداية عند الحديث عن المكدس, في بقية العمليات (الحذف و الإظهار) لا يوجد فرق يُذكر. أقرب مثال على الطابور هو قوائم الانتظار أو الــ Waiting List حيث نجد أن أول من يدخل هو أول من يخرج و آخر من يدخل هو آخر من يخرج و هذا النوع من الترتيب يُعرف اختصاراً بــ FIFO أي First In First Out. كما هو الحال مع المكدس, الطابور لا يملك نوع بيانات خاص به و إنما هو مجرد تركيبة يُمكن محاكاتها باستخدام المصفوفات أو القوائم (سواء كانت بسيطة أو مزدوجة) أو حتى الأشجار (Trees).

تنويه:

في بقية المقالة :

1. سأقوم بتقسيم الكود الكامل إلى مجموعة دوال للتوضيح.
2. كل جزء من الكود سيكون مُرتبطاً بالجزء السابق له.
3. الأخطاء التي شرحناها سابقا (مثل فشل عملية الحجز) لن نتعرض لها هذه المرة من أجل الاختصار.

المحاكاة باستخدام المصفوفات

لمحاكاة الطابور بالمصفوفات سنحتاج إلى 3 متغيرات: الأول عبارة عن المصفوفة التي ستُحاكي الطابور و المتغير الثاني يحمل رقم أول خانة من الطابور و المتغير الثالث يحمل رقم آخر خانة, هكذا:

بالنسبة لتهيئة المتغيرات, قمنا بحجز 20 خانة للمصفوفة Queue ثم أسندنا القيمة -1 لكل من front و rear كدلالة على فراغ الطابور.

نأتي الآن إلى دالة الإدراج :

إذا تساوت قيمة rear مع SIZE-1 فهذا يعني أننا وصلنا إلى آخر خانة و بالتالي لا يمكننا إضافة المزيد من العناصر لذا قمنا بإظهار الرسالة OverFlow كدلالة على حدوث فيض عند محاولة الإدراج.

في الحالة المعاكسة, سنقوم بالانتقال إلى الخانة الموالية ثم نقرأ العدد المُدخل و نخزنه في الخانة الحالية.

بالنسبة لدالة الحذف فهي كالتالي :

إذا تساوت قيمة rear مع front فهذا يعني أنه لا يوجد عنصر للسحب, هذا من جهة.

من جهة أخرى, يتساوى  rear مع front عند -1 فقط و من المعروف أن -1 لا يمكن أن تكون index لأحد عناصر المصفوفة لأن الترقيم يبدأ من 0 لذا قمنا بإظهار الرسالة UnderFlow كدلالة على أن index المصفوفة أقل من الصفر.

في الحالة المعاكسة, سنقوم بإظهار قيمة الخانة الحالية و الانتقال إلى الخانة الموالية (لذا أجد أن هذه المحاكاة سيئة جداً لأنه لا يتم حذف العناصر بصفة حقيقية كتحرير الذاكرة كما يحدث في القوائم).

دالة الإظهار أعتقد أنها واضحة, إذا تساوت قيمة rear مع front فهذا يعني أن الطابور فارغ. في الحالة المعاكسة, سنقوم بإظهار كافة عناصر الطابور :

المحاكاة باستخدام القوائم  – مُقدمة

كما قلنا سابقا, توجد عدة صفات مشتركة بين الطابور و المكدس و بالتالي يمكننا اعتبار أن الطابور ما هو إلا حالة خاصة من القوائم المتصلة حيث لا يُمكن إضافة عنصر إلا في نهاية القائمة أما عملية الحذف فتظل كما كانت. بالرغم من تشابه الــ Queue و الــ Stack إلا أن التغييرات ستكون مُعقدة نسبيا نظرا لأن الطابور يُلزمنا بالانتقال إلى بداية أو نهاية القائمة حسب نوع العملية المطلوب إجرائها (إضافة أو حذف).

المحاكاة باستخدام القوائم البسيطة

الإعلان عن الطابور سيكون هكذا:

الطابور يحتوي على قيمة واحدة من نوع int بالإضافة إلى المؤشر ptrNext الذي يُمثل مفتاح الدخول للعقدة الموالية. المؤشر front يُشير إلى قمة الطابور بينما يُشير rear إلى مؤخرة الطابور.

نبدأ مع دالة الإضافة :

في البداية, قمنا بحجز مساحة جديدة للمؤشر q ثم طلبنا من المستخدم إدخال عدد صحيح ليتم تخزينه في المتغير value داخل العقدة الجديدة. إذا كان أحد المؤشرين front أو rear يُشير إلى NULL فهذا يعني أن الطابور فارغ لذلك ستلعب دالة الإضافة في هذه الحالة دور دالة التهيئة, في الحالة المعاكسة سنجعل المؤشر اللاحق لــ rear يُشير إلى الطابور ثم نقوم بتحديث المؤشر rear.

أما دالة الحذف فهي  كالآتي :

إذا كان حمل أحد المؤشرين front أو rear القيمة NULL فهذا يعني أن الطابور فارغ و بالتالي لا توجد عناصر للسحب لذا قمنا بإظهار رسالة تُفيد بذلك.

في الحالة المعاكسة سنقوم بنسخ front داخل q و نُظهر القيمة التي سيتم حذفها ثم نحرر المؤشر q بعد أن ننتقل إلى العقدة الموالية.

بالنسبة لدالة الإظهار فلن تتغير كثيرا (سبق و أن شرحنا فكرتها في الجزء الأول) :

المحاكاة باستخدام القوائم المزدوجة

لتمثيل الطابور باستخدام القوائم المزدوجة يكفي أن نتذكر معا كيفية الإعلان عن قائمة مزدوجة بسيطة تحوي عنصر واحد مثلا:

المؤشر head يُشير إلى قمة الطابور بينما يُشير tail إلى مؤخرة الطابور أما المتغير length فيُمثل طول الطابور.

دالة الإضافة ستكون كالآتي :

في البداية, قمنا بالتحقق من أن الطابور لم يمتلئ بعد, إذا كان قد امتلأ نُظهر رسالة تفيد بذلك و يتم الخروج من الدالة.

إذا تجاوزنا مرحلة التحقق فهذا يعني أن الطابور لم يمتلأ بعد لذا قمنا بالإعلان عن مكدس جديد باسم temp و قمنا بحجز المساحة المطلوبة له ثم أسندنا قيمة الوسيط إلى المتغير value و جعلنا المؤشر اللاحق يُشير إلى NULL. إذا كان طول الطابور يُساوي صفر فهذا يعني أن العقدة المُراد إضافتها هي أول عقدة لذا جعلنا المؤشر السابق يُشير إلى NULL و كذلك اللاحق ثم جعلنا المؤشر head يُشير إلى بداية الطابور. في الحالة المعاكسة (هذا يعني أنه توجد أكثر من عقدة) نجعل المؤشر السابق للعقدة الحالة يُشير إلى tail ثم نجعل المؤشر اللاحق لــ tail يُشير إلى العقدة الحالية.

في النهاية نقوم بتحديث الطابور ثم نزيد طول الطابور بواحد.

بالنسبة لدالة الحذف فستكون كالتالي :

إذا كانت قيمة المتغير length أقل أو تُساوي صفر فهذا يعني أن الطابور فارغ و بالتالي سيتم إظهار رسالة تُفيد بذلك و الخروج من الدالة.

في الحالة المعاكسة, سنقوم بحفظ نسخة من المؤشر المُراد تحريره ثم ننتقل إلى العقدة الموالية و نحرر المؤشر ثم نجعله يُشير إلى NULL (هذه الخطوة مهمة جدا و هي عادة حسنة عند التعامل مع المؤشرات) و أخيرا ننقص طول الطابور بواحد.

دالة الإظهار لن تتغير كثيراً (سبق و أن شرحناها في الجزء الثاني) :

اختبر قدراتك

اكتب برنامج يطلب من المستخدم إدخال جملة ثم يُخبره ما إذا كانت تلك الجملة تُمثل Palindrome أو لا.

ملاحظة : قم بتخزين الجملة في Stack ثم خزن نسخة أخرى من الجملة في Queue و قارن بين محتوى البنيتين.

إلى هنا أصل بك أخي القارئ إلى نهاية هذا الدرس, آمل أن تكون استفدت من هذا الدرس و تعلمتَ أشياء جديدة

تحياتي.