قائمة الانتظار (نوع بيانات مجرد)

يمكن تنفيذ قوائم الانتظار كنوع بيانات منفصل، أو اعتبارها حالة خاصة من قائمة انتظار ثنائية الطرف (deque) دون تنفيذها بشكل منفصل. على سبيل المثال، تسمح لغتا بيرل وروبي بإضافة عناصر إلى مصفوفة وحذفها منها من كلا الطرفين، لذا يمكن استخدام دالتي `add` و` deque` لإضافة عناصر إلى قائمة وحذفها منها (أو العكس )، ^{[ 2 ]} على الرغم من أن هذه العمليات قد لا تكون فعالة في بعض الحالات.push()shift()unshift()pop()

توفر مكتبة القوالب القياسية في لغة C++ std::queue<T>فئةً مُنمّطة تقتصر على عمليات الإضافة/الحذف فقط. ومنذ إصدار J2SE 5.0، تحتوي مكتبة Java على Queueواجهة تُحدد عمليات قائمة الانتظار؛ وتشمل الفئات المُنفذة لها LinkedList(منذ J2SE 1.6) ArrayDeque. أما PHP، فتضم فئة SplQueue ومكتبات خارجية مثل beanstalk'd و Gearman .

قائمة انتظار بسيطة مُنفذة بلغة TypeScript :

class Queue <T> { private items : T [] = [ ] ;enqueue ( element : T ) : void { this.items.push ( element ) ; }​​​dequeue ( ) : T | undefined { return this.items.shift ( ) ; }​isEmpty ( ) : boolean { return this.items.length === 0 ; } }​​​

يتم تخزين بيانات هذا الطابور في قائمتين مرتبطتين بشكل فردي باسم${\displaystyle f}$و${\displaystyle r}$القائمة${\displaystyle f}$يحتل الجزء الأمامي من الطابور. القائمة${\displaystyle r}$يحتفظ هذا الجزء بالعناصر المتبقية (أي الجزء الخلفي من الطابور) بترتيب عكسي . من السهل إضافته إلى مقدمة الطابور عن طريق إضافة عقدة في بدايته.${\displaystyle f}$وإذا${\displaystyle r}$إذا لم تكن فارغة، فمن السهل إزالتها من نهاية قائمة الانتظار عن طريق إزالة العقدة الموجودة في رأسها.${\displaystyle r}$. متى${\displaystyle r}$القائمة فارغة${\displaystyle f}$يتم عكسها وتخصيصها لـ${\displaystyle r}$ثم رئيس${\displaystyle r}$تمت إزالته.

تستغرق عملية الإدراج ("enqueue") دائمًا${\displaystyle O(1)}$يستغرق الأمر بعض الوقت. عملية الإزالة ("إزالة العنصر من قائمة الانتظار")${\displaystyle O(1)}$عندما القائمة${\displaystyle r}$ليس فارغًا. عندما${\displaystyle r}$إذا كان فارغًا، فإن العكس هو الصحيح${\displaystyle O(n)}$أين${\displaystyle n}$هو عدد العناصر في${\displaystyle f}$لكن يمكننا القول إنه كذلك${\displaystyle O(1)}$الوقت المستهلك ، لأن كل عنصر في${\displaystyle f}$كان لا بد من إدراجه ويمكننا تعيين تكلفة ثابتة لكل عنصر في الاتجاه المعاكس لوقت إدراجه.

تحقق قائمة الانتظار في الوقت الفعلي${\displaystyle O(1)}$الوقت اللازم لجميع العمليات، دون احتساب الاستهلاك. ستكون هذه المناقشة فنية، لذا تذكر ذلك، بالنسبة لـ${\displaystyle l}$قائمة،${\displaystyle |l|}$يدل على طوله، ذلك${\displaystyle {\texttt {null}}}$يمثل قائمة فارغة و${\displaystyle {\texttt {cons}}(h,t)}$يمثل القائمة التي رأسها${\displaystyle h}$والذي ذيله${\displaystyle t}$.

تتكون بنية البيانات المستخدمة لتنفيذ قوائم الانتظار لدينا من ثلاث قوائم مرتبطة بشكل فردي.${\displaystyle (f,r,s)}$أين${\displaystyle f}$هو مقدمة الصف و${\displaystyle r}$يمثل الجزء الخلفي من الطابور بترتيب عكسي. الثابت في هذا الهيكل هو أن${\displaystyle s}$الجزء الخلفي من${\displaystyle f}$بدونها${\displaystyle |r|}$العناصر الأولى، أي${\displaystyle |s|=|f|-|r|}$ذيل الطابور${\displaystyle ({\texttt {cons}}(x,f),r,s)}$ثم يصبح الأمر تقريبًا${\displaystyle (f,r,s)}$وإدراج عنصر${\displaystyle x}$ل${\displaystyle (f,r,s)}$يكاد يكون${\displaystyle (f,{\texttt {cons}}(x,r),s)}$يقال ذلك تقريبًا، لأنه في كلتا النتيجتين،${\displaystyle |s|=|f|-|r|+1}$دالة مساعدة${\displaystyle {\texttt {aux}}}$يجب استدعاء الدالة بعد ذلك لكي يتحقق الشرط الثابت. يجب النظر في حالتين، اعتمادًا على ما إذا كان${\displaystyle s}$القائمة فارغة، وفي هذه الحالة${\displaystyle |r|=|f|+1}$أو لا. التعريف الرسمي هو${\displaystyle {\texttt {aux}}(f,r,{\texttt {cons}}(\_,s))=(f,r,s)}$و${\displaystyle {\texttt {aux}}(f,r,{\texttt {null}})=(f',{\texttt {null}},f')}$أين${\displaystyle f'}$يكون${\displaystyle f}$ثم يتبع ذلك${\displaystyle r}$معكوسة.

دعونا نتصل${\displaystyle {\texttt {reverse}}(f,r)}$الدالة التي تُرجع${\displaystyle f}$ثم يتبع ذلك${\displaystyle r}$معكوسة. لنفترض كذلك أن${\displaystyle |r|=|f|+1}$، لأن هذا هو الحال عند استدعاء هذه الدالة. وبشكل أدق، نُعرّف دالة كسولة.${\displaystyle {\texttt {rotate}}(f,r,a)}$والتي تأخذ كمدخل ثلاث قوائم بحيث${\displaystyle |r|=|f|+1}$، وإرجاع سلسلة من${\displaystyle f}$، ل${\displaystyle r}$معكوسة و${\displaystyle a}$. ثم${\displaystyle {\texttt {reverse}}(f,r)={\texttt {rotate}}(f,r,{\texttt {null}})}$التعريف الاستقرائي للدوران هو${\displaystyle {\texttt {rotate}}({\texttt {null}},{\texttt {cons}}(y,{\texttt {null}}),a)={\texttt {cons}}(y,a)}$و${\displaystyle {\texttt {rotate}}({\texttt {CONS}}(x,f),{\texttt {cons}}(y,r),a)={\texttt {cons}}(x,{\texttt {rotate}}(f,r,{\texttt {null}}(y,a)))}$مدة تشغيله هي${\displaystyle O(r)}$ولكن، نظرًا لاستخدام التقييم الكسول، يتم تأخير الحساب حتى يتم فرض النتائج بواسطة الحساب.

القائمة${\displaystyle s}$لهذه القائمة في بنية البيانات غرضان. فهي بمثابة عداد لـ${\displaystyle |f|-|r|}$، بالفعل،${\displaystyle |f|=|r|}$إذا وفقط إذا${\displaystyle s}$هي القائمة الفارغة. يسمح لنا هذا العداد بالتأكد من أن القائمة الخلفية لا تتجاوز القائمة الأمامية أبدًا. علاوة على ذلك، باستخدام${\displaystyle s}$، وهو ذيل لـ${\displaystyle f}$، يجبر على حساب جزء من القائمة (الكسولة)${\displaystyle f}$خلال كل${\displaystyle tail()}$و${\displaystyle insert()}$العملية. لذلك، عندما${\displaystyle |f|=|r|}$القائمة${\displaystyle f}$الأمر مفروض تمامًا. لو لم يكن كذلك، لكان التمثيل الداخلي لـ${\displaystyle f}$قد يكون الأمر عبارة عن إضافة لإضافات لإضافات لإضافات أخرى، ولن تكون عملية الإجبار عملية ثابتة الوقت بعد الآن.

•  تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "الطابور المحدود" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .