إطار المجموعات

Queue وDeque والـ Stack

15 دقيقة الدرس 8 من 14

Queue وDeque والـ Stack

الـ Queue (الطابور) هو مجموعة مصمَّمة لحفظ العناصر قبل معالجتها. القاعدة الأساسية هي FIFO — الأول دخولًا هو الأول خروجًا: تُضاف العناصر من طرف (الذيل) وتُحذف من الطرف الآخر (الرأس). تخيّل طابور الدفع في محل البقالة.

الـ Deque (الطابور المزدوج، ينطق "ديك") يعمّم مفهوم الطابور: يمكنك إضافة العناصر وحذفها من كلا الطرفين. هذا التجريد الواحد يمكنه العمل كطابور أو كمكدّس أو كنافذة منزلقة.

واجهة Queue

تمتدّ java.util.Queue<E> من Collection وتضيف عائلتين من الوظائف — إحداهما ترمي استثناءات عند الفشل والأخرى تُعيد قيمة خاصة:

الإضافة من الذيل: add(e) ترمي IllegalStateException؛ offer(e) تُعيد false.
الحذف من الرأس: remove() ترمي NoSuchElementException؛ poll() تُعيد null.
الاطلاع على الرأس: element() ترمي استثناءً؛ peek() تُعيد null.

في الممارسة العملية، استخدم ثلاثي offer / poll / peek — فهو آمن من null والخيار الأسلوبي المعتاد.

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

واجهة Deque

تمتدّ java.util.Deque<E> من Queue وتعكس كل وظيفة على الطرفين. الاتفاقية في التسمية واضحة: تنتهي الوظائف بـ First أو Last.

offerFirst(e) / offerLast(e) — الإضافة من الرأس / الذيل.
pollFirst() / pollLast() — الحذف من الرأس / الذيل، تُعيد null إذا كانت فارغة.
peekFirst() / peekLast() — الاطلاع دون حذف.
push(e) / pop() / peek() — أسماء بديلة للمكدّس تعمل على الرأس.

ArrayDeque — التنفيذ الأمثل

java.util.ArrayDeque<E> مصفوفة دائرية قابلة للتوسّع تُنفّذ Deque. وهي الخيار الصحيح الافتراضي لكلٍّ من الطوابير والمكدّسات في الكود أحادي الخيط.

استخدام ArrayDeque كطابور (FIFO)

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> printQueue = new ArrayDeque<>();

printQueue.offer("job-1");
printQueue.offer("job-2");
printQueue.offer("job-3");

// معالجة بترتيب الوصول
while (!printQueue.isEmpty()) {
    String job = printQueue.poll();   // يحذف الرأس؛ يُعيد null إذا كان فارغًا
    System.out.println("Printing: " + job);
}
// الناتج:
// Printing: job-1
// Printing: job-2
// Printing: job-3

صرِّح عن المتغير كـ Queue<String> لا ArrayDeque<String>. البرمجة وفق الواجهة تُبقي كودك مرنًا — يمكنك الاستبدال بـ LinkedList أو ArrayBlockingQueue المحدودة دون تغيير أي سطر آخر.

استخدام ArrayDeque كمكدّس (LIFO)

المكدّس يتبع قاعدة LIFO — الأخير دخولًا هو الأول خروجًا. حالات الاستخدام الكلاسيكية: تاريخ التراجع، تحليل التعابير، والاجتياز بالعمق أولًا.

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> undoStack = new ArrayDeque<>();

undoStack.push(100);   // يدفع إلى الرأس
undoStack.push(200);
undoStack.push(300);

System.out.println(undoStack.peek());  // 300 — اطلاع دون حذف
System.out.println(undoStack.pop());   // 300 — يحذف من الرأس
System.out.println(undoStack.pop());   // 200
System.out.println(undoStack.pop());   // 100

صرِّح عن المتغير كـ Deque<Integer> حين تقصد دلالات المكدّس. الأسماء البديلة push / pop / peek على Deque تعمل حصرًا على الرأس، وهو بالضبط ما يحتاجه المكدّس.

لماذا تتجنّب java.util.Stack؟

يأتي Java مع كلاس يُسمّى java.util.Stack<E> موجود في JDK منذ الإصدار 1.0. يجب عدم استخدامه في الكود الجديد.

يمتدّ Stack من Vector الذي يزامن كل وظيفة. في الكود أحادي الخيط هذا الاستحواذ على القفل تكلفة صرفة دون أي فائدة.
لأن Stack يمتدّ من Vector، يرث get(int index) وadd(int index, E e) وغيرهما من وظائف الوصول بالفهرس التي تكسر تجريد المكدّس. يمكن للمستدعين إدراج عناصر أو حذفها من أي موضع — وهذا ليس مكدّسًا.
توثيق Javadoc الخاص بـ Stack نفسه يقول: "مجموعة أكثر اكتمالًا واتساقًا من عمليات LIFO للمكدّس توفّرها واجهة Deque وتنفيذاتها، التي يجب استخدامها بدلًا من هذا الكلاس."

لا تستخدم java.util.Stack أبدًا في الكود الجديد. استخدم بدلًا منه Deque<E> stack = new ArrayDeque<>();. إنه أسرع (لا مزامنة)، ويكشف فقط العمليات المناسبة للمكدّس عبر نوع الواجهة Deque، وهو التوصية في Javadoc الرسمي.

خصائص الأداء

تخزّن ArrayDeque العناصر في مصفوفة دائرية. جميع عمليات الحدود الأربع — الإضافة والحذف من الرأس أو الذيل — هي O(1) مستهلكة. تتضاعف المصفوفة حين تمتلئ وهو نسخ O(n) عرضي، لكن بالمتوسط على جميع عمليات الإدراج تكون التكلفة O(1). لا يوجد تكلفة تخصيص لكل عقدة كما في البنى المرتبطة.

تُنفّذ LinkedList أيضًا Deque، لكن كل عنصر كائن مستقل على الكومة مع حقلَي مؤشر. لأعباء عمل الطوابير والمكدّسات، تستهلك ArrayDeque ذاكرة أقل ولها موقع تخزين مؤقت أفضل مما يجعلها أسرع عمليًا. افضّل ArrayDeque ما لم تحتج تحديدًا إلى واجهة List على الكائن ذاته.

نصيحة — أعطِ الـ Deque سعة ابتدائية إذا كنت تعرف الحجم مسبقًا. new ArrayDeque<>(1024) يخصّص المصفوفة الداخلية مسبقًا متجنّبًا نسخ تغيير الحجم خلال مرحلة الملء. السعة الافتراضية 16 عنصرًا.

مثال عملي: مدقّق الأقواس المتوازنة

التحقق من توازن الأقواس في سلسلة نصية مسألة كتابية كلاسيكية للمكدّس. كل قوس فاتح يُدفع؛ كل قوس غالق يجب أن يطابق قمة المكدّس.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class BracketChecker {

    private static final Map<Character, Character> PAIRS = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

    public static boolean isBalanced(String input) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : input.toCharArray()) {
            if (PAIRS.containsValue(ch)) {
                stack.push(ch);                 // قوس فاتح
            } else if (PAIRS.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != PAIRS.get(ch)) {
                    return false;               // قوس غالق غير متطابق
                }
            }
        }
        return stack.isEmpty();                 // أي فاتحون متبقّون = غير متوازن
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("({[]})"));   // true
        System.out.println(isBalanced("({[})"));    // false
        System.out.println(isBalanced("((())"));    // false
    }
}

الاختيار بين Queue وDeque

تحتاج معالجة FIFO صارمة؟ صرِّح عن المتغير كـ Queue<E> وخلفيّته ArrayDeque.
تحتاج مكدّسًا (LIFO)؟ صرِّح كـ Deque<E> وخلفيّته ArrayDeque، واستخدم push/pop/peek.
تحتاج التعامل مع الطرفين (مثل نافذة منزلقة)؟ استخدم Deque<E> مع واجهة برمجة First/Last الكاملة.
تحتاج أمانًا متعدد الخيوط؟ انظر إلى java.util.concurrent: LinkedBlockingDeque وConcurrentLinkedQueue وغيرها.

الخلاصة

تُعرِّف Queue دلالات FIFO؛ تعمّمها Deque للطرفين وتعمل أيضًا كمكدّس. ArrayDeque هو التنفيذ الصحيح لكلا الدورين في الكود أحادي الخيط — إنه أسرع وأقل استهلاكًا من LinkedList لعمليات الحدود فقط. صرِّح دائمًا عن المتغيرات كـ Queue<E> أو Deque<E>، لا بالنوع الملموس. ولا تلجأ أبدًا إلى كلاس Stack القديم: Javadoc نفسه يوجّهك إلى Deque.