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.
هتطلع من الفصل ده وإنت عارف
- تعرف من كلام المسألة إنها 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؟
إزاي تعرفه من المسألة
أول اتنين في السطر التاني دول stack، لأن الأحدث هو اللي بيتعالج الأول. والتالت heap، لأنك عايز أصغر عنصر من كل اللي اتضاف، مش من آخر k بس.
| النوع | بيعمل إيه | بنعمله في JS إزاي | أشهر مسائل |
|---|---|---|---|
| Queue عادي | تضيف في الآخر وتشيل من الأول | array + head index | Number of Recent Calls، Time Needed to Buy Tickets |
| Circular queue | حجم ثابت، بيعيد استخدام الأماكن الفاضية | array + head + size + % | Design Circular Queue |
| Deque | تضيف وتشيل من الناحيتين | circular buffer، أو array + head و tail | Design Circular Deque |
| Monotonic deque | max أو min لكل window | deque فيه indices قيمهم مترتبة | Sliding Window Maximum |
| BFS queue | تلف على graph مستوى مستوى | array + head | Rotting 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 كده، والكود ده بيعمل نفس اللي بيحصل جوه:
- بنحفظ أول عنصر قبل ما الـ loop تكتب فوقه.
- الـ
kبيبدأ من 1 عشان بننقلarr[k]لـarr[k - 1]، ولو بدأ من 0 هنكتب فيarr[-1]. الـ loop بتلف n - 1 مرة، وده الـ O(n). - مفيش طريقة تخلّي التاني يبقى
arr[0]من غير ما الكل يتحرك، لأن الـ index لازم يفضل هو مكان الخانة. - بعد النقل آخر عنصر بقى موجود مرتين، فبنقصّر الـ 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²).
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++.
head.
- ليه
head = 0؟ أولpushهيروح index 0 وده هيبقى الـ front. كل اللي قبلheadخرج خلاص، بس لسه في الـ array. pushبتضيف في الآخر من غير ما تحرّك حاجة: amortized O(1)، لأن الـ array ساعات بتكبر وتتنسخ بس ده نادر.- الـ early return ده مش عشان error. لو الـ queue فاضي وعملنا
head++، الـheadهيعدّيlengthوsize()تطلع سالبة. وundefinedهو نفس اللي[].shift()بترجّعه. - ده الحل كله: سطر O(1) بدل n - 1 نقلة.
- تنضيف optional. من غيره queue خدم مليون عنصر هيفضل شايل مليون خانة. بننضّف لما الميتين يبقوا النص أو أكتر، فالأحياء اللي الـ
sliceبتنسخهم أقل من عدد اللي خرجوا من آخر تنضيف، فالمتوسط يفضل O(1). في LeetCode تقدر تشيل السطور دي. - الحجم =
length - head، مشlength. دي أشهر غلطة مع الـ head index، لأن الـlengthفيها الميتين.
الخانات الباهتة خرجت من الـ queue بس لسه في الـ array. ولاحظ إن ولا عنصر بيتحرك مع الـ dequeue:
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)، ومفيش خانات ميتة.
- الـ
nextبيبدأnullلأن أي node جديدة بتتحط في الآخر، فمفيش حد وراها. - ليه محتاجين
tail؟ من غيره، عشان تضيف في الآخر لازم تمشي من الـheadلآخر node، وده O(n). - الـ edge case بتاع الـ queue الفاضي: مفيش
tailنربط بعده، فالـ node الجديدة هي الأول والآخر. من غيره الـheadهيفضلnullللأبد. - الـ queue مش فاضي: آخر node بقت تشاور على الجديدة، والجديدة بقت هي الآخر.
- الـ front بقى اللي بعده. الـ node القديمة محدش بيشاور عليها، فالـ garbage collector هيشيلها.
- السطر اللي الناس بتنساه. لو شلنا آخر عنصر،
headبقىnullبسtailلسه على node ميتة. الـ enqueue الجاي هيربط فيها، والعنصر يضيع.
| الطريقة | enqueue | dequeue | الـ memory | تستخدمها إمتى |
|---|---|---|---|---|
array + shift | O(1) | O(n) | قد العناصر | queue صغير جدًا بس. ما تعتمدش عليها. |
array + head | O(1)* | O(1) | بتشيل الميتين لحد التنضيف | أغلب المسائل، وخصوصًا BFS. الأسرع في الكتابة. |
| linked list | O(1) | O(1) | قد العناصر + pointer لكل عنصر | queue عايش كتير وبيخدم عناصر كتير. |
| circular buffer | O(1) | O(1) | ثابتة: k خانة | لما الحجم الأقصى معروف (مثال 3). |
* amortized: في المتوسط، مش كل مرة لوحدها.
كده عندك queue O(1). يلا نستخدمه في أول مسألة.
مثال محلول 1: Number of Recent Calls
أول مثال بيطبّق القالب زي ما هو. الجديد هنا إن الـ queue بيمثّل window بالزمن، واللي بيخرج منها مش بيرجع تاني.
اعمل class اسمها RecentCounter فيها ping(t). كل نداء معناه request وصل في الوقت t بالـ ms. رجّع عدد الـ requests اللي في الفترة [t - 3000, t] بالطرفين. الـ t مضمون إنه بيزيد كل مرة.
نفكّر فيها مع بعض
- افهم المطلوب: window زمنية طولها 3000 بتتحرك لقدام مع كل
ping، والطرفين داخلين. - Brute force: نحفظ كل الـ pings ونعدّ اللي جوه الفترة كل مرة. O(n) لكل
ping، يعني O(n²) في الآخر. - الـ key insight: الـ
tبيزيد دايمًا، فالحدt - 3000بيزيد. يعني ping بقى أقدم من الحد النهارده هيفضل أقدم منه للأبد: اللي يخرج ما بيرجعش. - واللي بيخرج دايمًا الأقدم: الـ pings داخلة بالترتيب، فنضيف في الآخر ونشيل من الأول. ده queue، والإجابة هي حجمه.
- Edge cases: أول
ping، و ping عندt - 3000بالظبط (لازم يتحسب)، وفجوة كبيرة بتخرّج كل اللي قبلها.
- نفس القالب: array و
head. الـtimessorted لوحدها لأن الـtبيزيد. - بنضيف الجديد قبل الـ while، وده اللي بيضمن إن الـ while تقف (السطر الجاي).
- ليه
<مش<=؟ الفترة بالطرفين، فالـ ping اللي عندt - 3000بالظبط لازم يفضل. ومفيشhead < lengthفي الشرط لأن آخر عنصر هوt، وعمره ما هيبقى أقل منt - 3000. head++بدلshift(): O(1).- الإجابة هي حجم الـ 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).
اعمل queue (push في الآخر، pop و peek من الأول، و empty) بس مسموحلك بعمليات الـ stack بس: تحط فوق، تشيل من فوق، تبص على اللي فوق، الحجم. يعني في JS: push و pop و arr[arr.length - 1] و length.
نفكّر فيها مع بعض
- المشكلة: الـ stack بيطلّع الأحدث، والـ queue لازم يطلّع الأقدم، والأقدم مدفون تحت.
- الملاحظة: لو صبّيت stack في stack تاني، الترتيب بيتقلب، والأقدم بيبقى على الوش.
- Brute force: مع كل
popنصب، نشيل، ونصب تاني نرجّع. شغال، بس كلpopبقى O(n). - الحل الـ lazy:
inStackللجديد وoutStackللشيل، وما بنصبّش إلا لماoutStackيفضى. ليه صح؟ الـ invariant إن أي عنصر فيoutStackأقدم من أي عنصر فيinStack، فاللي فوقoutStackهو الأقدم في الـ queue كله. - Edge cases:
peekقبل أيpop، وpushفي النص بين الـ pops، وتفضّي الاتنين لحد ماemptyتبقى true.
- الـ queue كله =
outStackمن فوق لتحت، وبعدهinStackمن تحت لفوق. - الـ push O(1) دايمًا، ومش بيلمس
outStack. popبتناديpeekعشان منطق الصب يتكتب مرة واحدة بس.- أهم سطر: بنصب بس لو
outStackفاضي. لو صبّينا وهو فيه حاجة، الجديد يقعد فوق القديم والترتيب يبوظ. - أقدم عنصر كان تحت خالص في
inStack، فبيتنقل في الآخر ويقعد فوق خالص فيoutStack. - لازم الاتنين يبقوا فاضيين. ممكن
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() | 7 | peek بتصب حتى لو مفيش pop قبلها |
| push(1), push(2), pop(), push(3), pop() | 1, 2 | push في النص: الـ 3 لازم يستنى ورا الـ 2 |
| push(1), pop(), empty() | 1, true | الاتنين فاضيين |
| push(1), push(2), pop(), empty() | 1, false | inStack فاضي بس outStack فيه 2 |
التعقيد: push و empty O(1) دايمًا. pop و peek O(n) في الـ worst case لعملية واحدة، و O(1) amortized. والـ memory O(n).
الـ two stacks والـ head index الاتنين amortized. طب لو الحجم ثابت وعايز كل عملية O(1) بجد؟
مثال محلول 3: Design Circular Queue
الجديد هنا الـ wrap-around: لما توصل لآخر خانة، ترجع تستخدم أول خانة بالـ %، فمفيش نسخ خالص ولا amortized.
اعمل queue حجمه الأقصى k: enQueue(value) و deQueue() بيرجّعوا true لو نجحوا و false لو لأ، و Front() و Rear() بيرجّعوا أول وآخر عنصر أو -1 لو فاضي، و isEmpty() و isFull(). الأماكن اللي بتفضى من الأول لازم تتستخدم تاني.
نفكّر فيها مع بعض
- ليه الـ head index لوحده مش كفاية؟ في array ثابتة بحجم 4: بعد 4 enqueue و 2 dequeue الآخر وصل لآخر خانة، فمفيش مكان، مع إن أول خانتين فاضيين.
- الـ key insight: نعتبر الـ array دايرة: بعد آخر خانة ييجي خانة 0. والـ
%بيعمل كده:(3 + 1) % 4 = 0. - نمسك إيه؟
headوsize. مكان الآخر(head + size - 1) % k، ومكان الإضافة الجاية(head + size) % k. - ليه
sizeمشtail؟ لو مسكناheadوtailبس، الفاضي والمليان الاتنينhead === tail. الـsizeبيفرّق بينهم من غير أي لف. - Edge cases:
k = 1، إضافة في queue مليان، شيل من فاضي،FrontوRearعلى فاضي، والـ wrap-around نفسه.
(11 + 3) % 12 = 2. الـ array الدايرية زي الساعة بالظبط.
- array بحجم ثابت عمرها ما بتكبر، والـ state كلها في رقمين: الأول فين، وكام واحد جوه.
- مليان؟ المسألة عايزة
false، مش error ومش نكتب فوق حاجة. - ليه
head + size؟ العناصر فيheadلـhead + size - 1، فأول خانة فاضية بعدهمhead + size. والـ% capبيلف بيها للأول لو عدّت الآخر. - ممكن الخانة فيها قيمة قديمة خرجت، عادي، بنكتب فوقها.
- ده الـ dequeue كله: الـ head يتقدم one step ويلف لـ 0 بعد آخر خانة. مش بنمسح القيمة، هي بقت برا الـ range.
- لازم نتشيك على الفاضي الأول، لأن
data[head]ممكن فيها قيمة قديمة خرجت، فهترجّع رقم غلط بدل-1. - هنا التشيك أهم: لو
size = 0وhead = 0، الحساب-1 % cap، وفي JS ده-1مشcap - 1. هنرجع للنقطة دي في الـ deque. - الفاضي والمليان من
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 empty | false | من غير التشيك 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 |
|---|---|---|---|
| إضافة في الآخر | push | O(1) | O(1) |
| شيل من الآخر | pop | O(1) | O(1) |
| إضافة في الأول | unshift | O(n) | O(1) |
| شيل من الأول | shift | O(n) | O(1) |
الـ array نصها deque كويس (الآخر) ونصها وحش (الأول). نفس الـ circular buffer بيحلها: الإضافة في الأول معناها إن الـ head يرجع خطوة لورا، ولو كان عند 0 يلف لآخر خانة. دي Design Circular Deque:
- نفس state الـ circular queue بالظبط:
headوsize. - أهم سطر. لو
head = 0الخانة اللي قبله هيcap - 1، بس(0 - 1) % 4في JS بتطلع-1. الـ+ capبيخلّي الرقم موجب دايمًا، ومش بيغيّر الباقي في الحالات العادية:(5 - 1 + 8) % 8 = 4. - بنحرّك الـ head الأول وبعدين نكتب، لأن الـ head القديم فيه الـ front الحالي.
- الشيل من الأول: الرقم موجب دايمًا، فمش محتاجين
+ cap. - الآخر مكانه
head + size - 1، فلماsizeتقل الآخر بقى اللي قبله لوحده.
head و tail: الشيل من الأول head++، والشيل من الآخر tail--، والإضافة dq[tail++] = i. من غير % ومن غير shift.
طب إيه أشهر مسألة محتاجة تشيل من الناحيتين؟ الـ max لكل window.
مثال محلول 4: Sliding Window Maximum
الجديد هنا إن الـ deque مش بس بيشيل من الناحيتين، ده مترتب (monotonic): بنرمي منه أي عنصر بقى مالوش لازمة. نفس روح الـ monotonic stack من الفصل اللي فات، بس مع window بتخرّج عناصر من الأول.
عندك array nums ورقم k. فيه window طولها k بتبدأ من أول الـ array وبتتحرك خانة خانة لحد الآخر. رجّع أكبر رقم في كل window.
نفكّر فيها مع بعض
- Brute force: لكل window نلف على الـ k عنصر. O(n·k)، ومع n = 10⁵ و k = 5·10⁴ ده 2.5 مليار عملية: TLE.
- ليه الـ sliding window العادي مش كفاية؟ المجموع لما عنصر يخرج بتطرحه وخلاص. لكن الـ max لو خرج، مش هتعرف مين بعده من غير ما تلف تاني.
- حل متوسط: heap فيه العناصر، وتشيل اللي خرج لما يطلع فوق. O(n log n).
- الـ key insight: لو
j < iوnums[j] <= nums[i]، يبقىjعمره ما هيبقى max تاني: أي window جاية فيهاjفيهاiكمان، وjهيخرج قبله. فنرميه. - النتيجة: اللي بيفضل indices طالعة وقيمهم نازلة، فالـ max هو الـ front. بنشيل من الآخر (اللي بقوا مالهمش لازمة) ومن الأول (الـ max لما يخرج من الـ window)، عشان كده deque.
- بنخزّن indices مش قيم: عشان نعرف الـ front خرج من الـ window ولا لأ، محتاجين مكانه، وخصوصًا مع المكررات.
- ليه array بطول n؟ كل index بيدخل مرة واحدة، فالـ
tailعمره ما هيعدّي n. ومش بنستخدمshiftلأنها O(k) والحل يبقى O(n·k). - الـ deque هو
dq[head .. tail - 1]، والـtailمعناه "الخانة الفاضية الجاية" زيlength. - ليه
<=؟ الـ window هي[i - k + 1, i]، فأول index برا هوi - k. وifمشwhileلأن الـ window بتتحرك one step فبيخرج index واحد بالكتير، وبنبص على الـ front بس لأنه الأقدم. - قلب الحل: اللي في الآخر أصغر من أو قد الجديد مالوش لازمة، فنرميه. الـ
<=بترمي القديم المساوي لأنه هيخرج الأول، والـ<صح برضه بس بتسيب مكررات. - نضيف
iفي الآخر (post-increment: نكتب فيdq[tail]وبعدينtailيزيد). الترتيب لسه نازل لأن كل اللي قدامه أكبر منه. - ليه
i >= k - 1؟ أول window كاملة بتخلص عند indexk - 1. لو كتبتi > k - 1هتضيّع أول window، ده بالظبط الـ off-by-one بتاع<و<=.
الخانات الزرقا هي الـ window، واللي حواليها خط متقطع موجودة في الـ deque. الـ deque تحت مكتوب فيه index:value:
| 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). الفرق إن القديم المساوي بيفضل قاعد من غير لازمة.
فيه مكان تاني الـ 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 هو اللي بيضمن الترتيب ده: اللي اكتشفناه الأول بيخرج الأول.
- الـ
distبتعمل حاجتين: visited، والمسافة. الـ start بعده 0. head < queue.lengthمشqueue.length > 0. الـ array عمرها ما بتقصر مع الـ head index، فالشرط التاني مش هيبقى false أبدًا.- بنطلّع الأقدم، وده اللي بيخلّي الترتيب مستوى مستوى: كل المستوى 1 دخل قبل أي حد من المستوى 2.
- بنعلّم visited وقت الدخول، مش الخروج. لو استنينا للخروج، نفس الـ node ممكن تدخل الـ queue أكتر من مرة من جيران مختلفين.
- المسافة = مسافة اللي اكتشفها + 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 كبيرة ده بيضاعف الشغل جامد.
تمرين: فكّر قبل ما تفتح
ناس في طابور تذاكر، والشخص i عايز tickets[i] تذكرة. كل ثانية، اللي في الأول بياخد تذكرة واحدة. لو لسه عايز يرجع يقف في آخر الطابور، ولو خلص يمشي. الشخص اللي عند index k هيخلص بعد كام ثانية؟
تلميح 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 دقيقة على مسألة، ارجع للجزء بتاعها هنا وبعدين حاول تاني من غير ما تبص.
- Number of Recent Callsالمثال المحلول 1. اكتبه بالـ head index من دماغك.
- Implement Queue using Stacksالمثال المحلول 2. اشرح الـ amortized لنفسك بصوت عالي.
- Implement Stack using Queuesالعكس: بعد كل push لف الـ queue عشان الجديد يبقى في الأول.
- Time Needed to Buy Ticketsالتمرين اللي فوق: simulation بـ queue، وبعدين O(n).
- Number of Students Unable to Eat Lunchsimulation تانية: اعرف إمتى الطابور "اتقفل" ومحدش هيتحرك تاني.
- Design Circular Queueالمثال المحلول 3:
headوsizeو%. - Design Circular Dequeنفسها من الناحيتين. الاختبار الحقيقي هو
(head - 1 + cap) % cap. - Reveal Cards In Increasing Ordersimulate العملية على queue فيه الـ indices مش القيم.
- Dota2 Senateاتنين queues بيتنافسوا، واللي يكسب يرجع الآخر بـ index أكبر.
- Sliding Window Maximumالمثال المحلول 4. اكتب الـ monotonic deque من غير ما تبص.
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limitاتنين monotonic deques (max و min) جوه sliding window.
- Rotting Orangesجسر للـ graphs: BFS على grid من كذا نقطة بداية مع بعض.
- Shortest Subarray with Sum at Least Kاختياري: monotonic deque على الـ prefix sums.
وفي الآخر، الفصل كله في صفحة واحدة.
الخلاصة
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 سطور بتكتبهم.