تكرار السؤال: …
الإجابة المختصرة
المكدس يعمل بنظام 'من يدخل آخراً يخرج أولاً' (LIFO)، والطابور بنظام 'من يدخل أولاً يخرج أولاً' (FIFO). والمكدس الرتيب يحافظ على ترتيب تصاعدي أو تنازلي صارم لعناصره لحل مسائل النطاقات بـ O(N).
الشرح
تُستخدم الـ Stacks في تتبع استدعاء الدوال (Call Stack)، التراجع (Undo)، والتحقق من الأقواس المتوازنة. وتُستخدم الـ Queues في جدولة المهام ومعالجة الطلبات بالترتيب. أما الـ Monotonic Stack فيُستخدم في مسائل الخوارزميات المتقدمة (مثل إيجاد أول عنصر أكبر Next Greater Element أو حساب مساحة المستطيلات في الهيستوجرام)، حيث يتم إخراج العناصر التي تخل بالترتيب الرتيب قبل الإضافة.
مثال بالكود
from collections import deque
stack = []
stack.append(1); stack.append(2)
print(stack.pop()) # 2 (LIFO)
queue = deque()
queue.append(1); queue.append(2)
print(queue.popleft()) # 1 (FIFO)
def next_greater(nums): # monotonic stack: each element is pushed/popped once → O(n)
result, stack = [-1] * len(nums), [] # stack holds indices of a decreasing sequence
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return result
print(next_greater([2, 1, 5, 3])) # [5, 5, -1, -1]أخطاء شائعة
- استخدام مصفوفة عادية في لغة لا تدعم إزالة العنصر الأول بـ O(1) للطابور (مثل array.shift()) مما يسبب كلفة O(N) مع كل عملية خروج.