المكدس والطابور

١المكدس Stack: آخر من يدخل أول من يخرج

المكدس تركيب بعمليتين أساسيتين: push يضع عنصرًا في القمة، و pop يأخذ العنصر من القمة. وبجانبهما peek لرؤية القمة دون أخذها. كلها O(1).

class Stack:    def __init__(self):        self.items = []    def push(self, x):        self.items.append(x)       # O(1)    def pop(self):        return self.items.pop()    # O(1)    def peek(self):        return self.items[-1]    def is_empty(self):        return len(self.items) == 0 s = Stack()for x in ["كتاب 1", "كتاب 2", "كتاب 3"]:    s.push(x)print("القمة:", s.peek())while not s.is_empty():    print("أخذنا:", s.pop())

نضع القمة في آخر القائمة لا في أولها؛ لأن append و pop() في الآخر O(1)، أما في الأول فـ O(n).

٢تطبيق: هل الأقواس متوازنة؟

المترجم يتحقق أن كل قوس مفتوح له قوس يغلقه بالترتيب الصحيح. الحل بالمكدس: نضع كل قوس مفتوح في المكدس، وعند القوس المغلق نتأكد أن القمة هي القوس المقابل له:

pairs = {")": "(", "]": "["}stack = []ok = Truefor ch in "([)]":    if ch in "([":        stack.append(ch)    elif not stack or stack.pop() != pairs[ch]:        ok = False        breakprint(ok and not stack)

٣الطابور Queue: أول من يدخل أول من يخرج

الطابور يضيف من الخلف enqueue ويُخرج من الأمام dequeue. لو استخدمنا list لكان الإخراج pop(0) بـ O(n). لذلك نستخدم collections.deque، وهو قائمة مترابطة مزدوجة من الداخل: الطرفان كلاهما O(1):

from collections import deque printer = deque()printer.append("تقرير.pdf")      # enqueueprinter.append("شهادة.docx")printer.append("جدول.xlsx") while printer:    doc = printer.popleft()       # dequeue    print("طباعة:", doc, "| الباقي:", len(printer))

٤محاكاة طابور: كم ينتظر العملاء؟

الطوابير تُستخدم لمحاكاة الأنظمة الحقيقية: عملاء يصلون إلى كاشير يخدم عميلًا كل 3 دقائق. كم ينتظر كل عميل؟

from collections import deque arrivals = [("أحمد", 0), ("سارة", 1), ("خالد", 2), ("منى", 8), ("فهد", 9)]SERVICE = 3                       # دقائق لكل عميل queue = deque(arrivals)clock = 0for _ in range(len(arrivals)):    name, arrived = queue.popleft()    start = max(clock, arrived)   # ينتظر حتى يفرغ الكاشير    print(f"{name}: وصل {arrived}، بدأ {start}، انتظر {start - arrived} د")    clock = start + SERVICE

٥متى أستخدم أيهما؟