ما هي بنية بيانات قائمة الانتظار في بايثون؟



ستزودك هذه المقالة بمعرفة مفصلة وشاملة لهياكل بيانات قائمة الانتظار في بايثون مع الكثير من الأمثلة.

نظرًا لأنك درست بالفعل حول أهمية هياكل البيانات في المقالة السابقة ، فلنغوص في موضوع المقالة ، أي بنية بيانات قائمة الانتظار. سأناقش المواضيع التالية:

الحاجة إلى بنية بيانات قائمة الانتظار

افترض أنك تريد فيلمًا يومًا ما. في المجمع ، تم إصدار التذاكر على أساس First-Come-First-Serve وكان الناس يقفون وراء بعضهم البعض في انتظار دورهم. لذلك ماذا ستفعل؟؟ لابد أنك ذهبت إلى الخلف ووقفت خلف آخر شخص ينتظر التذكرة.





queue-data-structure

هنا ، يقف الناس واحدًا خلف الآخر ويتم خدمتهم بناءً على أول ما يدخل أولًا يخرج (FIFO) آلية. يُعرف هذا الترتيب باسم طابور.



أمثلة من الحياة اليومية في قائمة الانتظار

دعنا نفكر في بعض الأمثلة حيث نجد نوع قائمة الانتظار يعمل في الحياة اليومية:

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

كل هذه الأمثلة تتبع لأول مرة في الخروج الماضي إستراتيجية.

إنشاء هيكل بيانات قائمة الانتظار

بصرف النظر عن العمليات التكميلية ، قد أقول إن العمليات الرئيسية الممكنة في قائمة الانتظار هي:



واحد. En- قائمة الانتظار أو إضافة عنصر إلى نهاية قائمة الانتظار.

2. إلغاء الطابور أو إزالة عنصر من مقدمة قائمة الانتظار

الآن ، دعنا نبدأ من خلال إنشاء قائمة انتظار الفصل في بايثون:

class Queue: def __init __ (self، max_size): self .__ max_size = max_size self .__ العناصر = [None] * self .__ max_size self .__ الخلفية = -1 self .__ front = 0
  • اقصى حجم هو الحد الأقصى لعدد العناصر المتوقعة في قائمة الانتظار.
  • يتم تخزين عناصر قائمة الانتظار في قائمة بيثون
  • يشير الخلفية إلى موضع الفهرس الخاص بالعنصر الأخير في قائمة الانتظار.
  • يتم اعتبار الجزء الخلفي في البداية -1 لأن قائمة الانتظار فارغة
  • يشير Front إلى موضع العنصر الأول في قائمة الانتظار.
  • يتم اعتبار الواجهة الأمامية 0 في البداية لأنها ستشير دائمًا إلى العنصر الأول في قائمة الانتظار

قائمة الانتظار

الآن ، عندما تحاول إدراج العناصر في قائمة الانتظار ، عليك أن تتذكر النقاط التالية:

  • ما إذا كانت هناك مساحة متبقية في قائمة الانتظار أم لا ، أي إذا كانت الخلفية تساوي max_size -1
  • سيشير الجزء الخلفي إلى آخر عنصر تم إدراجه في قائمة الانتظار.

إذن ، ماذا ستكون الخوارزمية ؟؟

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns قيمة bool سواء كانت قائمة الانتظار ممتلئة أم لا ، True if full and False وإلا def is_full (self): return self .__ rear == self .__ max_size-1 # يُدرج / يُدرج بيانات في قائمة الانتظار إلى قائمة الانتظار إذا لم تكن قائمة تعريف كاملة (self ، data): if (self.is_full ()): print ('Queue is full. لا توجد قائمة enqueue ممكنة') else: self .__ rear + = 1 self. __elements [self .__ rear] = البيانات # عرض كل محتوى عرض تعريف قائمة الانتظار (ذاتي): لـ i في النطاق (0 ، ذاتي .__ خلفي + 1): طباعة (self .__ العناصر [i]) # يمكنك استخدام أدناه __str __ () لطباعة عناصر كائن DS أثناء تصحيح أخطاء def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

الآن ، عندما تقوم بتنفيذ ما يلي:

queue1 = قائمة الانتظار (5)

#Enqueue كل العناصر المطلوبة.

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

queue1.display ()

queue1.enqueue ('F')

طباعة (قائمة الانتظار 1)

انتاج:

إلى

ب

تحويل الكائن إلى مجموعة php

ج

د

يكون

قائمة الانتظار ممتلئة. لا يوجد قائمة قائمة ممكنة

بيانات قائمة الانتظار (من الأمام إلى الخلف): A B C D E.

دي-كيو

الآن ، نظرًا لأنك أدخلت / أدرجت العناصر في قائمة الانتظار ، فأنت تريد إزالة / حذفها من المقدمة ، لذلك عليك الاهتمام بما يلي:

  • هناك عناصر في قائمة الانتظار ، أي يجب ألا تكون الخلفية مساوية لـ -1.
  • ثانيًا ، عليك أن تتذكر أنه عندما يتم حذف العناصر من المقدمة ، يجب أن تزداد بعد حذف الواجهة بحيث تشير إلى المقدمة التالية.
  • يجب ألا تشير الواجهة الأمامية إلى نهاية قائمة الانتظار ، أي يساوي الحد الأقصى للحجم.

إذن ، ماذا ستكون الخوارزمية ؟؟

#function للتحقق مما إذا كانت قائمة الانتظار فارغة أم لا def is_empty (self): if (self .__ rear == - 1 أو self .__ front == self .__ max_size): إرجاع True else: إرجاع False #function لإلغاء عنصر وإرجاع it def dequeue (self): if (self.is_empty ()): print ('queue is already blank') else: data = self .__ العناصر [self .__ front] self .__ front + = 1 إرجاع البيانات #function لعرض العناصر من من الأمام إلى الخلف إذا لم تكن قائمة الانتظار فارغة ، عرض def (ذاتي): if (not self.is_empty ()): لـ i في النطاق (self .__ الأمامية ، self .__ الخلفية + 1): print (self .__ العناصر [i]) else : طباعة ('قائمة انتظار فارغة')

الآن عندما تقوم بتنفيذ ما يلي:

queue1 = قائمة الانتظار (5)

#Enqueue كل العناصر المطلوبة

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

طباعة (قائمة الانتظار 1)

#Dequeue كل العناصر المطلوبة

print ('Dequeued:' ، queue1.dequeue ())

print ('Dequeued:' ، queue1.dequeue ())

print ('Dequeued:' ، queue1.dequeue ())

print ('Dequeued:' ، queue1.dequeue ())

اذهب للعمل في بيثون

print ('Dequeued:' ، queue1.dequeue ())

print ('Dequeued:' ، queue1.dequeue ())

# عرض جميع العناصر الموجودة في قائمة الانتظار.

queue1.display ()

انتاج:

بيانات قائمة الانتظار (من الأمام إلى الخلف): A B C D E.

مطرود: أ

مطرود: ب

ديكويد: ج

مطرود: د

مطرود: E

قائمة الانتظار فارغة بالفعل

غير مؤهل: لا شيء

قائمة انتظار فارغة

تطبيقات قائمة الانتظار

اعتبارًا من الآن ، لقد فهمت بالفعل أساسيات قائمة الانتظار. الآن للتعمق أكثر سننظر في بعض تطبيقاته.

  • مثال 1:

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

لنفترض أنك أصدرت أوامر طباعة لثلاث مستندات بالترتيب doc1 ، متبوعًا بـ doc2 و doc3.
سيتم ملء قائمة انتظار الطباعة كما هو موضح أدناه:

doc-n ، حيث يكون المستند هو المستند المرسل للطباعة و n ، هو عدد الصفحات في المستند. على سبيل المثال ، تعني doc2-10 أن doc2 ستتم طباعته ويتكون من 10 صفحات. إليك رمز يحاكي عملية قائمة انتظار الطباعة. انتقل من خلال الكود ولاحظ كيفية استخدام قائمة الانتظار في هذا التنفيذ.

class Queue: def __init __ (self، max_size): self .__ max_size = max_size self .__ العناصر = [None] * self .__ max_size self .__ الخلفية = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): إرجاع إرجاع صحيح False def is_empty (self): if (self .__ front> self .__ rear): إرجاع إرجاع صحيح False def enqueue (self، data): if (self.is_full ()): print ('Queue is full !!!') else: self .__ rear + = 1 self .__ العناصر [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Queue is blank! !! ') else: data = self .__ العناصر [self .__ front] self .__ front + = عرض رقم تعريف بيانات إرجاع واحد (ذاتي): للفهرس في النطاق (self .__ الأمامي ، النفس .__ الخلفي + 1): print (self .__ العناصر [index]) def get_max_size (self): return self .__ max_size # يمكنك استخدام أدناه __str __ () لطباعة عناصر كائن DS أثناء #debugging def __str __ (self): msg = [] index = self .__ front while (فهرس<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()

انتاج:

تم إرسال doc1-5 للطباعة

doc2-3 أرسلت للطباعة

doc3-6 أرسلت للطباعة

تم طباعة الوثيقة doc1-5

المتبقي لا. عدد الصفحات في الطابعة: 7

تم طباعة doc2-3

المتبقي لا. عدد الصفحات في الطابعة: 4

تعذرت طباعة doc3. لا توجد صفحات كافية في الطابعة

  • المثال الثاني:

دعونا نحاول فهم مثال آخر يستخدم بنية بيانات قائمة الانتظار. هل يمكنك محاولة فهم الكود ومعرفة ما تقوم به الوظيفة التالية؟

  1. متعة مواطنه (اسم):
  2. aqueue = طابور (100)
  3. لعدد في النطاق (1 ، ن + 1):
  4. قائمة (عدد)
  5. النتيجة = 1
  6. بينما (ليس (aqueue.is_empty ())):
  7. عدد = AQUUE.DEQUEUE ()
  8. النتيجة * = الأسطوانات
  9. طباعة (نتيجة)

عندما يتم استدعاء وظيفة fun () بتمرير n ،

  • الأسطر 2 إلى 4 en- قائمة العناصر من 1 إلى n
  • تجد الأسطر من 5 إلى 8 ناتج هذه العناصر عن طريق فصلها واحدًا تلو الآخر

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

لديك سؤال لنا؟ يرجى ذكر ذلك في قسم التعليقات بهذه المقالة وسنعاود الاتصال بك في أقرب وقت ممكن.

للحصول على معرفة متعمقة حول Python مع تطبيقاتها المختلفة ، يمكنك التسجيل في البث المباشر مع دعم 24/7 والوصول مدى الحياة.