מה זה תור?
פרָאק הם מבני נתונים המשמשים לאחסון ושליפה של אלמנטים בסדר קבוע מראש. זהו מבנה נתונים ליניארי הדומה למחסנית ונצמד ל- FIFO (כניסה ראשונה, יוצאת ראשונה) כְּלָל. אפשר להשוות את זה לרשימת המתנה או לתור שבו הראשון שמגיע מקבל שירות ראשון. רכיבים קיימים נשמטים מחזית ה- תוֹר , ואלמנטים חדשים מתווספים מאחור.
יישום תור בגולנג
יישום א תוֹר in Go פשוט ויעיל וניתן ליישם אותו באמצעות ארבע השיטות הבאות.
1: פרוסות
בגו, א פרוסה הוא מערך דינמי שיכול להשתנות בגודלו. ליישם א תוֹר באמצעות א פרוסה , נוכל להוסיף אלמנטים לחלק האחורי של פרוסה באמצעות פונקציית התוספת המובנית והסר אלמנטים מחזית ה- פרוסה באמצעות חיתוך.
גישה זו קלה לבנייה ומציעה ביצועים טובים לפעולות הוספה וחיתוך הודות לפרוסות המובנות של Go. עם זאת, שיטת החיתוך, הכוללת העתקת רכיבים למערך בסיס חדש עלולה להפוך ללא יעילה אם תוֹר מרחיב ומצריך פעולות ביטול תור חוזרות ונשנות.
הקוד הבא מגדיר את תוֹר יישום באמצעות פרוסה ב-Go.
החבילה הראשית
יְבוּא 'fmt'
func main ( ) {
תוֹר := עשה ( [ ] מִמְשָׁק { } , 0 )
תוֹר = לְצַרֵף ( תוֹר , 'אנגלית' )
תוֹר = לְצַרֵף ( תוֹר , 'אורדו' )
תוֹר = לְצַרֵף ( תוֹר , 'מתמטיקה' )
אם רק ( תוֹר ) > 0 {
פריט := תוֹר [ 0 ]
תוֹר = תוֹר [ 1 : ]
fmt. Println ( פריט )
}
אם רק ( תוֹר ) == 0 {
fmt. Println ( 'התור ריק' )
} אַחֵר {
fmt. Println ( תוֹר )
}
}
קוד ה-Go לעיל משתמש ב-Slice כדי לבנות קוד פשוט תוֹר מבנה נתונים. ה לְצַרֵף() הפונקציה משמשת לרישום אלמנטים לתוך תוֹר Slice, ופעולת Slice שמסירת את האלמנט הראשוני משמשת לתור אותם. עם fmt.Println() , האלמנט שהוצא בתור מודפס. לאחר מכן הקוד משתמש ב- רק() פונקציה כדי לקבוע אם התור ריק, ואם כן, הוא כותב ' תוֹר הוא ריק' באמצעות הפונקציה fmt.Println().
תְפוּקָה
2: רשימות מקושרות
צמתים הנושאים ערך ומצביע לצומת הבא ברשימה מרכיבים רשימה מקושרת. עם שני מצביעים, אחד מצביע לקדמת (ראש) הרשימה והשני מצביע לאחור (זנב), נוכל ליישם תוֹר באמצעות רשימה מקושרת. הסרת פריט מהתור (יציאה מהתור) כרוכה בהסרת הצומת בקדמת הרשימה בעוד שהוספת פריט לתור (עמידה בתור) כרוכה בהוספת צומת חדש בחלק האחורי של הרשימה.
שיטה זו מאפשרת פעולות יעילות של עמידה בתור ויציאה בתור, מכיוון שצריך לשנות רק את מצביעי הראש והזנב, בניגוד לפתרון המבוסס על פרוסות שבו יהיה צורך להעתיק אלמנטים.
השתמש ברשימה מקושרת כדי ליישם א תוֹר על ידי שימוש בקוד שסופק להלן:
החבילה הראשיתיְבוּא 'fmt'
הקלד Node struct {
ממשק ערך { }
הַבָּא * צוֹמֶת
}
הקלד תור struct {
רֹאשׁ * צוֹמֶת
זָנָב * צוֹמֶת
}
func main ( ) {
תוֹר := & תוֹר { רֹאשׁ : אֶפֶס , זָנָב : אֶפֶס }
newNode := & צוֹמֶת { ערך : 'אנגלית' , הַבָּא : אֶפֶס }
תוֹר. זָנָב = newNode
תוֹר. רֹאשׁ = newNode
newNode = & צוֹמֶת { ערך : 'אורדו' , הַבָּא : אֶפֶס }
תוֹר. זָנָב . הַבָּא = newNode
תוֹר. זָנָב = newNode
newNode = & צוֹמֶת { ערך : 'מתמטיקה' , הַבָּא : אֶפֶס }
תוֹר. זָנָב . הַבָּא = newNode
תוֹר. זָנָב = newNode
אם תוֹר. רֹאשׁ != אֶפֶס {
פריט := תוֹר. רֹאשׁ . ערך
תוֹר. רֹאשׁ = תוֹר. רֹאשׁ . הַבָּא
fmt. Println ( פריט )
}
אם תוֹר. רֹאשׁ == אֶפֶס {
fmt. Println ( 'התור ריק' )
}
}
מבנה הצומת מייצג כל פריט בתור ומכיל שני שדות: שדה ערך לאחסון ערך הפריט, והשדה הבא להצבעה על הפריט הבא בתור. מבנה התור משתמש במאפייני ראש וזנב כדי לעקוב אחר החלק הקדמי והאחורי של התור, בהתאמה. ה פרָאק פריט ראשון מסומן על ידי תכונת הראש, בעוד שהפריט האחרון שלו מצוין על ידי תכונת הזנב.
הפרמטרים של הראש והזנב מוגדרים תחילה ל אֶפֶס כאשר חדש תוֹר נוצר בפונקציה main() . מצביעי הראש והזנב מתעדכנים כדי להוסיף שלושה צמתים ל- תוֹר עם הערכים 'אנגלית', 'אורדו', ו 'מתמטיקה'. ה 'אנגלית' פריט הוא אז 'תורם' (הוסר) מהחזית של תוֹר על ידי הצגת הערך שלו והקדמת מצביע הראש לצומת הבא ב- תוֹר . לאחר ביטול התור, אם הראש הופך לריק, זה אומר שהתור ריק, וההודעה ' תוֹר ריק' מודפס.
תְפוּקָה
3: מבנים
ב-Go, אתה יכול ליצור מבנה נתונים מותאם אישית הנקרא a struct לייצג את א תוֹר . זֶה struct יכולים להיות שדות לאחסון תוֹר אלמנטים ושיטות כדי להוסיף ולהסיר פריטים, לבדוק אם התור ריק ולקבל את גודל התור הנוכחי.
דרך זו ליצור א תוֹר in Go מציעה הטמעה נוחה ומובלעת עם שיטות קלות לשימוש שניתן להרחיב ולהתאים אישית עם תכונות נוספות. זוהי גישה גמישה המאפשרת לבצע שינויים ביישום או להוסיף יכולות חדשות בכל עת שיידרש.
יצירת התאמה אישית struct עם מתודות כרוך בכתיבת קוד נוסף בהשוואה לשתי הדרכים האחרות, מה שעשוי להגביר את המורכבות. עם זאת, זה גם מספק יותר גמישות ושליטה על היישום של תוֹר .
הדוגמה הבאה מציגה יצירת מבנה נתונים לייצוג א תוֹר ב-Go.
החבילה הראשיתיְבוּא 'fmt'
הקלד תור struct {
פריטים [ ] מִמְשָׁק { }
}
func ( ש * תוֹר ) תור ( ממשק פריט { } ) {
ש. פריטים = לְצַרֵף ( ש. פריטים , פריט )
}
func ( ש * תוֹר ) תור ( ) מִמְשָׁק { } {
אם רק ( ש. פריטים ) == 0 {
לַחֲזוֹר אֶפֶס
}
פריט := ש. פריטים [ 0 ]
ש. פריטים = ש. פריטים [ 1 : ]
לַחֲזוֹר פריט
}
func ( ש * תוֹר ) זה ריק ( ) bool {
לַחֲזוֹר רק ( ש. פריטים ) == 0
}
func ( ש * תוֹר ) גודל ( ) int {
לַחֲזוֹר רק ( ש. פריטים )
}
func main ( ) {
תוֹר := & תוֹר { פריטים : עשה ( [ ] מִמְשָׁק { } , 0 ) }
תוֹר. תור ( 'אנגלית' )
תוֹר. תור ( 'אורדו' )
תוֹר. תור ( 'מתמטיקה' )
פריט := תוֹר. תור ( )
fmt. Println ( פריט )
אם תוֹר. זה ריק ( ) {
fmt. Println ( 'התור ריק' )
}
גודל := תוֹר. גודל ( )
fmt. Println ( 'גודל התור:' , גודל )
}
בקוד לעיל, פריט מצורף לפרוסה של הפריט באמצעות ה- תור() שיטה, שמעבירה אותו לסוף ה- תוֹר . בעקבות ה נכנס ראשון, יוצא ראשון (FIFO) עקרון, ה Dequeue() השיטה מוציאה פריט מהחזית של תוֹר ומחזיר אותו. אורך פרוסת הפריט מסומן כחלק מה- זה ריק() בדוק את השיטה כדי לראות אם תוֹר זה ריק. על ידי החזרת אורך פרוסת הפריטים, ה גודל() השיטה מחזירה את הנוכחי פרָאק גודל.
הפונקציה main() משתמשת ב- מבנה תור כדי ליצור חדש תוֹר , הוסף לו אלמנטים, הסר ממנו פריטים, קבע אם ה תוֹר ריק, וחשב את גודלו.
תְפוּקָה
4: ערוצים
ב-Go, ניתן להשתמש בסוג הערוץ המובנה ליישום א תוֹר מבנה נתונים. ניתן ליצור את הערוץ עם גודל מאגר כדי להגביל את מספר האלמנטים שניתן להעמיד בתור בכל זמן נתון. כדי להוסיף אלמנט ל- תוֹר , ניתן לשלוח אותו לערוץ באמצעות <- מפעיל, בעוד כדי להסיר אלמנט מהתור, ניתן לקבל אותו מהערוץ באמצעות אותו מפעיל.
גישה זו יכולה להיות שימושית למדי במצבים שבהם גישה במקביל ל- תוֹר נדרש, מכיוון שערוצים בטוחים מטבעם לשימוש בו-זמני.
חשוב לזכור שערוצים של Go מוקלדים. זה אומר שאתה יכול לשלוח רק ערכים מסוג מסוים דרך ערוץ, ואתה יכול לקבל רק ערכים מאותו סוג מהערוץ.
זוהי המחשה כיצד להשתמש בערוץ כדי לבנות א תוֹר מבנה הנתונים ב-Go.
החבילה הראשיתיְבוּא (
'fmt'
'זְמַן'
)
הקלד תור struct {
ממשק הפריטים { }
}
funcNewQueue ( ) * תוֹר {
ש := & תוֹר {
פריטים : עשה ( ממשק צ'אן { } ) ,
}
לך ש. processItems ( )
לַחֲזוֹר ש
}
func ( ש * תוֹר ) processItems ( ) {
ל פריט := טווח q. פריטים {
אם פריט == 'אנגלית' {
fmt. Println ( 'תורן:' , פריט )
}
}
}
func ( ש * תוֹר ) תור ( ממשק פריט { } ) {
ש. פריטים <- פריט
}
funcmain ( ) {
תוֹר := תור חדש ( )
תוֹר. תור ( 'אנגלית' )
תוֹר. תור ( 'אורדו' )
תוֹר. תור ( 'מתמטיקה' )
זְמַן . לִישׁוֹן ( 2 * זְמַן . שְׁנִיָה )
}
הקוד לעיל יוצר א מבנה תור עם שדה בודד פריטים שהוא ערוץ של מִמְשָׁק{} סוּג. ה NewQueue() הפונקציה יוצרת מופע חדש של תוֹר ומאתחל את זה 'פריטים' שדה עם ערוץ חדש ללא מאגר. זה גם מתחיל גורוטינה חדשה כדי לעבד את הפריטים שנוספו לתור באמצעות processItems() פוּנקצִיָה. ה processItems() הפונקציה בודקת אם הפריט שהתקבל שווה ל 'אנגלית' ומדפיס הודעה לקונסולה עבור הפריט הזה בלבד. ה תור() הפונקציה משמשת להוספת פריטים חדשים לתור.
תְפוּקָה
סיכום
התור הוא מבנה נתונים חיוני ב-Go המשמש לאחסון ואחזור של אלמנטים בסדר מסוים. יישום א תוֹר in Go בטוח בשרשור, מה שהופך אותם לבחירה אידיאלית ליישום מקביל בתוכניות. ניתן ליישם אותו באמצעות פרוסות, רשימות מקושרות, מבנים וערוצים. הפרטים המלאים כבר מסופקים בהנחיות המפורטות לעיל.