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

تختبر هياكل البيانات هذه قدرتك على العمل مع المؤشرات وفهم ترتيب LIFO/FIFO -- مهارات تظهر في العديد من مسائل المقابلات.

القوائم المترابطة (Linked Lists)

القائمة المترابطة تخزن العناصر في عُقد مرتبطة بمؤشرات. الاختلافات الرئيسية عن المصفوفات:

الخاصية	المصفوفة	القائمة المترابطة
الوصول بالفهرس	O(1)	O(n)
الإدراج في البداية	O(n)	O(1)
الإدراج في النهاية	O(1)*	O(n) أو O(1) مع مؤشر الذيل
الذاكرة	متجاورة	متفرقة
أداء الكاش	أفضل	أسوأ

أنماط القوائم المترابطة الأساسية:

# التعريف
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# النمط 1: عكس القائمة المترابطة
def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# النمط 2: المؤشرات السريعة/البطيئة (كشف الدورات - Floyd)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# النمط 3: إيجاد منتصف القائمة المترابطة
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

نصيحة للمقابلات: تقنية المؤشر السريع/البطيء تحل العديد من مسائل القوائم المترابطة: كشف الدورات، إيجاد المنتصف، إيجاد العقدة رقم n من النهاية، وكشف نقاط التقاطع.

المكدسات (Stacks - LIFO)

المكدسات تتبع ترتيب الأخير يدخل أولاً يخرج. وهي أساسية لـ:

• مطابقة الأقواس -- السؤال الكلاسيكي في المقابلات
• المكدس الرتيب (Monotonic Stack) -- العنصر الأكبر/الأصغر التالي
• تقييم التعبيرات -- التحويل بين الصيغ
• اجتياز DFS -- DFS التكراري يستخدم مكدسًا

# أقواس صالحة (سؤال مقابلة كلاسيكي)
def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

# المكدس الرتيب: العنصر الأكبر التالي
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []  # يخزّن الفهارس
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

الطوابير (Queues - FIFO)

الطوابير تتبع ترتيب الأول يدخل أولاً يخرج. وهي أساسية لـ:

• اجتياز BFS -- اجتياز الأشجار مستوى بمستوى، أقصر مسار
• أقصى النافذة المنزلقة -- باستخدام deque (طابور ثنائي النهاية)
• جدولة المهام -- ترتيب العمليات

from collections import deque

# اجتياز BFS مستوى بمستوى
def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

متى تستخدم ماذا

نوع المسألة	هيكل البيانات	مثال
المطابقة/التداخل	المكدس	أقواس صالحة، وسوم HTML
الأكبر/الأصغر التالي	المكدس الرتيب	أسعار الأسهم، درجات الحرارة
المعالجة مستوى بمستوى	الطابور	BFS للأشجار، أقصر مسار
الترتيب العكسي	المكدس	عكس السلسلة، عمليات التراجع
كشف الدورات	قائمة مترابطة + سريع/بطيء	دورة القائمة، كشف الحلقات

---

التالي: سنستكشف الأشجار والرسوم البيانية -- أكثر هياكل البيانات تعقيدًا التي ستواجهها في المقابلات. :::