מהו מבנה נתוני תורים בפייתון?

כפי שכבר למדתם על חשיבותם של מבני נתונים במאמר הקודם, בואו לצלול נכון לנושא המאמר כלומר מבנה נתוני תור. אדון בנושאים הבאים:

• צורך במבנה נתוני תור
• דוגמאות לחיי היומיום לתור
• יצירת מבנה נתוני תור
• תור בתור
• דה-תור
• יישומים של תור

צורך במבנה נתוני תור

נניח שאתה רוצה לסרט יום אחד. במולטיפלקס הונפקו הכרטיסים על בסיס 'כל הקודם זוכה' ואנשים עמדו אחד אחרי השני והמתינו לתורם. אז מה תעשה?? בטח הלכת מאחור ונעמדת מאחורי האדם האחרון שחיכה לכרטיס.

דוגמה לחסימה סטטית בג'אווה

הנה, האנשים עומדים אחד אחרי השני והם מטופלים על בסיס ראשית בכניסה ראשונה (FIFO) מַנגָנוֹן. הסדר כזה מכונה א תוֹר.

דוגמאות לחיי היומיום לתור

בואו ניקח בחשבון כמה דוגמאות בהן אנו עובדים על סוג התור בחיי היומיום:

• מערכת מענה טלפונית- אדם שמתקשר ראשון לגאדג'ט שלך משתתף ראשון.
• מכונת בדיקת מזוודות - בודק את המזוודות שנשמרו לראשונה על המסוע.
• כלי רכב על גשר מס האגרה - הרכבים המגיעים מוקדם יוצאים תחילה.
• מוקד טלפוני - מערכות טלפון ישתמשו בתורים כדי לקיים סדר על אנשים שמתקשרים אליהם עד שנציג השירות יהיה בחינם.

כל הדוגמאות הללו עוקבות אחר כך ראשונה אחרונה אִסטרָטֶגִיָה.

יצירת מבנה נתוני תור

מלבד הפעולות המשלימות, אני יכול לומר שהפעולות העיקריות האפשריות בתור הן:

אחד. תור בתור או הוסף אלמנט בסוף התור.

2. דה-תור או הסר אלמנט מקדמת התור

עכשיו, נתחיל באמצעות יצירת תור בכיתה בפייתון:

תור מחלקה: def __init __ (עצמי, מקס_גודל): עצמי .__ max_size = max_size עצמי .__ אלמנטים = [אין] * עצמי .__ max_size עצמי .__ אחורי = -1 עצמי .__ חזית = 0

• גודל מקסימלי הוא המספר המרבי של אלמנטים הצפויים בתור.
• אלמנטים בתור מאוחסנים ברשימת הפיתונים
• אחורי מציין את מיקום האינדקס של האלמנט האחרון בתור.
• החלק האחורי נלקח בתחילה כ -1 מכיוון שהתור ריק
• חזית מציינת את מיקום האלמנט הראשון בתור.
• החלק הקדמי נלקח להיות 0 בהתחלה מכיוון שהוא תמיד יצביע על האלמנט הראשון בתור

Enqueue

כעת, כשאתה מנסה לצרף אלמנטים לתור, עליך לזכור את הנקודות הבאות:

• בין אם נותר מקום בתור ובין אם לא, כלומר אם האחורי שווה למקס_גודל -1
• החלק האחורי יצביע על האלמנט האחרון שהוכנס בתור.

אז מה יהיה האלגוריתם ??

# חוזר max_size של תור def get_max_size (עצמי): להחזיר self .__ max_size # returns ערך bool בין אם התור מלא או לא, נכון אם מלא ושקר אחרת def is_full (self): return self .__ rear == self .__ max_size-1 # מכניס / עוקב נתונים לתור אם הוא לא מלא להגדרת ערך (עצמי, נתונים): אם (self.is_full ()): הדפס ('התור מלא. אין אפשרות לתצוגה') אחר: עצמי .__ אחורי + = 1 עצמי. __elements [self .__ rear] = data # הצג את כל התוכן של תצוגת def def (עצמי): עבור i בטווח (0, עצמי .__ אחורי + 1): הדפס (אלמנטים__. עצמית [i]) # אתה יכול להשתמש ב למטה __str __ () להדפסת האלמנטים של אובייקט DS תוך ניפוי באגים def __str __ (עצמי): 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

כעת, כאשר אתה מבצע את הפעולות הבאות:

תור 1 = תור (5)

# תעד את כל האלמנטים הדרושים.

תור1. אנקווה ('A')

תור1. אנקווה ('B')

תור1. אנקווה ('C')

תור1. אנקווה ('D')

תור1. אנקווה ('E')

queue1.display ()

תור1. אנקווה ('F')

הדפס (תור 1)

תְפוּקָה:

ל

ב

ג

ד

IS

התור מלא. אין אפשרות להפסיק

נתוני תור (קדמי לאחורי): A B C D E

דה-תור

כעת, לאחר שהכנסת / אטמת את האלמנטים בתור, ברצונך להסיר אותם / למחוק אותם מלפנים, לכן עליך לדאוג למעקב:

• יש אלמנטים בתור, כלומר האחורי לא צריך להיות שווה ל- -1.
• שנית, עליכם לזכור שככל שאלמנטים נמחקים מלפנים כך, לאחר מחיקת חזית יש להגדיל אותה לכיוון חזית הבאה.
• החלק הקדמי לא אמור לכוון לסוף התור, כלומר שווה ל- max_size.

אז מה יהיה האלגוריתם ??

# פונקציה כדי לבדוק אם התור ריק או שאינו def הוא_פנוי (עצמי): אם (עצמי .__ אחורי == - 1 או עצמי .__ קדמי == עצמי .__ מקס_גודל): להחזיר נכון אחר: להחזיר False # פונקציה לביצוע אלמנט וחזרה זה def dequeue (עצמי): אם (self.is_empty ()): הדפס ('התור כבר ריק') אחר: נתונים = עצמי .__ אלמנטים [עצמי .__ קדמי] עצמי .__ חזית + = 1 החזרת נתונים # פונקציה להצגת אלמנטים מ מקדימה לאחורה אם התור אינו ריק תצוגת def (עצמי): אם (לא self.is_empty ()): עבור אני בטווח (עצמי .__ קדמי, עצמי .__ אחורי + 1): הדפס (אלמנטים .__ עצמית [i]) אחר : הדפס ('תור ריק')

עכשיו כשאתה מבצע את הפעולות הבאות:

תור 1 = תור (5)

# פתח את כל האלמנטים הדרושים

תור1. אנקווה ('A')

תור1. אנקווה ('B')

תור1. אנקווה ('C')

תור1. אנקווה ('D')

תור1. אנקווה ('E')

מה זה קונסטרוקטור בפיתון

הדפס (תור 1)

# תייג את כל האלמנטים הדרושים

הדפס ('Dequeued:', queue1.dequeue ())

הדפס ('Dequeued:', queue1.dequeue ())

הדפס ('Dequeued:', queue1.dequeue ())

הדפס ('Dequeued:', queue1.dequeue ())

הדפס ('Dequeued:', queue1.dequeue ())

הדפס ('Dequeued:', queue1.dequeue ())

# הצג את כל האלמנטים בתור.

queue1.display ()

תְפוּקָה:

נתוני תור (קדמי לאחורי): A B C D E

מדורגים: א

מוריד: ב

מדורגים: ג

העמסת יתר של השיטה לעומת עקיפת השיטה

מדורגים: ד

מדורגים: ה

התור כבר ריק

מוריד: אין

תור ריק

יישומים של תור

נכון לעכשיו, כבר הבנתם את יסודות התור. עכשיו כדי לצלול עמוק יותר נבחן כמה מהיישומים שלה.

• דוגמה 1:

תור הדפסה ב- Windows משתמש בתור לאחסון כל עבודות ההדפסה הפעילות והממתינות. כשאנחנו רוצים להדפיס מסמכים, אנו מוציאים פקודות הדפסה בזו אחר זו. בהתבסס על פקודות ההדפסה, המסמכים יעמדו בשורה בתור ההדפסה. כאשר המדפסת מוכנה, המסמך ישלח תחילה בכניסה הראשונה כדי להדפיסו.

נניח שהנפקת פקודות הדפסה עבור 3 מסמכים בהזמנה doc1, ואחריה doc2 ו- doc3.
תור ההדפסה יאוכלס כמוצג להלן:

doc-n, כאשר המסמך הוא המסמך שנשלח להדפסה ו- n, הוא מספר העמודים במסמך. לדוגמא, doc2-10 פירושו ש- doc2 יש להדפיס ויש בו 10 עמודים. הנה קוד המדמה פעולת תור הדפסה. עברו על הקוד וצפו כיצד משתמשים בתור ביישום זה.

תור כיתה: def __init __ (עצמי, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = עצמי .__ max_size-1): להחזיר חזרה אמיתית שקר def הוא_אפס (עצמי): אם (עצמי .__ קדמי> עצמי .__ אחורי): להחזיר חזרה אמיתית שגיאה def def (עצמי, נתונים): אם (self.is_full ()): הדפס ('התור מלא !!!') אחר: עצמי .__ אחורי + = 1 עצמי .__ אלמנטים [עצמי .__ אחורי] = שער הגדרת נתונים (עצמי): אם (self.is_empty ()): הדפס ('התור ריק! !! ') אחר: נתונים = אלמנטים .__ עצמית [עצמי .__ קדמי] עצמי .__ קדמי + = 1 תצוגת הגדרת נתונים חזרה (עצמי): לאינדקס בטווח (עצמי .__ קדמי, עצמי .__ אחורי + 1): הדפס (אלמנטים .__ עצמית) [אינדקס]) def get_max_size (עצמי): להחזיר את עצמי .__ max_size # ניתן להשתמש בהמשך __str __ () כדי להדפיס את האלמנטים של אובייקט DS בעוד ש- defebging def __str __ (עצמי): msg = [] index = self .__ חזית בעוד (אינדקס<=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. אין מספיק עמודים במדפסת

• דוגמה 2:

בואו ננסה להבין דוגמה נוספת המשתמשת במבנה נתוני התור. האם אתה יכול לנסות להבין את הקוד ולספר מה הפונקציה הבאה עושה?

1. כיף בהחלט (n):
2. aqueue = תור (100)
3. עבור מספר בטווח (1, n + 1):
4. enqueue (num)
5. תוצאה = 1
6. בעוד (לא (aqueue.is_empty ())):
7. מספר = AQUUE.DEQUEUE ()
8. תוצאה * = מספר
9. הדפס (תוצאה)

כאשר פונקציה fun () מופעלת על ידי העברת n,

• שורות 2 עד 4 מציבות בתור את האלמנטים מ -1 עד n
• שורות 5 עד 8 מוצאות את התוצר של אותם אלמנטים על ידי ביטול תור זה אחד אחד

עם זאת, אנו מגיעים לסוף מאמר זה במבנה נתוני התור. אם הבנת וניהלת את הקודים בעצמך בהצלחה אתה כבר לא מתחיל במבנה נתוני התור.

יש לך שאלה עבורנו? אנא הזכיר זאת בסעיף ההערות במאמר זה ונחזור אליך בהקדם האפשרי.

כדי לקבל ידע מעמיק על Python יחד עם היישומים השונים שלו, אתה יכול להירשם לשידור חי עם תמיכה 24/7 וגישה לכל החיים.