Queue و Dequequeue · FIFO · head index · circular buffer · deque · monotonic deque

في الفصل اللي فات (Stack) كان الـ rule إن آخر حاجة تدخل هي أول حاجة تطلع. دلوقتي العكس بالظبط: الـ queue، اللي يدخل الأول يطلع الأول. شكله أبسط data structure ممكنة، بس في JS الطريقة الـ obvious (push و shift) ممكن تقلب حلك O(n²) من غير ما تاخد بالك. هنا هتعرف ليه، وتعمل queue سريع بجد، وتجيب الـ max لكل window في O(n) بـ deque.

قبله: Stack و Sliding Window بيمهّد لـ: BFS في الـ Graphs و Trees

هتطلع من الفصل ده وإنت عارف

  • تعرف من كلام المسألة إنها queue (الأقدم الأول)، ولا stack (الأحدث الأول)، ولا deque (من الناحيتين).
  • تفهم ليه shift() بتاخد O(n) في JS، وتكتب queue بـ head index وبـ linked list من دماغك.
  • تكتب circular buffer، وتعرف ليه (i - 1 + cap) % cap مش (i - 1) % cap.
  • تفهم يعني إيه amortized O(1)، وتشرحها في انترفيو.
  • تحل Sliding Window Maximum بـ monotonic deque، وتثبت إنها O(n) مع إن فيها while جوه for.
  • تشوف إن الـ queue هو قلب الـ BFS.

ليه Queue؟

حاجات كتير لازم تتعالج by order of arrival: requests جاية على server، print jobs، رسايل في chat، ناس مستنية دورها. اللي وصل الأول ليه الحق يتخدم الأول، والـ data structure اللي بتضمن الترتيب ده اسمها queue.

تشبيه طابور الفرن الصبح. الجديد بيقف في آخر الطابور، والعيش بيتدّى للي في أوله. محدش بيدخل من النص، ومحدش بيتخدم قبل اللي قدامه. لو حد عمل كده الناس هتتخانق، ولو الكود بتاعك عمل كده الإجابة هتطلع غلط.
العمليةبتعمل إيهالمفروض تاخد
enqueue(x)تضيف x في الآخر (الـ back)O(1)
dequeue()تشيل اللي في الأول (الـ front) وترجّعهO(1)
peek()تبص على الـ front من غير ما تشيلهO(1)
size() / isEmpty()عدد العناصر / فاضي ولا لأO(1)

بص عليه وهو شغال بالطريقة اللي أي حد بيكتبها في JS أول مرة:

الترتيب اللي خرجوا بيه هو نفس ترتيب دخولهم. ده FIFO: First In, First Out، عكس الـ LIFO بتاع الـ stack. الفرق كله في سؤال واحد: لما أشيل، أشيل الأقدم ولا الأحدث؟

المشكلة إن JS ما فيهاش Queue built-in. في C++ عندك std::queue، وفي Python collections.deque، وفي Java ArrayDeque. في JS الناس بتستخدم array: push للآخر و shift من الأول. الـ push تمام، والـ shift هي الـ catch.

بس قبل ما نحل مشكلة shift، إزاي تعرف أصلًا إن المسألة عايزة queue؟

إزاي تعرفه من المسألة

لما تشوف: in order of arrivalfirst come, first servedrecent requests in the last X ms simulate turns / roundslevel by levelshortest path (unweighted) minimum number of stepsmax / min of every window of size kfixed-size bufferadd / remove at both ends
ومش هو غالبًا لو: matching brackets / undothe newest item firstsmallest / largest of everything so far

أول اتنين في السطر التاني دول stack، لأن الأحدث هو اللي بيتعالج الأول. والتالت heap، لأنك عايز أصغر عنصر من كل اللي اتضاف، مش من آخر k بس.

النوعبيعمل إيهبنعمله في JS إزايأشهر مسائل
Queue عاديتضيف في الآخر وتشيل من الأولarray + head indexNumber of Recent Calls، Time Needed to Buy Tickets
Circular queueحجم ثابت، بيعيد استخدام الأماكن الفاضيةarray + head + size + %Design Circular Queue
Dequeتضيف وتشيل من الناحيتينcircular buffer، أو array + head و tailDesign Circular Deque
Monotonic dequemax أو min لكل windowdeque فيه indices قيمهم مترتبةSliding Window Maximum
BFS queueتلف على graph مستوى مستوىarray + headRotting Oranges، أقصر طريق في grid
flowchart TD
  A["Items are processed by arrival time"] --> B{"Oldest first?"}
  B -- no --> S["Newest first: stack"]
  B -- yes --> C{"Remove from the back too?"}
  C -- no --> Q["Queue: array + head index"]
  C -- yes --> D{"Max or min of a moving window?"}
  D -- yes --> M["Monotonic deque of indices"]
  D -- no --> DQ["Deque: circular buffer"]
  Q --> E{"Fixed capacity?"}
  E -- yes --> R["Circular queue"]
  

اسأل نفسك الأسئلة دي بالترتيب ده.

في أغلب الحالات هتبدأ بـ array. طب إيه بالظبط المشكلة في shift()؟

ليه shift() بطيئة؟

الـ array في الـ memory خانات جنب بعض، والـ index هو رقم الخانة. والـ invariant إن arr[0] هو أول عنصر دايمًا. فلما تشيل أول عنصر، كل العناصر لازم تتنقل خانة شمال عشان التاني يبقى arr[0]. الـ spec بتاعة JS نفسها بتوصف shift كده، والكود ده بيعمل نفس اللي بيحصل جوه:

  1. بنحفظ أول عنصر قبل ما الـ loop تكتب فوقه.
  2. الـ k بيبدأ من 1 عشان بننقل arr[k] لـ arr[k - 1]، ولو بدأ من 0 هنكتب في arr[-1]. الـ loop بتلف n - 1 مرة، وده الـ O(n).
  3. مفيش طريقة تخلّي التاني يبقى arr[0] من غير ما الكل يتحرك، لأن الـ index لازم يفضل هو مكان الخانة.
  4. بعد النقل آخر عنصر بقى موجود مرتين، فبنقصّر الـ array خانة.

5 نقلات عشان عنصر واحد. لو هتطلّع كل العناصر زي ما بيحصل في BFS: (n - 1) + (n - 2) + ... = حوالي n²/2. يعني queue فيه 100,000 عنصر = حوالي 5 مليار نقلة. ده O(n²) مستخبّي جوه سطر شكله بريء.

جرّبتها على Node 24: 100 ألف رقم طلّعتهم مرة بـ shift ومرة بـ head index (الطريقة الجاية). الـ shift كانت أبطأ بمئات المرات، ولما ضاعفت العدد لـ 200 ألف وقتها اتضرب في 4 تقريبًا. ضاعفت n فالوقت اتضرب في 4: ده بالظبط شكل O(n²).

خلي بالك على arrays صغيرة shift ممكن تبان سريعة، لأن V8 (الـ engine بتاع Chrome و Node) ساعات بيحرّك "بداية" الـ array بدل ما ينقل العناصر. ده optimization جوه الـ engine، مش مضمون، وفي التجربة اللي فوق بطّل يشتغل مع الـ arrays الكبيرة. في الانترفيو اعتبر shift() و unshift() و splice(0, 1) كلهم O(n).

طب إزاي نعمل dequeue من غير ما نحرّك ولا عنصر؟

Queue بـ head index: القالب الأساسي

الـ key insight: بدل ما ننقل العناصر، ننقل الـ front نفسه. العناصر بتفضل مكانها، ومعانا متغير head معناه "أول عنصر لسه ما خرجش موجود في الـ index ده". الـ dequeue بقى مجرد head++.

تشبيه نظام التذاكر في البنك. محدش بيقوم يتحرك كرسي لقدام كل ما حد يخلص. كل واحد قاعد مكانه بالرقم بتاعه، والشاشة بتعرض "رقم 37"، ولما يخلص تبقى 38. الشاشة دي هي الـ head.
  1. ليه head = 0؟ أول push هيروح index 0 وده هيبقى الـ front. كل اللي قبل head خرج خلاص، بس لسه في الـ array.
  2. push بتضيف في الآخر من غير ما تحرّك حاجة: amortized O(1)، لأن الـ array ساعات بتكبر وتتنسخ بس ده نادر.
  3. الـ early return ده مش عشان error. لو الـ queue فاضي وعملنا head++، الـ head هيعدّي length و size() تطلع سالبة. و undefined هو نفس اللي [].shift() بترجّعه.
  4. ده الحل كله: سطر O(1) بدل n - 1 نقلة.
  5. تنضيف optional. من غيره queue خدم مليون عنصر هيفضل شايل مليون خانة. بننضّف لما الميتين يبقوا النص أو أكتر، فالأحياء اللي الـ slice بتنسخهم أقل من عدد اللي خرجوا من آخر تنضيف، فالمتوسط يفضل O(1). في LeetCode تقدر تشيل السطور دي.
  6. الحجم = length - head، مش length. دي أشهر غلطة مع الـ head index، لأن الـ length فيها الميتين.

الخانات الباهتة خرجت من الـ queue بس لسه في الـ array. ولاحظ إن ولا عنصر بيتحرك مع الـ dequeue:

في الاختبار مش محتاج class في أغلب المسائل (زي الـ BFS) هتكتبه inline على طول: const queue = [start]; let head = 0; وبعدين while (head < queue.length) { const x = queue[head++]; ... }. نفس الفكرة في 3 سطور.

الـ head index سريع، بس الخانات الميتة بتفضل في الـ memory لحد التنضيف. فيه طريقة من غير array خالص؟

Queue بـ linked list

كل عنصر بيتحط في node صغيرة فيها القيمة و pointer اسمه next بيشاور على اللي وراه. ومعانا pointer على أول node (head) و pointer على آخر node (tail). الـ enqueue بيربط node بعد الـ tail، والـ dequeue بيحرّك الـ head one step. الاتنين O(1)، ومفيش خانات ميتة.

تشبيه طابور كل واحد فيه عارف بس مين واقف وراه، والعسكري اللي بينظّم عارف أول واحد وآخر واحد. جه حد جديد؟ العسكري يقول لآخر واحد "ده وراك". أول واحد خلص؟ يسأله "مين وراك؟" ويبقى ده الأول.
  1. الـ next بيبدأ null لأن أي node جديدة بتتحط في الآخر، فمفيش حد وراها.
  2. ليه محتاجين tail؟ من غيره، عشان تضيف في الآخر لازم تمشي من الـ head لآخر node، وده O(n).
  3. الـ edge case بتاع الـ queue الفاضي: مفيش tail نربط بعده، فالـ node الجديدة هي الأول والآخر. من غيره الـ head هيفضل null للأبد.
  4. الـ queue مش فاضي: آخر node بقت تشاور على الجديدة، والجديدة بقت هي الآخر.
  5. الـ front بقى اللي بعده. الـ node القديمة محدش بيشاور عليها، فالـ garbage collector هيشيلها.
  6. السطر اللي الناس بتنساه. لو شلنا آخر عنصر، head بقى null بس tail لسه على node ميتة. الـ enqueue الجاي هيربط فيها، والعنصر يضيع.
الطريقةenqueuedequeueالـ memoryتستخدمها إمتى
array + shiftO(1)O(n)قد العناصرqueue صغير جدًا بس. ما تعتمدش عليها.
array + headO(1)*O(1)بتشيل الميتين لحد التنضيفأغلب المسائل، وخصوصًا BFS. الأسرع في الكتابة.
linked listO(1)O(1)قد العناصر + pointer لكل عنصرqueue عايش كتير وبيخدم عناصر كتير.
circular bufferO(1)O(1)ثابتة: k خانةلما الحجم الأقصى معروف (مثال 3).

* amortized: في المتوسط، مش كل مرة لوحدها.

كده عندك queue O(1). يلا نستخدمه في أول مسألة.

مثال محلول 1: Number of Recent Calls

أول مثال بيطبّق القالب زي ما هو. الجديد هنا إن الـ queue بيمثّل window بالزمن، واللي بيخرج منها مش بيرجع تاني.

Number of Recent Calls

easyLeetCode 933

اعمل class اسمها RecentCounter فيها ping(t). كل نداء معناه request وصل في الوقت t بالـ ms. رجّع عدد الـ requests اللي في الفترة [t - 3000, t] بالطرفين. الـ t مضمون إنه بيزيد كل مرة.

ping(200) → 1 [200] ping(1500) → 2 [200, 1500] ping(3100) → 3 window 100..3100: all three ping(3300) → 3 window 300..3300: 200 is out ping(4600) → 3 window 1600..4600: 1500 is out ping(7000) → 2 window 4000..7000: 3100 and 3300 are out

نفكّر فيها مع بعض

  1. افهم المطلوب: window زمنية طولها 3000 بتتحرك لقدام مع كل ping، والطرفين داخلين.
  2. Brute force: نحفظ كل الـ pings ونعدّ اللي جوه الفترة كل مرة. O(n) لكل ping، يعني O(n²) في الآخر.
  3. الـ key insight: الـ t بيزيد دايمًا، فالحد t - 3000 بيزيد. يعني ping بقى أقدم من الحد النهارده هيفضل أقدم منه للأبد: اللي يخرج ما بيرجعش.
  4. واللي بيخرج دايمًا الأقدم: الـ pings داخلة بالترتيب، فنضيف في الآخر ونشيل من الأول. ده queue، والإجابة هي حجمه.
  5. Edge cases: أول ping، و ping عند t - 3000 بالظبط (لازم يتحسب)، وفجوة كبيرة بتخرّج كل اللي قبلها.
  1. نفس القالب: array و head. الـ times sorted لوحدها لأن الـ t بيزيد.
  2. بنضيف الجديد قبل الـ while، وده اللي بيضمن إن الـ while تقف (السطر الجاي).
  3. ليه < مش <=؟ الفترة بالطرفين، فالـ ping اللي عند t - 3000 بالظبط لازم يفضل. ومفيش head < length في الشرط لأن آخر عنصر هو t، وعمره ما هيبقى أقل من t - 3000.
  4. head++ بدل shift(): O(1).
  5. الإجابة هي حجم الـ queue: كل اللي من head للآخر جوه الفترة.
الـ pingsالمتوقعليه الحالة دي مهمة
ping(5)1أول ping: الـ while مش بتدخل
ping(1), ping(3001)1, 2الطرف بالظبط: الـ < بيخلّي الـ 1 جوه
ping(1), ping(3002)1, 1الـ 1 بقى أقدم من الحد بواحد، فخرج
ping(10), ping(20), ping(99999)1, 2, 1فجوة كبيرة: الـ while بتشيل أكتر من عنصر

التعقيد: الـ while ممكن تلف كتير في ping واحد، بس كل ping بيدخل مرة وبيخرج مرة بالكتير. فمجموع لفّاتها على كل الـ pings n بالكتير: O(1) amortized لكل ping، و O(n) memory.

طب لو المسألة قالتلك: ممنوع تستخدم غير stacks، اعمل queue؟

مثال محلول 2: Implement Queue using Stacks

الجديد هنا فكرة amortized O(1) بوضوح: عملية واحدة ممكن تبقى غالية، بس الشغل الكلي على n عملية O(n).

Implement Queue using Stacks

easyLeetCode 232

اعمل queue (push في الآخر، pop و peek من الأول، و empty) بس مسموحلك بعمليات الـ stack بس: تحط فوق، تشيل من فوق، تبص على اللي فوق، الحجم. يعني في JS: push و pop و arr[arr.length - 1] و length.

push(1), push(2), push(3) peek() → 1 pop() → 1 push(4) pop() → 2 pop() → 3 pop() → 4 empty() → true

نفكّر فيها مع بعض

  1. المشكلة: الـ stack بيطلّع الأحدث، والـ queue لازم يطلّع الأقدم، والأقدم مدفون تحت.
  2. الملاحظة: لو صبّيت stack في stack تاني، الترتيب بيتقلب، والأقدم بيبقى على الوش.
  3. Brute force: مع كل pop نصب، نشيل، ونصب تاني نرجّع. شغال، بس كل pop بقى O(n).
  4. الحل الـ lazy: inStack للجديد و outStack للشيل، وما بنصبّش إلا لما outStack يفضى. ليه صح؟ الـ invariant إن أي عنصر في outStack أقدم من أي عنصر في inStack، فاللي فوق outStack هو الأقدم في الـ queue كله.
  5. Edge cases: peek قبل أي pop، و push في النص بين الـ pops، وتفضّي الاتنين لحد ما empty تبقى true.
تشبيه رصّة أطباق اتغسلت بالترتيب، وأول طبق تحت خالص. عايز الأقدم الأول؟ انقل الرصّة طبق طبق لرصّة جنبها، فالأقدم يبقى فوق. فضل خد من الرصّة التانية لحد ما تخلص، والأطباق الجديدة على الأولى، وما تنقلش تاني إلا لما التانية تفضى.
  1. الـ queue كله = outStack من فوق لتحت، وبعده inStack من تحت لفوق.
  2. الـ push O(1) دايمًا، ومش بيلمس outStack.
  3. pop بتنادي peek عشان منطق الصب يتكتب مرة واحدة بس.
  4. أهم سطر: بنصب بس لو outStack فاضي. لو صبّينا وهو فيه حاجة، الجديد يقعد فوق القديم والترتيب يبوظ.
  5. أقدم عنصر كان تحت خالص في inStack، فبيتنقل في الآخر ويقعد فوق خالص في outStack.
  6. لازم الاتنين يبقوا فاضيين. ممكن outStack يبقى فاضي و inStack فيه عناصر لسه ما اتصبّتش.

الـ stackين معروضين كـ arrays: الخانة اللي عليها top هي فوق الـ stack. وتحتهم الـ queue زي ما المستخدم شايفه، ولاحظ إنه ما بيتغيرش وإحنا بنصب:

يعني إيه amortized O(1)؟

أول peek في الـ animation نقلت 3 عناصر مرة واحدة، وده O(n). بس بص على كل عنصر لوحده طول حياته: بيتحط في inStack، بيتشال منه، بيتحط في outStack، بيتشال منه. 4 عمليات بالظبط، وعمره ما بيرجع inStack. فـ n عملية = أقل من 4n شغل، يعني O(1) في المتوسط لكل عملية. زي قسط العربية: الصبّة الكبيرة متقسّطة على العناصر اللي اتصبّت.

العملياتالمتوقعليه الحالة دي مهمة
push(7), peek()7peek بتصب حتى لو مفيش pop قبلها
push(1), push(2), pop(), push(3), pop()1, 2push في النص: الـ 3 لازم يستنى ورا الـ 2
push(1), pop(), empty()1, trueالاتنين فاضيين
push(1), push(2), pop(), empty()1, falseinStack فاضي بس outStack فيه 2

التعقيد: push و empty O(1) دايمًا. pop و peek O(n) في الـ worst case لعملية واحدة، و O(1) amortized. والـ memory O(n).

في الانترفيو الـ follow-up المشهور: "خلّي كل العمليات amortized O(1)". قول جملة الـ 4 عمليات لكل عنصر بصوت عالي. والمسألة العكسية (Stack using Queues) في قايمة التمرين.

الـ two stacks والـ head index الاتنين amortized. طب لو الحجم ثابت وعايز كل عملية O(1) بجد؟

مثال محلول 3: Design Circular Queue

الجديد هنا الـ wrap-around: لما توصل لآخر خانة، ترجع تستخدم أول خانة بالـ %، فمفيش نسخ خالص ولا amortized.

Design Circular Queue

mediumLeetCode 622

اعمل queue حجمه الأقصى k: enQueue(value) و deQueue() بيرجّعوا true لو نجحوا و false لو لأ، و Front() و Rear() بيرجّعوا أول وآخر عنصر أو -1 لو فاضي، و isEmpty() و isFull(). الأماكن اللي بتفضى من الأول لازم تتستخدم تاني.

k = 4 enQueue(1), enQueue(2), enQueue(3), enQueue(4) → true × 4 enQueue(5) → false (full) Rear() → 4 deQueue(), deQueue() → true, true enQueue(5), enQueue(6) → true, true (they reuse slots 0 and 1) isFull() → true Front() → 3 Rear() → 6

نفكّر فيها مع بعض

  1. ليه الـ head index لوحده مش كفاية؟ في array ثابتة بحجم 4: بعد 4 enqueue و 2 dequeue الآخر وصل لآخر خانة، فمفيش مكان، مع إن أول خانتين فاضيين.
  2. الـ key insight: نعتبر الـ array دايرة: بعد آخر خانة ييجي خانة 0. والـ % بيعمل كده: (3 + 1) % 4 = 0.
  3. نمسك إيه؟ head و size. مكان الآخر (head + size - 1) % k، ومكان الإضافة الجاية (head + size) % k.
  4. ليه size مش tail؟ لو مسكنا head و tail بس، الفاضي والمليان الاتنين head === tail. الـ size بيفرّق بينهم من غير أي لف.
  5. Edge cases: k = 1، إضافة في queue مليان، شيل من فاضي، Front و Rear على فاضي، والـ wrap-around نفسه.
تشبيه ساعة الحيطة. الساعة 11 وزوّدت 3 ساعات؟ العقرب مش بيروح 14، بيلف ويقف على 2: (11 + 3) % 12 = 2. الـ array الدايرية زي الساعة بالظبط.
  1. array بحجم ثابت عمرها ما بتكبر، والـ state كلها في رقمين: الأول فين، وكام واحد جوه.
  2. مليان؟ المسألة عايزة false، مش error ومش نكتب فوق حاجة.
  3. ليه head + size؟ العناصر في head لـ head + size - 1، فأول خانة فاضية بعدهم head + size. والـ % cap بيلف بيها للأول لو عدّت الآخر.
  4. ممكن الخانة فيها قيمة قديمة خرجت، عادي، بنكتب فوقها.
  5. ده الـ dequeue كله: الـ head يتقدم one step ويلف لـ 0 بعد آخر خانة. مش بنمسح القيمة، هي بقت برا الـ range.
  6. لازم نتشيك على الفاضي الأول، لأن data[head] ممكن فيها قيمة قديمة خرجت، فهترجّع رقم غلط بدل -1.
  7. هنا التشيك أهم: لو size = 0 و head = 0، الحساب -1 % cap، وفي JS ده -1 مش cap - 1. هنرجع للنقطة دي في الـ deque.
  8. الفاضي والمليان من size على طول، وده سبب اختيارنا ليه.

الخانات الزرقا جوه الـ queue، والباهتة فيها قيم قديمة خرجت. ركّز على الـ wrap-around لما الـ 5 والـ 6 يدخلوا:

الحالةالمتوقعليه مهمة
k = 1: enQueue(9), enQueue(8)true, falseمليان من أول عنصر
Front() / Rear() on empty-1, -1من غير التشيك، Rear هتحسب -1 % k
deQueue() on emptyfalseمن غير التشيك size هتبقى سالبة
enQueue after wrapالخانة 0، 1، ...الـ % بيلف من الآخر للأول

التعقيد: كل العمليات O(1) فعلًا، مش amortized. والـ memory O(k) ثابتة.

لو شلنا size ومسكنا head و tail بس (الـ tail = مكان الإضافة الجاية)، إيه اللي هيبوظ؟

  • الـ enqueue هيبقى O(n)
  • الفاضي والمليان الاتنين هيبقوا head === tail، ومش هنعرف نفرّق
  • مش هنعرف نحسب الـ Front
  • مفيش حاجة هتبوظ خالص

في الأول head = tail = 0 والـ queue فاضي. بعد k إضافات الـ tail لفّ ورجع 0، فبقى head === tail والـ queue مليان. الحلول: يا تمسك size، يا تسيب خانة فاضية دايمًا (array حجمها k + 1) عشان المليان يبقى (tail + 1) % cap === head.

الـ circular queue بيضيف من ورا ويشيل من قدام. طب لو محتاج تضيف وتشيل من الناحيتين؟

الـ Deque: queue من الناحيتين

الـ deque (بتتنطق "دِك"، اختصار double-ended queue) بيضيف ويشيل من الأول ومن الآخر. يعني هو queue و stack في نفس الوقت.

العمليةفي JS arrayالتكلفة في الـ arrayالمفروض في deque
إضافة في الآخرpushO(1)O(1)
شيل من الآخرpopO(1)O(1)
إضافة في الأولunshiftO(n)O(1)
شيل من الأولshiftO(n)O(1)

الـ array نصها deque كويس (الآخر) ونصها وحش (الأول). نفس الـ circular buffer بيحلها: الإضافة في الأول معناها إن الـ head يرجع خطوة لورا، ولو كان عند 0 يلف لآخر خانة. دي Design Circular Deque:

  1. نفس state الـ circular queue بالظبط: head و size.
  2. أهم سطر. لو head = 0 الخانة اللي قبله هي cap - 1، بس (0 - 1) % 4 في JS بتطلع -1. الـ + cap بيخلّي الرقم موجب دايمًا، ومش بيغيّر الباقي في الحالات العادية: (5 - 1 + 8) % 8 = 4.
  3. بنحرّك الـ head الأول وبعدين نكتب، لأن الـ head القديم فيه الـ front الحالي.
  4. الشيل من الأول: الرقم موجب دايمًا، فمش محتاجين + cap.
  5. الآخر مكانه head + size - 1، فلما size تقل الآخر بقى اللي قبله لوحده.
في مسائل الـ window مش محتاج كل ده في الـ monotonic deque (المثال الجاي) مفيش إضافة في الأول، وكل index بيدخل مرة واحدة. فكفاية array عادية فيها head و tail: الشيل من الأول head++، والشيل من الآخر tail--، والإضافة dq[tail++] = i. من غير % ومن غير shift.

طب إيه أشهر مسألة محتاجة تشيل من الناحيتين؟ الـ max لكل window.

مثال محلول 4: Sliding Window Maximum

الجديد هنا إن الـ deque مش بس بيشيل من الناحيتين، ده مترتب (monotonic): بنرمي منه أي عنصر بقى مالوش لازمة. نفس روح الـ monotonic stack من الفصل اللي فات، بس مع window بتخرّج عناصر من الأول.

Sliding Window Maximum

hardLeetCode 239

عندك array nums ورقم k. فيه window طولها k بتبدأ من أول الـ array وبتتحرك خانة خانة لحد الآخر. رجّع أكبر رقم في كل window.

Input: nums = [5, 3, 4, 1, 7, 2, 2, 6], k = 3 Output: [5, 4, 7, 7, 7, 6] [5 3 4] → 5, [3 4 1] → 4, [4 1 7] → 7, [1 7 2] → 7, [7 2 2] → 7, [2 2 6] → 6

نفكّر فيها مع بعض

  1. Brute force: لكل window نلف على الـ k عنصر. O(n·k)، ومع n = 10⁵ و k = 5·10⁴ ده 2.5 مليار عملية: TLE.
  2. ليه الـ sliding window العادي مش كفاية؟ المجموع لما عنصر يخرج بتطرحه وخلاص. لكن الـ max لو خرج، مش هتعرف مين بعده من غير ما تلف تاني.
  3. حل متوسط: heap فيه العناصر، وتشيل اللي خرج لما يطلع فوق. O(n log n).
  4. الـ key insight: لو j < i و nums[j] <= nums[i]، يبقى j عمره ما هيبقى max تاني: أي window جاية فيها j فيها i كمان، و j هيخرج قبله. فنرميه.
  5. النتيجة: اللي بيفضل indices طالعة وقيمهم نازلة، فالـ max هو الـ front. بنشيل من الآخر (اللي بقوا مالهمش لازمة) ومن الأول (الـ max لما يخرج من الـ window)، عشان كده deque.
  6. بنخزّن indices مش قيم: عشان نعرف الـ front خرج من الـ window ولا لأ، محتاجين مكانه، وخصوصًا مع المكررات.
تشبيه مسابقة "مين أطول واحد" في طابور بيتحرك: كل دقيقة واحد بيدخل من ورا وواحد بيمشي من قدام. لما يدخل واحد طويل، كل اللي قدامه وأقصر منه مالهمش أمل، لأنه هيفضل موجود بعدهم كلهم. فبنشطبهم، والكشف اللي فاضل مترتب من الأطول للأقصر، وأول اسم فيه هو الكسبان.
  1. ليه array بطول n؟ كل index بيدخل مرة واحدة، فالـ tail عمره ما هيعدّي n. ومش بنستخدم shift لأنها O(k) والحل يبقى O(n·k).
  2. الـ deque هو dq[head .. tail - 1]، والـ tail معناه "الخانة الفاضية الجاية" زي length.
  3. ليه <=؟ الـ window هي [i - k + 1, i]، فأول index برا هو i - k. و if مش while لأن الـ window بتتحرك one step فبيخرج index واحد بالكتير، وبنبص على الـ front بس لأنه الأقدم.
  4. قلب الحل: اللي في الآخر أصغر من أو قد الجديد مالوش لازمة، فنرميه. الـ <= بترمي القديم المساوي لأنه هيخرج الأول، والـ < صح برضه بس بتسيب مكررات.
  5. نضيف i في الآخر (post-increment: نكتب في dq[tail] وبعدين tail يزيد). الترتيب لسه نازل لأن كل اللي قدامه أكبر منه.
  6. ليه i >= k - 1؟ أول window كاملة بتخلص عند index k - 1. لو كتبت i > k - 1 هتضيّع أول window، ده بالظبط الـ off-by-one بتاع < و <=.

الخانات الزرقا هي الـ window، واللي حواليها خط متقطع موجودة في الـ deque. الـ deque تحت مكتوب فيه index:value:

ليه O(n) مع إن فيه while جوه for؟ عدّ من ناحية العناصر مش اللفات: كل index بيتضاف مرة واحدة (سطر 8)، وبيتشال مرة واحدة بالكتير (سطر 6 أو 7). فمجموع لفّات الـ while على البرنامج كله أقل من n، والشغل كله O(n). نفس حجة الـ amortized بتاعة الـ two stacks.
Inputالمتوقعليه الحالة دي مهمة
[4], k = 1[4]عنصر واحد: سطر 9 بيشتغل من أول لفة
[1, -1], k = 1[1, -1]k = 1: الإجابة هي الـ array نفسها
[3, 1, 2], k = 3[3]k = n: window واحدة بس
[9, 8, 7, 6, 5], k = 2[9, 8, 7, 6]نازلة: محدش بيترمي من الآخر، كله بيخرج من الأول
[1, 2, 3, 4, 5], k = 2[2, 3, 4, 5]طالعة: كل جديد بيرمي اللي قبله
[2, 2, 2, 2], k = 3[2, 2]مكررات: الـ <= بترمي القديم المساوي
[9, 1, 2], k = 2[9, 2]الـ 9 لازم يخرج عند i = 2: اختبار لـ <= في سطر 6

التعقيد: O(n) وقت. والـ memory O(n) عشان حاجزين array بطول n، مع إن الـ deque الحي k عنصر بالكتير. لو عايز O(k) بالظبط استخدم circular buffer بحجم k.

في سطر 7، لو غيّرنا <= لـ <، إيه اللي هيحصل؟

  • الإجابة هتطلع غلط لما يبقى فيه أرقام متكررة
  • الإجابة هتفضل صح، بس الـ deque هيشيل مكررات مالهاش لازمة
  • الحل هيبقى O(n²)
  • هيضرب error

مع < القيم في الـ deque بتبقى "نازلة أو متساوية". الـ front لسه هو الـ max، وكل index لسه بيدخل ويخرج مرة، فالحل صح و O(n). الفرق إن القديم المساوي بيفضل قاعد من غير لازمة.

في الانترفيو ابدأ بالـ brute force O(n·k)، وبعدين الـ heap O(n log n)، وبعدين قول الـ key insight بصوت عالي: "لو فيه رقم أحدث وأكبر أو قده، القديم مالوش لازمة". الجملة دي وحجة الـ O(n) أهم من الكود نفسه.

فيه مكان تاني الـ queue فيه هو البطل، وهتقابله كتير جدًا: الـ BFS.

لمحة: الـ queue هو قلب الـ BFS

أهم استخدام للـ queue في الانترفيوهات هو BFS (Breadth-First Search). هتدرسه بالتفصيل في فصل الـ graphs، بس خد الفكرة من دلوقتي.

الـ graph ببساطة: nodes (دواير، زي محطات المترو) و edges (خطوط بتوصل بينهم). بنمثّله بـ adjacency list: graph[node] هي array الجيران، فـ graph[2] = [0, 3, 4] معناها إن 2 متوصلة بـ 0 و 3 و 4. السؤال: لو بدأنا من 0، كل node بعيدة كام edge على الأقل؟ الـ BFS بيزور الأقرب الأول، مستوى مستوى، والـ queue هو اللي بيضمن الترتيب ده: اللي اكتشفناه الأول بيخرج الأول.

تشبيه إشاعة في العيلة. إنت قلتها لأقرب ناس ليك (المستوى 1)، وكل واحد فيهم قالها لقرايبه اللي لسه ما سمعوهاش (المستوى 2). اللي سمعها الأول بيبلّغها الأول، واللي سمعها قبل كده ما بيتقالهاش تاني.
  1. الـ dist بتعمل حاجتين: visited، والمسافة. الـ start بعده 0.
  2. head < queue.length مش queue.length > 0. الـ array عمرها ما بتقصر مع الـ head index، فالشرط التاني مش هيبقى false أبدًا.
  3. بنطلّع الأقدم، وده اللي بيخلّي الترتيب مستوى مستوى: كل المستوى 1 دخل قبل أي حد من المستوى 2.
  4. بنعلّم visited وقت الدخول، مش الخروج. لو استنينا للخروج، نفس الـ node ممكن تدخل الـ queue أكتر من مرة من جيران مختلفين.
  5. المسافة = مسافة اللي اكتشفها + 1، وده أقصر طريق لأن أول وصول بيبقى من أقرب مستوى.

ترتيب الخروج: 0، وبعدين 1 و 2 (المستوى 1)، وبعدين 3 و 4، وبعدين 5. لو بدّلت الـ queue بـ stack هتغطس في طريق واحد للآخر قبل ما ترجع، وده DFS، وما بيدّيش أقصر مسافة. هتشوف الاتنين في الـ trees و الـ graphs، و BFS على grid في Graphs على Grid.

قبل ما تتمرن: إيه الغلطات اللي بتوقّع الناس في كل اللي فات؟

غلطات مشهورة

1. shift() جوه loop على queue كبير

على graph فيه 10⁵ node ده ممكن ياخد ثواني ويطلع TLE. الصح: let head = 0 و queue[head++]، واتعوّد عليه من الأول حتى في المسائل الصغيرة.

2. head index مع شرط queue.length

الشرط لازم head < queue.length، والحجم queue.length - head. أي مكان كاتب فيه length لوحدها، اسأل: "طب والميتين؟".

3. الـ % مع رقم سالب

في JS (و C++ و Java) نتيجة الـ % بتاخد إشارة الرقم الشمال، لكن في Python -1 % 4 بتطلع 3، فلو جاي من Python خلي بالك. زوّد cap قبل الـ % في أي طرح.

4. نسيت tail = null في الـ linked queue

أول enqueue بعدها هيشوف tail !== null ويربط في الـ node الميتة، والـ head يفضل null، والعنصر يضيع. الحل: if (this.head === null) this.tail = null;.

5. تصب الـ inStack كل مرة في Queue using Stacks

الـ 2 كان فوق outStack مستني دوره، وجه الـ 3 اتحط فوقه. الصب يحصل بس لما outStack يبقى فاضي.

6. الـ expire بـ < بدل <= في Sliding Window Maximum

اكتب الـ window على ورقة قبل الشرط: [i - k + 1, i]. أول index برا هو i - k، فالشرط dq[head] <= i - k.

يلا نتأكد إن الأفكار دي ثبتت.

اختبر نفسك

queue فيه n عنصر في array، وطلّعتهم كلهم واحد واحد بـ shift(). التكلفة الكلية كام؟

  • O(n)
  • O(n log n)
  • O(n²)
  • O(1)

كل shift بتنقل كل اللي فاضل: (n - 1) + (n - 2) + ... + 1 = حوالي n²/2. بالـ head index نفس الشغل O(n).

queue بـ head index: items.length = 9 و head = 4. الـ queue فيه كام عنصر؟

  • 9
  • 4
  • 5
  • 13

الـ indices من 0 لـ 3 خرجوا. الأحياء من 4 لـ 8: دول 5 = 9 - 4.

circular queue حجمه cap = 5، و head = 3 و size = 4. الـ enqueue الجاي هيكتب في أنهي index؟

  • 7
  • 2
  • 0
  • مش هينفع، الـ queue مليان

(3 + 4) % 5 = 2. العناصر في 3، 4، 0، 1، فأول خانة فاضية 2. ومش مليان لأن 4 أقل من 5.

في Queue using Stacks، عملت n push وبعدين n pop. أنهي جملة صح؟

  • كل pop بتاخد O(n)، فالمجموع O(n²)
  • أول pop بتاخد O(n) والباقي O(1)، فالمجموع O(n)، يعني amortized O(1) لكل عملية
  • كل pop بتاخد O(1) بالظبط
  • المجموع O(n log n)

أول pop بتصب الـ n عنصر مرة واحدة، وبعدها كلهم في outStack بالترتيب الصح. وكل عنصر اتصب مرة واحدة بس.

في Sliding Window Maximum، الـ deque من الأول للآخر شكله إيه دايمًا؟

  • القيم طالعة
  • الـ indices طالعة والقيم نازلة
  • الـ indices نازلة والقيم طالعة
  • مالوش ترتيب، المهم إن الـ max فيه

الـ indices طالعة لأننا بنضيف في الآخر بالترتيب، والقيم نازلة لأننا بنرمي من الآخر أي حد أصغر من الجديد أو قده. عشان كده الـ front هو الأكبر.

في الـ BFS، ليه بنعلّم الـ node إنها visited وقت ما تدخل الـ queue، مش وقت ما تخرج؟

  • عشان الكود يبقى أقصر
  • عشان نفس الـ node ما تدخلش الـ queue أكتر من مرة من جيران مختلفين
  • عشان الـ queue ما يبقاش فاضي
  • مش فارقة خالص

في الـ animation، node 3 جارة لـ 1 و 2. لو بنعلّم وقت الخروج، 1 و 2 الاتنين هيضيفوها قبل ما تخرج، فتدخل مرتين. في graphs كبيرة ده بيضاعف الشغل جامد.

تمرين: فكّر قبل ما تفتح

Time Needed to Buy Tickets

easyLeetCode 2073

ناس في طابور تذاكر، والشخص i عايز tickets[i] تذكرة. كل ثانية، اللي في الأول بياخد تذكرة واحدة. لو لسه عايز يرجع يقف في آخر الطابور، ولو خلص يمشي. الشخص اللي عند index k هيخلص بعد كام ثانية؟

tickets = [3, 1, 4, 2], k = 2 → 10
تلميح 1

ده queue بالظبط: اعمل queue فيه الـ indices، وكل لفة طلّع واحد، نقّص تذكرته، وزوّد الوقت، ولو لسه محتاج رجّعه الآخر. وقف لما k يخلص. ده O(مجموع التذاكر).

تلميح 2

من غير simulation: k هيلف tickets[k] لفة. كل واحد قبله (أو هو نفسه) هياخد min(tickets[i], tickets[k])، وكل واحد بعده min(tickets[i], tickets[k] - 1)، لأن في آخر لفة k بيخلص قبل ما دورهم ييجي.

الحل

في المثال: 3 + 1 + 4 + min(2, 3) = 10. لاحظ i <= k مش i < k: الشخص k نفسه بيتحسب مع اللي قبله. والـ while (true) مضمون تخلص لأن تذاكر k محدودة.

لو عدّيت الأسئلة دي، إنت جاهز للمسائل.

اتمرن على LeetCode بالترتيب

حلها بالترتيب ده، كل مسألة بتضيف فكرة واحدة جديدة، والتقدّم بيتحفظ. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للجزء بتاعها هنا وبعدين حاول تاني من غير ما تبص.

وفي الآخر، الفصل كله في صفحة واحدة.

الخلاصة

في جملة واحدة الـ queue معناه "الأقدم يطلع الأول"، وفي JS بتعمله بـ array و head بيتحرك بدل shift. ولما تحتاج تشيل من الناحيتين (زي الـ max في window)، استخدم deque فيه indices وارمي أي عنصر بقى مالوش لازمة.
السؤالالإجابة
shift() ولا head index؟head index دايمًا في الـ loops. shift و unshift O(n).
Queue ولا stack؟الأقدم يتعالج الأول: queue. الأحدث الأول: stack.
الحجم كام؟length - head، مش length.
إمتى circular buffer؟لما الحجم الأقصى معروف، أو المسألة بتقول design circular.
الـ % مع الطرح؟زوّد cap الأول: (i - 1 + cap) % cap.
إمتى deque؟لما تحتاج تشيل من الناحيتين، وأشهرها max أو min لكل window.
Monotonic deque ولا heap؟window ثابتة بتتحرك: deque في O(n). أصغر حاجة من كل اللي اتضاف: heap في O(log n) للعملية.
Complexity؟عمليات الـ queue O(1) أو amortized O(1). الـ monotonic deque O(n) لأن كل index يدخل مرة ويخرج مرة.

الفصل الجاي: Linked List. الـ LinkedQueue اللي عملناها كانت أول linked list ليك: nodes و next و head و tail، وغلطة الـ tail اللي ما رجعش null. هناك هنفصّلها: نعكسها، وندمج اتنين، و fast & slow، والـ dummy node. والـ queue نفسه هيرجعلك في الـ trees (level order) و الـ graphs (BFS)، وساعتها القالب الأول ده هيبقى أكتر 5 سطور بتكتبهم.