طابور ذو طرفين

مدخل

الناتج

كطابور

كمجموعة

طابور ذو طرفين كأنبوب

في علوم الحاسوب ، يُعدّ الطابور ذو الطرفين (يُختصر إلى deque - / dɛk / DEK ) نوع بيانات مجردًا يعمل كحاوية ، مع تقييد الوصول إلى العناصر المخزنة فيه. وباعتباره تعميمًا لكل من المكدس والطابور ، قد يؤدي الطابور ذو الطرفين وظائف مشابهة كمخزن مؤقت للبيانات : إذ يُمكن استخدامه كحاوية ( طابور)، أو للتراجع (مكدس). ومع ذلك، فهو يوفر مرونة أكبر في إدارة ترتيب العناصر، وتعتمد بعض الخوارزميات على وظائفه.

وصف

يُعرَض الطابور ذو الطرفين غالبًا على أنه طابور مُعمَّم، ومن هنا جاء اسمه. وهو طابور "يسمح بالإضافة والحذف من كلا الطرفين". يُوصَف الطابور ذو الطرفين أيضًا بأنه تعميم لبنية بيانات المكدس المجردة، أي "مكدسان متصلان عند القاعدة"، مع عنصر سفلي مشترك، أو كمزيج من المكدس والطابور. ^{[ 1 ]}^{[ أ ]}^{[ ب ]} وبالمقابل، يُعد كل من الطابور والمكدس شكلين مُقيَّدين من الطابور ذي الطرفين.

تُستخدم تشبيهات مختلفة مع أشياء من العالم الحقيقي لوصف نظام الطابور المزدوج (deque). يُقارن هذا النظام بـ"مجموعة أوراق اللعب" التي تشترك معها في بعض الخصائص والنطق. ^{[ 3 ]}^{[ 4 ]}^{: 239}^{[ 5 ]} كما يُشبه نظام الطابور المزدوج بـ"قلادة ذات خرز يمكن إضافتها أو إزالتها من أي من طرفيها". ومثل الطابور العادي، يُصوَّر نظام الطابور المزدوج على أنه مجموعة من العناصر المصطفة في أنبوب مفتوح من كلا الطرفين؛ ولكن على عكس الطابور العادي، يمكن للعناصر التحرك في كلا الاتجاهين داخل الأنبوب. ويركز "نموذج السكة الحديدية" الذي قدمه كنوت (نسبةً إلى "ساحة تحويل دايجسترا" ) ^{[ 4 ]}^{: 240} على التشابه مع الطابور العادي، حيث يحتوي على مدخل واحد ومخرج واحد، ومفاتيح لاختيار جانب الطابور المزدوج المراد الوصول إليه. ^{[ 6 ]}^{: 175}

تُجرى العمليات الرئيسية على قائمة الانتظار المزدوجة (deque) على جانبيها (أو طرفيها ): إضافة عنصر إلى المجموعة ( enqueue )، وإزالة عنصر (dequeue )، وقراءة عنصر ( peek ). في أي لحظة، لا يمكن الوصول إلا إلى عنصرين فقط، من أي من جانبي قائمة الانتظار المزدوجة، بناءً على تاريخها. العنصر المُحدد على أحد الجانبين هو إما أحدث عنصر أُضيف إلى هذا الجانب ( سلوك LIFO )، أو - في حال عدم وجود عنصر مُضاف - أقدم عنصر أُضيف إلى الجانب الآخر ( سلوك FIFO ). تمنح سياسة الخدمة هذه البنية مرونةً وتعدد استخدامات أكبر، ولكنها تجعل فهمها واستخدامها أكثر صعوبة. ^{[ ج ]}

يمكن وصف العمليات الست الرئيسية على قائمة الانتظار المزدوجة (deque) بطريقتين، استنادًا إلى عمليات قائمة الانتظار (أو المكدس): إما بتكرارها على طرفي البنية (مثلاً add_left، add_right، ، إلخ)، أو بتعميمها باستخدام مُعامل يُشير إلى موقع تنفيذ العملية (مثلاً add(left,...)، add(right,...)، ، إلخ). لكل طريقة مزاياها: فالأولى تسمح بتعدد العمليات ولكنها تتطلب أسماءً مختلفة على كل طرف، بينما تُبسط الثانية الواجهة بتقليل عدد العمليات إلى النصف وتسمح بالاستفادة من تناظر البنية. ^{[ 7 ]} فيما يلي، سنعتمد الخيار الثاني لتجنب التكرار غير الضروري.

يحتوي نظام deque على نوعين فرعيين آخرين محتملين (الأشكال الأكثر تقييدًا غير مجدية):

الطابور المزدوج المقيد بالإدخال هو طابور يمكن فيه الحذف من أي من طرفيه، بينما لا يمكن الإضافة إلا من طرف واحد. وهو طابور ذو مخرج خلفي، أو مكدس ذو مخرج سفلي.
الطابور المزدوج ذو الإخراج المقيد هو طابور يمكن إدخال عناصر إليه من أي من طرفيه، ولكن لا يمكن حذفها إلا من طرف واحد. وهو طابور ذو مدخل أمامي، أو مكدس ذو مدخل سفلي.

على الرغم من محدوديتها، فإن لهذه الأنواع الفرعية العديد من التطبيقات ، وقد تكون بعض تطبيقاتها أبسط.

*مثال على العمليات على قائمة انتظار مزدوجة* من قائمة انتظار مزدوجة فارغة
العمليات
أضف (يسار، `DE`)	`DE`
أضف (يمين، `CK`)	`DE`	`CK`
إزالة (يسار)		`CK`
أضف (يسار، `STA`)	`STA`	`CK`
أضف (يمين، `QUE`)	`STA`	`CK`	`QUE`
أضف (يمين، `UE`)	`STA`	`CK`	`QUE`	`UE`
إزالة (يسار)		`CK`	`QUE`	`UE`
إزالة (يسار)			`QUE`	`UE`
أضف (يسار، `DE`)		`DE`	`QUE`	`UE`
إزالة (يمين)		`DE`	`QUE`

بعد كنوت، ^{[ 4 ]} غالبًا ما تُوصف هذه البنى بأنها أشكال مختلفة من القوائم أو المتتاليات الخطية المقيدة . فهي تحافظ على العناصر الموجودة فيها بترتيب معين، بينما تسمح بالوصول إلى بعضها فقط: العنصر الأول و/أو الأخير في المتتالية. مع ذلك، يعترض مؤلفون آخرون على أنها "تخفي ديناميكيتها الداخلية عن المستخدم" ^[²^]^:¹³⁹ ، وأن التطبيقات الشائعة فقط هي الخطية. ويعتبرون أن بنى البيانات ذات الوصول المقيد هذه إما:

شبه مُهيكلة : فهي تحتوي على "عنصر خاص أو مُحدد ولكن لا توجد علاقة منطقية بينها وبين بقية العناصر"، و"العملية التي تحذف عنصرًا لا تأخذ أي عنصر كمعامل"؛ ^{[ 8 ]}^{: 13، 189}
أو هياكل النقاط "لأن هناك نقطتين فقط من قائمة الانتظار للعالم الخارجي" ^{[ 2 ]}^{: 129} : المكدس هو هيكل نقطة واحدة، بينما قائمة الانتظار وقائمة الانتظار المزدوجة هي هياكل نقطتين.

على سبيل المثال، يمكن تنفيذ قائمة الانتظار المزدوجة باستخدام كومة دنيا-قصوى ، أو باستخدام مجموعة : قبل إدخال أي عنصر، يُوسَم بعدد صحيح يُستخدم كقيمة له في الكومة، ويعتمد ذلك على تاريخ الحاوية. ^{[ 8 ]}^{: A1} العناصر المخزنة في الكومة غير مرتبة، وتعتمد مواقعها على الحالة الداخلية للبنية. ومن هياكل الوصول المقيد الشائعة الأخرى قائمة الانتظار ذات الأولوية ، وهي ليست بنية خطية.

يمكن تعميم قائمة الانتظار المزدوجة (deque) بإضافة بعض العمليات: فقائمة الانتظار المزدوجة ذات الترتيب الهرمي، أو قائمة الانتظار المزدوجة ذات الترتيب الهرمي (mindeque) ، تسمح بعملية البحث عن أصغر عنصر . كما يُمكن إجراء عملية ربط سريعة أو حتى مثالية. ^{[ 9 ]}^{: 276}^{[ 10 ]}^{[ 11 ]}

يرى بعض المؤلفين أن بنية الطابور المزدوج (deque) قليلة الفائدة، وأقل فائدة من أشكالها المقيدة، وخاصة المكدس والطابور. ^{[ 1 ]}^{[ 2 ]}^{[ 9 ]}^{[ د ]}

↑ «لماذا لا يُطلق عليه اسم "الطبق المزدوج"؟ إنه لغز، لأن هذا الوصف دقيق على الأقل»،^{[ 2 ]}^{: 131}
↑ يمكن اعتبار قائمة الانتظار المزدوجة "إما قائمة انتظار فائقة أو مكدس فائق".^{[ 1 ]}
↑ «إذا أُدخلت عقدتان من أحد طرفي الشبكة وأُزيلتا من الطرف الآخر، فإنهما ستخرجان بترتيب الطابور. وإذا أُزيلتا من طرف الإدخال، فإنهما ستخرجان بترتيب المكدس. أما إذا أُزيلتا من طرفين متقابلين، فإن ترتيب خروجهما يكون عشوائيًا.»^{[ 2 ]}^{: 131}
↑ "هيكل بيانات يبحث عن تطبيق!"، كما ذكر روي إس. إلزاي في عام 1989.^{[ 12 ]}

مواصفة

يُعتبر الطابور المزدوج هنا غير محدود: إذ يمكن أن يحتوي على عدد غير محدود (وغير مُحدد) من العناصر. من الممكن وجود طابور مزدوج محدود، ويتطلب ذلك مواصفات مختلفة قليلاً، ولكن عند حدوث تجاوز، يعتمد السلوك على التنفيذ: قيمة خطأ، استثناء، حذف، إلخ.

ليكن لدينا قائمة انتظار مزدوجة $d \in D$ ، وعنصر $x \in X$ ، وجانب (نهاية) $e \in E = {يسار، يمين}$ حيث $\neg يسار = يمين$

العمليات الرئيسية: مع $D * = D \ {Λ}$

$أضف : هـ \times س \times د \to د *$
$إزالة : هـ \times د * \to د$
$اقرأ : هـ \times د * \to س$
$فارغ : D \to {⊤, ⊥}$

باعتبارها بنية خطية، يمكن تحديد deque من حيث ربط التسلسلات (يشار إليه بـ " $~$ ") والتسلسلات الفردية (يشار إليها بـ " $< ... >$ ").

متتالية فارغة: $Λ = < >$
$اقرأ (يسار، د) = س \Leftrightarrow \exists د' | د = < س > ~ د'$
$اقرأ (يمين، د) = س \Leftrightarrow \exists د' | د = د' ~ < س >$
$أضف (يسار، س ، د) = < س > ~ د$
$أضف (يمين، س ، د) = د ~ < س >$
$remove (left, d) = d' \Leftrightarrow \exists x | d = <x> ~ d'$
$إزالة (يمين، د) = د' \Leftrightarrow \exists س | د = د' ~ < س >$

يمكن الحصول على مواصفات بديهية (أو جبرية ) لـ deque عن طريق توسيع ودمج مواصفات المكدس والطابور. ^{[ 13 ]}^{[ 14 ]}^{[ 15 ]} (انظر أطروحة نغوين للحصول على صياغة بديلة ^{[ 16 ]} ).

القيود البديهية:

$فارغ (Λ) = ⊤$
$empty (add (e, x, d)) = ⊥$

على شكل مكدس:
- $اقرأ (هـ ، أضف (هـ ، د ، س)) = س$
- $إزالة (هـ ، إضافة (هـ ، س ، د)) = د$ 1

كطابور، ∀ d ≠ Λ :
- $اقرأ (\nege ، أضف (e ، x ، Λ )) = x$
- $اقرأ (\nege ، أضف (e ، x ، d) ) = اقرأ (\nege ، d)$
- $إزالة (\neg e, إضافة (e, x, Λ)) = Λ$ 2
- $remove (\nege, add (e, x, d) ) = add (e, x, remove (\nege, d))$ 3

ينتج عن تسلسل العمليات في المثال السابق التعبير التالي:

$د = إزالة (يمين، إضافة (يسار، DE ، إزالة (يسار، إزالة (يسار، إضافة (يمين، UE ، إضافة (يمين، QUE ، إضافة (يسار، STA ، إزالة (يسار، إضافة (يمين، CK ، إضافة (يسار، DE ،Λ))))))))))$

يمكن تبسيط ذلك باستخدام البديهيات ( 1 ) و ( 2 ) و ( 3 ) . وبالترتيب، بدءًا من قائمة الانتظار الفارغة:

أضف (يسار، DE) ⎞ ⎠ ⁽¹⁾_→ id

أضف (يمين، CK) ⎞ ⎠ ⁽³⁾_→ ⎛ ⎝ إزالة (يسار)

إزالة (يسار) أضف (يمين، CK) ⎞ ⎟ ⎟ ⎟ ⎠ ⁽²⁾_→ id

أضف (يسار، STA) ⎞ ⎠ ⁽¹⁾_→ id

أضف (يمين، QUE) ⎞ ⎠ ⁽³⁾_→ ⎛ ⎝ إزالة (يسار)

أضف (يمين، UE) ⎞ ⎠ ⁽³⁾_→ ⎛ ⎝ إزالة (يسار) أضف (يمين، QUE) ⎞ ⎠ ⁽³⁾_→ ⎛ ⎝ إزالة (يسار)

إزالة (يسار)

أضف (يمين، UE)

⎞ ⎠ ⁽³⁾_→ ⎛ ⎝

إزالة (يسار)

أضف (يمين، QUE)

⎞ ⎟ ⎟ ⎟ ⎠ →

DE QUE

إزالة (يسار) أضف (يمين، UE)) ⎞ ⎠ ⁽¹⁾_→ id

أضف (يسار، DE) ⎞ ⎠ ⁽³⁾_→ ⎛ ⎝ إزالة (يمين)

إزالة (يمين) أضف (يسار، DE)

وينتج عن ذلك التعبير التالي:

د = أضف (يسار، DE ، أضف (يمين، QUE ،Λ))

كتحويل من تسلسل فارغ :

< > أضف (يمين، QUE) ⟼ < QUE > أضف (يسار، DE) ⟼ < DE, QUE >

وعلى العكس من ذلك، يمكن تحديد المكدس والطابور بشكل بديهي من حيث الطابور المزدوج.

المواصفات الموروثة للمكدس

ليكن لدينا مجموعة من العناصر $s \in S \subset D$

العمليات:

$top (s) = read (left, s), \forall s \neq Λ$
$push (x, s) = add (left, x, s)$
$pop (s) = remove (left, s), \forall s \neq Λ$

البديهيات:

$top (push (x, s)) = x$
$pop (push (x, s)) = s$

المواصفات الموروثة للطابور

ليكن طابور $q \in Q \subset D$

العمليات:

$front (q) = read (left, q), \forall q \neq Λ$
$enqueue (x, q) = add (right, x, q)$
$dequeue (q) = إزالة (يسار, q) , \forall q \neq Λ$

البديهيات:

$front (enqueue (x,Λ)) = x$
$front (enqueue (x, q)) = front (q), \forall q \neq Λ$
$dequeue (enqueue (x,Λ)) = Λ$
$dequeue (enqueue (x, q)) = enqueue (x, dequeue (q)), \forall q \neq Λ$

مصطلحات

يُستخدم مصطلح deque ( يُلفظ / dɛk / DEK ) اختصارًا لـ " طابور مزدوج النهاية " . يُستخدم مصطلح dequeue أحيانًا، ولكنه قد يُسبب التباسًا لأنه يُستخدم أيضًا لعملية إزالة عنصر من الطابور المزدوج النهاية. يُمكن أيضًا تسمية الطابور المزدوج النهاية بقائمة مرتبطة رأسية-ذيلية ، مع أن هذا المصطلح يُشير في الأصل إلى تطبيق مُحدد . يُمكن تسمية الطابور المزدوج النهاية المُقيد بالإخراج بـ steque (اختصارًا لـ "طابور ذو نهاية مكدسة"). ^[¹⁷^]^:⁵³

لا توجد مصطلحات موحدة مرتبطة بقوائم الانتظار المزدوجة (deque). يشير مصطلحا " إضافة عنصر إلى قائمة الانتظار" و "إزالة عنصر من قائمة الانتظار"، المستعاران من بنية قائمة الانتظار، عمومًا إلى العمليات الأساسية على قائمة الانتظار المزدوجة، من كلا الطرفين. لكن غالبًا ما تستخدم الأبحاث والتطبيقات العملية أسماءً مختلفة. وتختلف أسماء العمليات باختلاف السياق، والمؤلف، والتطبيق، أو لغة البرمجة.

على غرار الطابور: الإضافة والإزالة ، أو الدفع والسحب ؛
على غرار المكدس: الدفع والسحب على جانب واحد، وربما الحقن والإخراج على الجانب الآخر ؛
على غرار القائمة: السلبيات وغير السلبيات على جانب واحد، والسلبيات وغير السلبيات على الجانب الآخر؛
على غرار المصفوفة: أضف إلى أحد الجانبين، وأضف إلى الجانب الآخر، أو قم بالإزاحة ثم أعد الإزاحة .

بخلاف هياكل البيانات المرتبطة، فإن قائمة الانتظار المزدوجة متناظرة. ويمكن تسمية جوانبها بحرية وفقًا للسياق:

على غرار الطابور: الأمام والخلف ؛
على غرار الرصة: الأعلى والأسفل ؛
قياساً على القائمة: الرأس أو الأخير ؛
على غرار المصفوفة: الأول والنهاية ، أو الأول والأخير ؛
وأخيراً ، يحافظ اليسار واليمين على التناظر الأصلي للهيكل.

قد يكون الاسم الكامل للعملية مزيجًا من اسم العملية الأساسية واسم الجانب: مثل push_front و pop_back . ويمكن ربط مصطلحات من تشبيهات مختلفة في سياق واحد: append و pop ، و push و shift ، أو front و tail . وأخيرًا، تستخدم بعض لغات البرمجة أسماءً مختلفة بناءً على بنية البيانات الأساسية.

تُستخدم أيضًا عمليات "النظرة الخاطفة" بشكل عام ، والتي تُعيد القيمة الموجودة في أحد طرفي قائمة الانتظار المزدوجة دون إخراجها منها. غالبًا ما تُسمى هذه العملية نسبةً إلى الطرف المستهدف: على سبيل المثال، top هي قيمة العنصر الموجود في أعلى قائمة الانتظار المزدوجة. في سياق البرمجة الوظيفية ، لا تُستخدم عملية إخراج العنصر من قائمة الانتظار المزدوجة (التي تُعيد قيمتين: العنصر المُزال وقائمة الانتظار المزدوجة الجديدة). يتم استبدالها بدالة نظرة خاطفة (مثل head و last ) ودالة تُعيد قائمة الانتظار المزدوجة ناقصًا العنصر الأخير، مثل tail و init .

التطبيقات

توجد طريقتان شائعتان على الأقل لتنفيذ قائمة الانتظار المزدوجة بكفاءة، وغالبًا ما تُقارن إحداهما بالأخرى : باستخدام قائمة مرتبطة ثنائيًا أو باستخدام مصفوفة ديناميكية مُعدّلة. توجد العديد من الاختلافات، وغالبًا ما تكون التطبيقات الفعلية حلولًا هجينة. بالإضافة إلى ذلك، توجد العديد من التطبيقات الوظيفية البحتة لقائمة الانتظار المزدوجة.

قائمة مرتبطة ثنائياً

مع أن القائمة البسيطة قد تُنفذ نموذج الطابور المزدوج، إلا أن القائمة المرتبطة ثنائياً تُعدّ أكثر ملاءمةً لتناظرها الذي يُتيح الوصول السريع إلى طرفي القائمة ( الرأس والذيل ، ومن هنا جاء اسم القائمة المرتبطة رأس-ذيل ). الحل الأمثل هو إدارة مرجعين؛ أو بدلاً من ذلك، يُمكن بناء الطابور المزدوج كقائمة دائرية.

قائمة مرتبطة بشكل مزدوج تحتوي عقدها على ثلاثة حقول: الرابط إلى العقدة السابقة، وقيمة العنصر، والرابط إلى العقدة التالية.

في تطبيق قائمة مرتبطة ثنائية، وبافتراض عدم وجود تكلفة إضافية للتخصيص/إلغاء التخصيص، يكون التعقيد الزمني لجميع عمليات القائمة المزدوجة هو $O(1)$ . بالإضافة إلى ذلك، يمكن أيضًا إجراء الإضافة أو الحذف في المنتصف، باستخدام مُكرِّر، في وقت ثابت؛ ومع ذلك، فإن الوقت المستغرق للوصول العشوائي بواسطة الفهرس هو $O(n) . وبالمثل،$ يتطلب العثور على عنصر معين عادةً وقتًا قدره $O(n)$ . تتميز هياكل البيانات المرتبطة عمومًا بضعف موضعية المرجع.

مصفوفة ديناميكية

في هذه الحالة أيضًا، على الرغم من إمكانية استخدام مصفوفة ديناميكية لتنفيذ قائمة انتظار مزدوجة، إلا أن استخدام نوع قابل للتوسع من كلا الطرفين يُعدّ أكثر ملاءمة. يُطلق على هذا النوع أحيانًا اسم قوائم الانتظار المزدوجة المصفوفية . ويمكن تحقيق ذلك بطرق مختلفة، على سبيل المثال:

عن طريق إزاحة موضع العنصر الأول من المصفوفة في الذاكرة المحجوزة: يتم توزيع المساحة غير المستخدمة على جانبي البيانات؛
مع مصفوفة دائرية .

يبلغ التعقيد الزمني المُستهلك لجميع عمليات قائمة الانتظار المزدوجة (deque) مع مصفوفة قائمة انتظار مزدوجة O $(1)$ ، وذلك بفضل التوسع الهندسي لمخزن البيانات الخلفي. بالإضافة إلى ذلك، يستغرق الوصول العشوائي بواسطة الفهرس وقتًا ثابتًا ؛ لكن متوسط الوقت المستغرق للإدراج أو الحذف في المنتصف هو $O(n)$ . بفضل الوصول العشوائي السريع، يستغرق العثور على عنصر في مصفوفة مرتبة وقتًا قدره $O(log n)$ ( بحث ثنائي ). في كل مرة يتم فيها تغيير حجم المصفوفة، يتم نقل المحتوى بأكمله: وبالتالي يتضاعف استخدام الذاكرة مؤقتًا (أو أكثر)، وتُفقد جميع المراجع المباشرة (الخارجية) لمحتوى المصفوفة.

تطبيقات وظيفية ومستمرة

لا يمكن استخدام القوائم المزدوجة المرتبطة كهياكل بيانات غير قابلة للتغيير . كما أن المصفوفة غير القابلة للتغيير ستكون غير فعالة للغاية (غالبًا ما تُحاكى المصفوفة بشجرة ). يمكن أن يعتمد التنفيذ الوظيفي البحت لقائمة الانتظار المزدوجة على المكدس، والذي يمكن تنفيذه بسهولة باستخدام قائمة مرتبطة أحادية كهيكل غير قابل للتغيير ومستمر .

توجد العديد من الدراسات في الأدبيات العلمية التي تتناول هذه المشكلة. وتعتمد جميعها على فكرتين رئيسيتين. الأولى هي إمكانية تمثيل قائمة الانتظار المزدوجة (deque) بزوج من المكدسات، أحدهما يمثل الجزء الأمامي من القائمة والآخر يمثل الجزء الخلفي. عندما يصبح أحد الجانبين فارغًا نتيجةً لكثرة عمليات السحب أو الإخراج ، تُنسخ قائمة الانتظار المزدوجة، الموجودة الآن في مكدس واحد، إلى مكدسين، يحتوي كل منهما على نصف عناصر القائمة. يضمن هذا التقسيم بالتساوي أن عملية النسخ هذه، على الرغم من تكلفتها العالية، تحدث بشكل غير متكرر. تُظهر حجة استهلاك بسيطة أن هذا يُعطي محاكاة خطية لقائمة الانتظار المزدوجة بعدد ثابت من المكدسات: حيث تُحاكى k عملية على قائمة الانتظار المزدوجة، بدءًا من قائمة فارغة، بواسطة O(k) عملية على المكدس. [...] أما الفكرة الثانية فهي استخدام النسخ التزايدي لتحويل هذه المحاكاة الخطية إلى محاكاة فورية: فبمجرد أن يصبح المكدسان غير متوازنين بدرجة كافية، تبدأ عملية إعادة النسخ لإنشاء مكدسين متوازنين.

— كابلان، حاييم؛ تارجان، روبرت إي. (1995). "قوائم مستمرة مع ربط العناصر عبر التباطؤ المتكرر". وقائع الندوة السنوية السابعة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة . لاس فيغاس، نيفادا. الصفحات 93-102 . doi : 10.1145/225058.225090 . (نسخة أولية من ^{[ 18 ]} )

قد تكون هذه العملية الأخيرة معقدة نوعًا ما، إذ يجب تنفيذها بالتزامن مع عمليات أخرى وإكمالها قبل العملية التالية، لتحقيق تعقيد زمني حقيقي مُستهلك. تتمثل الخطوة التالية في دعم العمليات في زمن $O(1)$ في أسوأ الحالات . يتمثل تحدٍ آخر في دمج قوائم الانتظار المزدوجة في الوقت الحقيقي. يقدم أوكاساكي حلاً بسيطًا يستخدم القوائم الكسولة مع التخزين المؤقت . تتم موازنة المكدسات جزئيًا تلقائيًا من خلال جدولة دقيقة للوظائف التزايدية. ^{[ 17 ]}^{: 52-59}^{: 115.} مع ذلك، يعتبر بعض المؤلفين هذه الخوارزمية غير وظيفية بحتة لأن التخزين المؤقت يُعتبر أثرًا جانبيًا . ^{[ 18 ]}^{: 581.} يقدم كابلان وتارجان نسختهما الخاصة من قائمة الانتظار المزدوجة الوظيفية البحتة (غير القابلة للدمج)، استنادًا إلى ثلاث أفكار: ^{[ 18 ]}

التمهيد الهيكلي للبيانات ، مما ينتج عنه بنية متكررة تتنبأ بشجرة الأصابع : قائمة الانتظار المزدوجة هي ثلاثية تتكون من قائمة انتظار مزدوجة فرعية محاطة بمخزنين مؤقتين محدودين الحجم. تعمل عمليتا الإضافة والحذف بشكل أساسي على المخازن المؤقتة (في الوقت الفعلي بسبب الحجم المحدود)، وتتقدمان خطوة واحدة للأمام في عملية الموازنة؛
التباطؤ التكراري ، المستوحى من التمثيل الثنائي الزائد (RBR)، حيث 2يمثل الرقم الإضافي حملاً معلقاً: تحتوي قائمة الانتظار الفرعية على أزواج من العناصر من قائمة الانتظار الأصلية، ويتأخر انتشار عملية الموازنة إلى قائمة الانتظار الفرعية كما هو الحال مع انتشار الحمل بعد زيادة أو إنقاص رقم RBR؛ ^{[ 17 ]}^{: 105}
وتعديلٌ لبنية العمود الفقري لشجرة الأصابع (المكدس) إلى مكدس من المكدسات يُمكن اعتباره قائمة تخطي ثنائية المستوى . يُتيح هذا الوصول الفوري إلى قوائم الانتظار الفرعية غير المتوازنة. قياسًا على RBR، تُمثل المكدسات الفرعية كتلًا متجاورة من 1الأرقام، يُمكن تخطيها للوصول إلى الرقم التالي 2، أي الحمل المُعلق.

في هذه الورقة، يقدم كابلان وتارجان أيضًا نسخة أكثر تعقيدًا تحقق الربط في الوقت الفعلي. مع ذلك، فإن هذا الوصف نصي في معظمه. ينشر كل من ج. فيينو، أ. ويندلينغ، أ. غينو، و ف. بوتييه تطبيقًا مُثبتًا لبنية البيانات هذه (بلغتي OCaml و Rocq )، إلى جانب وصف رسمي وتحليل مفصل للخوارزمية. ^{[ 19 ]}

بشكل عام، يتطلب الربط في الوقت الحقيقي أن يكون الطابور المزدوج عبارة عن مجموعة تتكون أساسًا من بنيتين فرعيتين، تحتوي كل منهما بدورها على طوابير مزدوجة أو مركبات من طوابير مزدوجة. ثم يتم استبدال الهيكل الخطي للطابور المزدوج غير القابل للربط بهيكل ثنائي .

قدّم كابلان وأوكاساكي وتارجان نسخةً أبسط وأكثر كفاءةً يمكن تنفيذها إما باستخدام التقييم الكسول أو باستخدام الطفرة بشكلٍ أوسع ولكن لا يزال محدودًا. ^{[ 20 ]} كما ابتكر ميهايسكو وتارجان تطبيقًا وظيفيًا بحتًا أبسط (ولكنه لا يزال معقدًا للغاية) لقوائم الانتظار المزدوجة القابلة للربط، بالإضافة إلى تطبيق أبسط بكثير لقوائم الانتظار المزدوجة غير القابلة للربط، وكلاهما يتمتع بحدود مثالية في أسوأ الحالات (لم تُنشر رسميًا). ^{[ 21 ]}

الدعم اللغوي

توفر حاويات Ada الحزم العامة Ada.Containers.Vectorsو Ada.Containers.Doubly_Linked_Lists، لتنفيذات المصفوفة الديناميكية والقائمة المرتبطة، على التوالي.

توفر مكتبة القوالب القياسية للغة C++ قوالب الفئات std::dequeو std::list، لتنفيذات المصفوفات المتعددة والقوائم المرتبطة، على التوالي.

ابتداءً من Java 6، يوفر إطار عمل المجموعات في Java Dequeواجهة جديدة تتيح وظائف الإضافة والحذف من كلا الطرفين. يتم تنفيذ هذه الواجهة بواسطة فئات مثل ArrayDeque(الجديدة أيضًا في Java 6) و LinkedList، والتي توفر تطبيقات المصفوفات الديناميكية والقوائم المرتبطة، على التوالي. مع ذلك، ArrayDequeوعلى عكس اسمها، لا تدعم فئة الوصول العشوائي.

يدعم كل من نموذج المصفوفة في جافا سكريبت ومصفوفات بيرل بشكل أصلي كلاً من إزالة ( shift و pop ) وإضافة ( unshift و push ) العناصر من كلا الطرفين.

أضافت بايثون 2.4 collectionsوحدة تدعم كائنات deque . يتم تنفيذها باستخدام قائمة مرتبطة ثنائياً من المصفوفات الفرعية ذات الطول الثابت.

ابتداءً من PHP 5.3، تتضمن إضافة SPL في PHP فئة 'SplDoublyLinkedList' التي يمكن استخدامها لتنفيذ هياكل بيانات Deque. سابقًا، كان إنشاء هيكل Deque يتطلب استخدام دوال المصفوفات array_shift/unshift/pop/push.

تُنفذ وحدة Data.Sequence في GHC بنية deque فعالة ووظيفية في لغة Haskell . يستخدم التنفيذ شجرتين أو ثلاث شجرات ذات أصابع مُعَلَّمة بأحجامها.

std::collectionsتتضمن لغة Rust مكتبة VecDeque التي تُنفذ قائمة انتظار مزدوجة الأطراف باستخدام مخزن مؤقت حلقي قابل للتوسع.

التطبيقات

R DELQUE.(J) - حذف المستخدم J من قوائم الانتظار R ENDQUE.(J) - يضع المستخدم J في نهاية مستوى قائمة الانتظار (J) R BEGQUE.(J) - يضع المستخدم J في بداية مستوى قائمة الانتظار (J)

في عام 1965، وقبل حتى تسمية نظام الطابور المزدوج (deque) ، وصف مقتطف من التعليمات البرمجية في الملاحظات الفنية لنظام CTSS ثلاث إجراءات فرعية تعالج طوابير "المستخدمين". لم يتم تنفيذ سوى الإجراءين الفرعيين الأولين، ولكن فكرة الطابور الأقل تقييدًا كانت موجودة ومُبرمجة في مكتبة. ^{[ 22 ]}

يمكن دائمًا استبدال الطابور ذي الطرفين بطابور عادي أو بنية مكدس. لذا، غالبًا ما تكون التطبيقات العملية للطابور ذي الطرفين نسخًا موسعة من الخوارزميات القائمة على المكدس أو الطابور. في الواقع، لا تحتاج العديد من التطبيقات إلا إلى طابور ذي طرفين مقيد بالمخرجات أو (نادرًا) بالمدخلات. هنا، نقتصر على التطبيقات العملية التي تعتمد بشكل أمثل على الطابور ذي الطرفين الصارم، أي التي لا تحتاج إلا إلى الوصول إلى العناصر من كلا الطرفين واحدًا تلو الآخر.

طابور رتيب

يمكن استخدام قائمة انتظار مزدوجة ذات مدخلات محدودة لإنشاء قائمة انتظار رتيبة ، أي سلسلة فرعية تكون عناصرها مرتبة بترتيب معين، إما تصاعديًا أو تنازليًا. عند إعطاء سلسلة، تحتفظ الخوارزمية فقط بالعناصر بالترتيب المطلوب وتتجاهل العناصر الأخرى. ويُحفظ ترتيب العناصر. لإنشاء سلسلة رتيبة تصاعدية (أو تنازلية)، تُستخدم عمليات المكدس فقط.

ابدأ بطابور انتظار مزدوج فارغ،
لكل عنصر في تسلسل الإدخال:
- إذا كان العنصر الأخير في قائمة الانتظار المزدوجة أكبر (أو أصغر) من العنصر الحالي، فقم بإخراجه.
- قم بإضافة العنصر الحالي إلى قائمة الانتظار المزدوجة (deque).

std :: deque <int> increase_monotonic_queue ( std :: vector <int> & seq [ ] ) { std :: deque <int> q ; for ( std :: size_t i = 0 ; i < seq.size ( ) ; i ++ ) { while ( ! q.empty ( ) && q.back ( ) > seq [ i ] ) q.pop_back ( ) ; q.push_back ( seq [ i ] ) ; } return q ; }

يمكن بعد ذلك إزالة عناصر التسلسل الرتيب من الجانب الآخر (ومن هنا جاء استخدام deque).

يمكن استخدام طابور رتيب لإيجاد القيمة الدنيا أو القصوى في نافذة منزلقة على تسلسل ما، وذلك في تعقيد زمني خطي. ^{[ 23 ]} يبلغ تعقيد الحل البسيط $O(nk)$ من الزمن و $O(1)$ من المساحة، حيث n هو طول التسلسل المدخل و k هو حجم النافذة. أما الحل الذي يستخدم نوعًا من طرق البحث، فيبلغ تعقيده $O(n.log n)$ من الزمن و $O(n)$ من المساحة.

في الكود التالي، يخزن الطابور الرتيب مراجع لعناصر التسلسل.

#تتضمن <vector> #تتضمن <deque>typedef std :: vector <int> :: const_iterator seq_iterator ; typedef std :: deque <seq_iterator> monotonic_queue ;monotonic_queue & decreasing_monotonic_queue_push ( monotonic_queue & q , seq_iterator i ) { while ( ! q . empty () && * q . back () < * i ) q . pop_back (); q . push_back ( i ); return q ; }std :: vector <int> max_of_subarrays ( std :: vector <int> & seq , std :: size_t win_sz ) { std :: vector <int> max_of_sub ; monotonic_queue decreasing ; seq_iterator i = seq.begin ( ) ; // مسح النافذة الأولى for ( size_t win_i = 0 ; i < seq.end ( ) && win_i < win_sz ; i ++ , win_i ++ ) decreasing_monotonic_queue_push ( decreasing , i ) ; max_of_sub.push_back ( * decreasing.front ( ) ) ; // مسح باقي التسلسل for ( / * keep i * / ; i < seq.end ( ) ; i ++ ) { if ( decreasing.front ( ) < = i - win_sz ) decreasing . pop_front ( ); // الخروج من نطاق decreasing_monotonic_queue_push ( decreasing , i ); max_of_sub.push_back ( * decreasing.front ( ) ) ; } return max_of_sub ; }

يتم إدخال كل عنصر من عناصر التسلسل المدخل وإخراجه مرة واحدة على الأكثر، مما ينتج عنه $2.n$ عملية. وبالتالي، فإن التعقيد الزمني هو $O(n)$ . أما التعقيد المكاني فهو $O(k)$ ، وهو الحد الأقصى لحجم قائمة الانتظار المزدوجة.

وبالمثل، يسمح الطابور الرتيب بتحسين بعض حالات البرمجة الديناميكية المكافئة لمسألة التسلسل الفرعي ذي الوزن الأدنى : مسألة أقصر مسار لرسم بياني موجه مُثقَّل، وتقسيم الفقرات ، وما إلى ذلك. تُوصف هذه المسائل بأنها محدبة أو مقعرة ، وبالتالي فهي رتيبة . عندئذٍ، ينخفض التعقيد الزمني من $O(n²) إلى$ O $(n log n)$ ، وإلى $O(n)$ في الحالات الملائمة. ^{[ 24 ]}^{[ 25 ]}

من التطبيقات المباشرة الأخرى للطابور الرتيب طابور الحد الأدنى ( minqueue) . في هذه الحالة، يختلف عدد العناصر في النافذة. يُعدّ طابور الحد الأدنى بنية بيانات ذات واجهة طابور تُتيح الوصول المباشر إلى أصغر عنصر مُخزّن. وتتمثل العمليات الرئيسية في الإضافة (enqueue )، والإزالة (dequeue) ، وإيجاد أصغر عنصر . على الرغم من أن الاسم يُشير إلى كومة (الحد الأدنى/الحد الأقصى) ، إلا أن طابور الحد الأدنى/الحد الأقصى ليس طابور أولوية : إذ يُحافظ على ترتيب العناصر من لحظة الدخول إلى لحظة الخروج (وفقًا لسياسة FIFO). يُعدّ الطابور العادي المُدمج مع طابور رتيب مُتزايد مساعد، والذي يُوفّر أصغر عنصر في بدايته، نسخةً بسيطةً من طابور الحد الأدنى بزمن مُستهلك ثابت $O(1).$ تُطبّق إضافة عنصر على كلا الطابورين، وعندما يُزال أصغر عنصر من الطابور العادي (أي العنصر الذي في بدايته نفسه)، يُزال أيضًا من الطابور الرتيب. ^{[ 9 ]}

الغلاف المحدب لخط متعدد بسيط

تحسب خوارزمية ميلكمان الغلاف المحدب لسلسلة مضلعية بسيطة (أو مضلع بسيط ) في زمن خطي. ويكمن الاختلاف الرئيسي بينها وبين الخوارزميات المشابهة الأخرى في أن خوارزمية ميلكمان تتطلب إضافة رؤوس أو إزالتها من طرفي سلسلة الغلاف المتشكلة. ومن هنا يأتي استخدام قائمة انتظار مزدوجة (deque). تحسب الخوارزمية موضع كل رأس جديد بالنسبة للقطعتين الأولى والأخيرة (رأسين لكل منهما) من سلسلة الغلاف (المخزنة في قائمة الانتظار المزدوجة). يتم تجاهل الرأس أو إضافته (وضعه في قائمة الانتظار) إلى جانبي قائمة الانتظار المزدوجة (حيث يمثل الغلاف حلقة تكرارية)، وذلك بعد إزالة (إخراج) بعض الرؤوس السابقة الموجودة الآن على الجانب الداخلي للغلاف. ^{[ 26 ]}^{[ 27 ]}^{[ 28 ]}

from collections import dequeدالة تحديد الموضع ( A , B , C ) : det = ( B.X - A.X ) * ( C.Y - A.Y ) - ( B.Y - A.Y ) * ( C.X - A.X ) إذا كان det > 0 : أرجع 1 # C على يسار الخط AB وإذا كان det < 0 : أرجع 0 # C على يمين الخط AB وإلا : أرجع -1 # AB و C على استقامة واحدةدالة ميلكمان ( المسار ): إذا كان موضع ( المسار [ 0 ]، المسار [ 1 ]، المسار [ 2 ]) يساوي 1 : hull = deque ([ المسار [ 2 ]، المسار [ 0 ]، المسار [ 1 ]، المسار [ 2 ]]) وإلا : hull = deque ([ المسار [ 2 ]، المسار [ 1 ]، المسار [ 0 ]، المسار [ 2 ]]) لكل v في المسار [ 3 :] : إذا كان موضع ( hull [ 0 ] ، hull [ 1 ] ، v ) يساوي 1 وموضع ( hull [ -2 ]، hull [ -1 ] ، v ) يساوي 1 : استمر بينما موضع ( hull [ 0 ]، hull [ 1 ] ، v ) أقل من أو يساوي 0 : hull.popleft ( ) hull . أضف العنصر v من اليسار إلى القائمة ` hull` . طالما أن موضع العنصر v في القائمة ` hull` أقل من أو يساوي صفرًا ، فقم بإزالة العنصر v من القائمة ` hull` . أضف العنصر v إلى القائمة ` hull` . أرجع القائمة ` hull` .

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

يمكن اعتبار المكدسات والطوابير نوعًا خاصًا من طوابير الأولوية ، حيث تُحدد الأولوية بترتيب إدخال العناصر. وبالمثل، يمكن لطابور مزدوج (deque) أن يُنفذ طابور أولوية بمستويين: تُضاف العناصر ذات الأولوية العالية إلى مقدمة الطابور، بينما تُضاف العناصر ذات الأولوية المنخفضة إلى مؤخرته. ^{[ 1 ]} ما لم يكن من الممكن إلغاء عنصر أو سرقته ثم إخراجه من الأسفل، فإن الطابور المزدوج المقيد بالإخراج يكون كافيًا.

وبالتالي، يُمكن تعديل خوارزمية ديكسترا القياسية لإيجاد أقصر مسار من مصدر واحد في رسم بياني ذي حواف بتكلفة صفرية وحواف بتكلفة 1. يُستخدم طابور مزدوج (deque) بدلاً من طابور الأولوية الدنيا . تُضاف العناصر ذات التكلفة الصفرية إلى مقدمة الطابور المزدوج (ذات الأولوية العالية)، ثم تُعالج دائمًا قبل العناصر ذات التكلفة الأعلى (ذات الأولوية المنخفضة) التي تُضاف إلى نهاية الطابور.

تُستخدم قائمة الانتظار المزدوجة (deque) في خوارزمية سرقة العمل . ^{[ 29 ]} تُنفذ هذه الخوارزمية جدولة المهام لعدة معالجات. تُحفظ قائمة انتظار مزدوجة منفصلة تحتوي على الخيوط المراد تنفيذها لكل معالج. لتنفيذ الخيط التالي، يحصل المعالج على العنصر الأول من قائمة الانتظار المزدوجة (باستخدام عملية "إزالة العنصر الأول"). إذا تفرّع الخيط الحالي، يُعاد إلى بداية قائمة الانتظار المزدوجة ("إضافة عنصر في البداية") ويتم تنفيذ خيط جديد. عندما يُنهي أحد المعالجات تنفيذ خيوطه الخاصة (أي عندما تكون قائمة الانتظار المزدوجة الخاصة به فارغة)، يمكنه "سرقة" خيط من معالج آخر: يحصل على العنصر الأخير من قائمة الانتظار المزدوجة الخاصة بالمعالج الآخر ("إزالة العنصر الأخير") وينفذه. تُستخدم خوارزمية سرقة العمل في مكتبة Intel's Threading Building Blocks (TBB) للبرمجة المتوازية.

آلة ديك

آلة الطابور المزدوج (DA) هي آلة ذات حالات محدودة مزودة بذاكرة مساعدة من نوع الطابور المزدوج. وهي تعميم لآلة الدفع لأسفل (PDA) (آلة المكدس) وآلة الطابور (آلة السحب لأعلى، PUA). وبذلك، فهي مكافئة لآلة تورينج ، وبالتالي يمكنها معالجة نفس فئة اللغات الرسمية . ولكن على عكس آلة الدفع لأسفل وآلة السحب لأعلى اللتين تفرضان التسلسل، تسمح آلة الطابور المزدوج بالتنفيذ المتوازي أو المتداخل لبعض العمليات. ^{[ 30 ]}

انظر أيضاً

مراجع

1 2 3 4 لويس، تي جي (ثيودور جايل) (1976). تطبيق هياكل البيانات . هوتون ميفلين. ص 56. ISBN 9780395240601.
1 2 3 4 5 أمسبري، واين. هياكل البيانات : من المصفوفات إلى قوائم الانتظار ذات الأولوية . وادزورث. ISBN 9780534045906.
↑ توماس، بيت؛ روبنسون، هيو؛ إيمز، جودي (1988). أنواع البيانات المجردة: مواصفاتها، وتمثيلها، واستخدامها . سلسلة أكسفورد للرياضيات التطبيقية وعلوم الحاسوب. أكسفورد : نيويورك: مطبعة كلارندون ؛ مطبعة جامعة أكسفورد. ص 142. ISBN 978-0-19-859663-9.
1 2 3 كنوت، دونالد إرفين (1997). فن برمجة الحاسوب . المجلد 1: الخوارزميات الأساسية ( الطبعة الثالثة). ريدينغ، ماساتشوستس: أديسون-ويسلي. القسم 2.2.1: المكدسات، والطوابير، والطوابير المزدوجة. ISBN 0-201-89683-4.
↑ جيسي ليبرتي؛ سيدهارتا راو؛ برادلي جونز. لغة C++ في ساعة واحدة يوميًا، سلسلة Sams Teach Yourself ، الطبعة السادسة. دار نشر Sams، 2009. ISBN 0-672-32941-7الدرس 18: فئات المصفوفات الديناميكية STL، ص 486.
↑ سميث، هاري ف. (1987). هياكل البيانات : الشكل والوظيفة . هاركورت بريس جوفانوفيتش. ISBN 9780155168206.
↑ بوتش، جرادي (1987). مكونات البرمجيات باستخدام لغة آدا: الهياكل والأدوات والأنظمة الفرعية . مينلو بارك، كاليفورنيا: دار بنجامين/كومينغز للنشر. الفصل 7. ISBN 978-0-8053-0610-1.
1 2 ديل، نيل ؛ ووكر، هنري م. (1996). أنواع البيانات المجردة: المواصفات، والتطبيقات، والتنفيذات . جونز وبارتليت ليرنينج. ISBN 978-0-66940000-7.
1 2 3 براس، بيتر (2008). هياكل البيانات المتقدمة . مطبعة جامعة كامبريدج. ص 272. ISBN 978-1-108-73551-3.
↑ غاجيفسكا، هانيا؛ تارجان، روبرت إي. (1986). "قوائم الانتظار المزدوجة ذات الترتيب الهرمي" . رسائل معالجة المعلومات . 22 (4): 197-200 . doi : 10.1016/0020-0190(86)90028-1 . تاريخ الاسترجاع : 28-02-2026 .
↑ بوخسباوم، آدم ل.؛ سوندار، راجاماني؛ تارجان، روبرت إي. (1995). "التمهيد الهيكلي للبيانات، وضغط المسار الخطي، وقوائم الانتظار المزدوجة ذات الترتيب الهرمي القابلة للتسلسل" . مجلة SIAM للحوسبة . 24 (6): 1190-1206 . doi : 10.1137/S0097539792242144 . ISSN 0097-5397 . تاريخ الاسترجاع: 28 فبراير 2026 .
↑ إلزاي، روي س. (1991). هياكل البيانات لنظم المعلومات الحاسوبية ( الطبعة الثانية). نيويورك: ماكميلان. ISBN 978-0-574-18740-6.
↑ مركز المعلومات التقنية للدفاع (1989-08-01). DTIC ADA218855: التحقق التلقائي من اتساق وقت التشغيل وتصحيح أخطاء البرامج المحددة رسميًا . الصفحات 6-7 .
↑ مركز المعلومات التقنية للدفاع (1991-10-01). DTIC ADA311117: مواصفات حزمة آنا: دراسات حالة . ص 41.
↑ لودن، كينيث سي. (1995). لغات البرمجة: المبادئ والتطبيق . سلسلة PWS-KENT في علوم الحاسوب ( الطبعة الثالثة [المطبوعة]). بوسطن، ماساتشوستس: PWS. ISBN 978-0-534-93277-0.
↑ نغوين، دوان هان (ديسمبر 1995). نموذج معماري للبحث عن مكونات البرمجيات (أطروحة). مونتيري، كاليفورنيا. كلية الدراسات العليا البحرية. ص 108-109 .
1 2 3 أوكازاكي، كريس (سبتمبر 1996). هياكل البيانات الوظيفية البحتة (ملف PDF) (أطروحة دكتوراه). جامعة كارنيجي ميلون. CMU-CS-96-177.
1 2 3 كابلان، حاييم؛ تارجان، روبرت إي. (1999). "قوائم انتظار ثنائية وظيفية بحتة، تعمل في الوقت الحقيقي مع تسلسل" . مجلة ACM . 46 (5): 577-603 . doi : 10.1145/324133.324139 .
^ فينوت، جولز. وندلينج، آرثر؛ جينيو، أرمايل؛ بوتييه ، فرانسوا (12/05/2025). “تم التحقق من Deques الوظيفية البحتة في الوقت الحقيقي”. أرخايف : 2505.07681 [ cs.PL ].
↑ كابلان، حاييم؛ أوكاساكي، كريس؛ تارجان، روبرت إي. (2000). "قوائم متصلة بسيطة ومستمرة" (PS) . مجلة SIAM للحوسبة . 30 (3): 965-977 . doi : 10.1137/S0097539798339430 . مؤرشف من الأصل بتاريخ 25-09-2010.
↑ ميهايسكو، رادو؛ تارجان، روبرت (أغسطس 2003)، "ملاحظات حول قوائم الانتظار المزدوجة القابلة للتسلسل في لغة ليسب البحتة" ، علوم الحاسوب 528 هياكل البيانات وخوارزميات الرسوم البيانية ، علوم الحاسوب (مادة دراسية)، جامعة برينستون، مؤرشفة من الأصل (ملف DOC) في 17 سبتمبر 2006
↑ سالتزر، جيروم هـ. (15 مارس 1965). "ملاحظات فنية حول نظام CTSS" . DSpace@MIT Home . الصفحات 40-41 . تاريخ الاسترجاع: 28 فبراير 2026 .
↑ "الحد الأقصى للنافذة المنزلقة" . GeeksForGeeks . 27 مايو 2011. مؤرشف من الأصل في 3 أغسطس 2025.
↑ يي، ريتشارد. "1D1D DP: تحسين البرمجة الديناميكية" . مؤرشف من الأصل في 16 يناير 2024.
↑ هيرشبرغ، دانيال س.؛ لارمور، لورانس ل. (1985)، مسألة المتتالية الفرعية ذات الوزن الأدنى ، جامعة كاليفورنيا في إرفاين: كلية دونالد برين لعلوم المعلومات والحاسوب{{citation}}: CS1 maint: publisher location ( link )
↑ ميلكمان، أفراهام أ. (1987). "الإنشاء الفوري للغلاف المحدب لخط متعدد بسيط" . رسائل معالجة المعلومات . 25 (1): 11-12 . doi : 10.1016/0020-0190(87)90086-X . MR 0896397 .
↑ لي، فاجي؛ كليت، راينهارد (2011). "الأغلفة المحدبة في المستوى". أقصر المسارات الإقليدية . لندن: سبرينغر لندن. doi : 10.1007/978-1-4471-2256-2_4 . ISBN 978-1-4471-2255-5تم الاطلاع عليه بتاريخ 10 فبراير 2026 .
↑ ألوبيس، جريج. "تاريخ خوارزميات الغلاف المحدب الخطي للمضلعات البسيطة" . مختبر الهندسة الحسابية في جامعة ماكجيل . جامعة ماكجيل . تم الاطلاع عليه بتاريخ 10 فبراير 2026 .
↑ بلوموف، روبرت د.؛ ليسرسون، تشارلز إي. (1999). "جدولة العمليات الحسابية متعددة الخيوط عن طريق سرقة العمل". مجلة ACM . 46 (5): 720-748 . doi : 10.1145/324133.324234 . S2CID 5428476 .
↑ كريسبي-ريغيزي، ستيفانو؛ سان بيترو، بييرلويجي (2020). "آلات الطابور المزدوج، واللغات، وتمثيلات الرسوم البيانية المستوية". علوم الحاسوب النظرية . 834 : 43-59 . doi : 10.1016/j.tcs.2020.02.029 .

روابط خارجية

تطبيق مفتوح المصدر وآمن من حيث النوع لقائمة الانتظار المزدوجة (deque) في شبكة أرشيف لغة C الشاملة
وثائق SGI STL: deque<T, Alloc>
مشروع برمجي: دراسة معمقة لحاوية قائمة الانتظار المزدوجة (Deque) في مكتبة STL
تنفيذ Deque بلغة C، مؤرشف بتاريخ 6 مارس 2014 على موقع Wayback Machine.
تنفيذ VBScript للمكدس، والطابور، والطابور المزدوج، وشجرة الأحمر والأسود
تطبيقات متعددة لقوائم الانتظار المزدوجة غير القابلة للتسلسل في لغة هاسكل

[3] «لماذا لا يُطلق عليه اسم "الطبق المزدوج"؟ إنه لغز، لأن هذا الوصف دقيق على الأقل»،^{[ 2 ]}^{: 131}

[4] يمكن اعتبار قائمة الانتظار المزدوجة "إما قائمة انتظار فائقة أو مكدس فائق".^{[ 1 ]}

[9] «إذا أُدخلت عقدتان من أحد طرفي الشبكة وأُزيلتا من الطرف الآخر، فإنهما ستخرجان بترتيب الطابور. وإذا أُزيلتا من طرف الإدخال، فإنهما ستخرجان بترتيب المكدس. أما إذا أُزيلتا من طرفين متقابلين، فإن ترتيب خروجهما يكون عشوائيًا.»^{[ 2 ]}^{: 131}

[16] "هيكل بيانات يبحث عن تطبيق!"، كما ذكر روي إس. إلزاي في عام 1989.^{[ 12 ]}

[lewis-1] 1 2 3 4 لويس، تي جي (ثيودور جايل) (1976). تطبيق هياكل البيانات . هوتون ميفلين. ص 56. ISBN 9780395240601.

[amsbury-2] 1 2 3 4 5 أمسبري، واين. هياكل البيانات : من المصفوفات إلى قوائم الانتظار ذات الأولوية . وادزورث. ISBN 9780534045906.

[5] توماس، بيت؛ روبنسون، هيو؛ إيمز، جودي (1988). أنواع البيانات المجردة: مواصفاتها، وتمثيلها، واستخدامها . سلسلة أكسفورد للرياضيات التطبيقية وعلوم الحاسوب. أكسفورد : نيويورك: مطبعة كلارندون ؛ مطبعة جامعة أكسفورد. ص 142. ISBN 978-0-19-859663-9.

[knuth-6] 1 2 3 كنوت، دونالد إرفين (1997). فن برمجة الحاسوب . المجلد 1: الخوارزميات الأساسية ( الطبعة الثالثة). ريدينغ، ماساتشوستس: أديسون-ويسلي. القسم 2.2.1: المكدسات، والطوابير، والطوابير المزدوجة. ISBN 0-201-89683-4.

[7] جيسي ليبرتي؛ سيدهارتا راو؛ برادلي جونز. لغة C++ في ساعة واحدة يوميًا، سلسلة Sams Teach Yourself ، الطبعة السادسة. دار نشر Sams، 2009. ISBN 0-672-32941-7الدرس 18: فئات المصفوفات الديناميكية STL، ص 486.

[smith-8] سميث، هاري ف. (1987). هياكل البيانات : الشكل والوظيفة . هاركورت بريس جوفانوفيتش. ISBN 9780155168206.

[10] بوتش، جرادي (1987). مكونات البرمجيات باستخدام لغة آدا: الهياكل والأدوات والأنظمة الفرعية . مينلو بارك، كاليفورنيا: دار بنجامين/كومينغز للنشر. الفصل 7. ISBN 978-0-8053-0610-1.

[dale96-11] 1 2 ديل، نيل ؛ ووكر، هنري م. (1996). أنواع البيانات المجردة: المواصفات، والتطبيقات، والتنفيذات . جونز وبارتليت ليرنينج. ISBN 978-0-66940000-7.

[brass-12] 1 2 3 براس، بيتر (2008). هياكل البيانات المتقدمة . مطبعة جامعة كامبريدج. ص 272. ISBN 978-1-108-73551-3.

[13] غاجيفسكا، هانيا؛ تارجان، روبرت إي. (1986). "قوائم الانتظار المزدوجة ذات الترتيب الهرمي" . رسائل معالجة المعلومات . 22 (4): 197-200 . doi : 10.1016/0020-0190(86)90028-1 . تاريخ الاسترجاع : 28-02-2026 .

[14] بوخسباوم، آدم ل.؛ سوندار، راجاماني؛ تارجان، روبرت إي. (1995). "التمهيد الهيكلي للبيانات، وضغط المسار الخطي، وقوائم الانتظار المزدوجة ذات الترتيب الهرمي القابلة للتسلسل" . مجلة SIAM للحوسبة . 24 (6): 1190-1206 . doi : 10.1137/S0097539792242144 . ISSN 0097-5397 . تاريخ الاسترجاع: 28 فبراير 2026 .

[15] إلزاي، روي س. (1991). هياكل البيانات لنظم المعلومات الحاسوبية ( الطبعة الثانية). نيويورك: ماكميلان. ISBN 978-0-574-18740-6.

[17] مركز المعلومات التقنية للدفاع (1989-08-01). DTIC ADA218855: التحقق التلقائي من اتساق وقت التشغيل وتصحيح أخطاء البرامج المحددة رسميًا . الصفحات 6-7 .

[18] مركز المعلومات التقنية للدفاع (1991-10-01). DTIC ADA311117: مواصفات حزمة آنا: دراسات حالة . ص 41.

[19] لودن، كينيث سي. (1995). لغات البرمجة: المبادئ والتطبيق . سلسلة PWS-KENT في علوم الحاسوب ( الطبعة الثالثة [المطبوعة]). بوسطن، ماساتشوستس: PWS. ISBN 978-0-534-93277-0.

[20] نغوين، دوان هان (ديسمبر 1995). نموذج معماري للبحث عن مكونات البرمجيات (أطروحة). مونتيري، كاليفورنيا. كلية الدراسات العليا البحرية. ص 108-109 .

[okasaki_PFDS-21] 1 2 3 أوكازاكي، كريس (سبتمبر 1996). هياكل البيانات الوظيفية البحتة (ملف PDF) (أطروحة دكتوراه). جامعة كارنيجي ميلون. CMU-CS-96-177.

[KT1999-22] 1 2 3 كابلان، حاييم؛ تارجان، روبرت إي. (1999). "قوائم انتظار ثنائية وظيفية بحتة، تعمل في الوقت الحقيقي مع تسلسل" . مجلة ACM . 46 (5): 577-603 . doi : 10.1145/324133.324139 .

[23] فينوت، جولز. وندلينج، آرثر؛ جينيو، أرمايل؛ بوتييه ، فرانسوا (12/05/2025). “تم التحقق من Deques الوظيفية البحتة في الوقت الحقيقي”. أرخايف : 2505.07681 [ cs.PL ].

[24] كابلان، حاييم؛ أوكاساكي، كريس؛ تارجان، روبرت إي. (2000). "قوائم متصلة بسيطة ومستمرة" (PS) . مجلة SIAM للحوسبة . 30 (3): 965-977 . doi : 10.1137/S0097539798339430 . مؤرشف من الأصل بتاريخ 25-09-2010.

[MT2003-25] ميهايسكو، رادو؛ تارجان، روبرت (أغسطس 2003)، "ملاحظات حول قوائم الانتظار المزدوجة القابلة للتسلسل في لغة ليسب البحتة" ، علوم الحاسوب 528 هياكل البيانات وخوارزميات الرسوم البيانية ، علوم الحاسوب (مادة دراسية)، جامعة برينستون، مؤرشفة من الأصل (ملف DOC) في 17 سبتمبر 2006

[ctss-26] سالتزر، جيروم هـ. (15 مارس 1965). "ملاحظات فنية حول نظام CTSS" . DSpace@MIT Home . الصفحات 40-41 . تاريخ الاسترجاع: 28 فبراير 2026 .

[27] "الحد الأقصى للنافذة المنزلقة" . GeeksForGeeks . 27 مايو 2011. مؤرشف من الأصل في 3 أغسطس 2025.

[28] يي، ريتشارد. "1D1D DP: تحسين البرمجة الديناميكية" . مؤرشف من الأصل في 16 يناير 2024.

[29] هيرشبرغ، دانيال س.؛ لارمور، لورانس ل. (1985)، مسألة المتتالية الفرعية ذات الوزن الأدنى ، جامعة كاليفورنيا في إرفاين: كلية دونالد برين لعلوم المعلومات والحاسوب{{citation}}: CS1 maint: publisher location ( link )

[30] ميلكمان، أفراهام أ. (1987). "الإنشاء الفوري للغلاف المحدب لخط متعدد بسيط" . رسائل معالجة المعلومات . 25 (1): 11-12 . doi : 10.1016/0020-0190(87)90086-X . MR 0896397 .

[31] لي، فاجي؛ كليت، راينهارد (2011). "الأغلفة المحدبة في المستوى". أقصر المسارات الإقليدية . لندن: سبرينغر لندن. doi : 10.1007/978-1-4471-2256-2_4 . ISBN 978-1-4471-2255-5تم الاطلاع عليه بتاريخ 10 فبراير 2026 .

[32] ألوبيس، جريج. "تاريخ خوارزميات الغلاف المحدب الخطي للمضلعات البسيطة" . مختبر الهندسة الحسابية في جامعة ماكجيل . جامعة ماكجيل . تم الاطلاع عليه بتاريخ 10 فبراير 2026 .

[jacm-33] بلوموف، روبرت د.؛ ليسرسون، تشارلز إي. (1999). "جدولة العمليات الحسابية متعددة الخيوط عن طريق سرقة العمل". مجلة ACM . 46 (5): 720-748 . doi : 10.1145/324133.324234 . S2CID 5428476 .

[34] كريسبي-ريغيزي، ستيفانو؛ سان بيترو، بييرلويجي (2020). "آلات الطابور المزدوج، واللغات، وتمثيلات الرسوم البيانية المستوية". علوم الحاسوب النظرية . 834 : 43-59 . doi : 10.1016/j.tcs.2020.02.029 .

[ 1 ]

[ أ ]

[ ب ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ ج ]

[ 7 ]

[

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ د ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗