כיצד להשתמש בתור C ++

מבוא

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

לאחר הסרת הפריט הראשון ברשימה המקורית, השני הופך לפריט הראשון. לאחר הסרת הפריט השני, השלישי הופך לפריט הראשון וכן הלאה.

דוגמה טובה למציאות של תור היא כאשר אנשים עומדים בתור לחכות לשירות או טוב. האדם הראשון מוגש ראשון לפני האחרון. עם זאת, התור עליו דיברו במדריך זה, הוא תור התוכנה, כפי שתוכנן ב- C ++.

FIFO

FIFO מייצג First-In, First-Out. זוהי דרך נוספת להעריך את התור. המשמעות היא שהפריט הראשון שנכנס לרשימה, הוא הפריט הראשון שיש להסיר, בכל פעם שתתבצע הסרה. תחילת הרשימה נקראת ראש או חזית; סוף הרשימה נקרא הגב או הזנב.

פעולות חיוניות

תור תוכנה חייב לכלול לפחות את הפעולות הבאות:

לִדחוֹף

פעולה זו, מוסיפה אלמנט חדש בחלק האחורי של התור. מבצע זה נקרא רשמית, enqueue.

מִשׁמֶרֶת

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

מאמר זה מסביר כיצד להשתמש במבנה נתוני התור C ++. עליכם להכיר מצביעי C ++ והפניות כדי להבין את שאר מאמר זה.

כיתה וחפצים

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

השם, התור, הוא מחלקה. לאובייקט שנוצר ממחלקת התורים יש שם מתכנת שנבחר.

יש צורך בפונקציה השייכת למחלקה כדי לייצר אובייקט מהמעמד. ב- C ++, לפונקציה הזו יש אותו שם כמו שם המחלקה. לאובייקטים שנוצרו (מיוצרים) מהכיתה יש שמות שונים שניתן להם על ידי המתכנת.

יצירת אובייקט מהמעמד פירושה בניית האובייקט; זה אומר גם להזדהות.

תוכנית C ++ המשתמשת במחלקת התורים, מתחילה בשורות הבאות בראש הקובץ:

#לִכלוֹל
#לִכלוֹל
באמצעות מרחב שמות std;

השורה הראשונה מיועדת לקלט/פלט. השורה השנייה היא לאפשר לתוכנית להשתמש בכל התכונות של מחלקת התורים. השורה השלישית מאפשרת לתוכנית להשתמש בשמות במרחב השמות הסטנדרטי.

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

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

בְּנִיָה

תוֹר<סוּג>שֵׁם()

ההצהרה הבאה מייצגת תור בשם, que מסוג int.

תוֹר<int>זֶה;

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

בנייה עם רשימת אתחול

ההגדרה הבאה מראה כיצד ליצור תור עם רשימת אתחול:

תוֹר<לָצוּף>זֶה({1.1, 2.2, 3.3, 4.4});

הורס תור

כדי להרוס תור, פשוט תן לו לצאת מהיקף.

גישה לרכיב תור

דחיפה (ערך)

תור הוא רשימת First-In-First-Out. אז כל ערך מתווסף מאחור. קטע הקוד הבא יוצר תור ריק, ולאחר מכן מתווספים חמישה ערכי צף מאחור:

תוֹר<לָצוּף>זֶה;

זֶה.לִדחוֹף(1.1);
זֶה.לִדחוֹף(2.2);
זֶה.לִדחוֹף(3.3);
זֶה.לִדחוֹף(4.4);
זֶה.לִדחוֹף(5.5);

גודל () קבוע

זה מחזיר את מספר האלמנטים בתור. הקוד הבא ממחיש:

תוֹר<לָצוּף>זֶה;
זֶה.לִדחוֹף(1.1);זֶה.לִדחוֹף(2.2);זֶה.לִדחוֹף(3.3);זֶה.לִדחוֹף(4.4);זֶה.לִדחוֹף(5.5);
עֲלוּת<<זֶה.גודל() << ' n';

הפלט הוא 5.

חֲזִית()

פעולה זו מחזירה הפניה לרכיב הראשון של התור, מבלי להסיר את האלמנט. הפלט של הקוד הבא הוא 1.1.

תוֹר<לָצוּף>זֶה;
זֶה.לִדחוֹף(1.1);זֶה.לִדחוֹף(2.2);זֶה.לִדחוֹף(3.3);זֶה.לִדחוֹף(4.4);זֶה.לִדחוֹף(5.5);
עֲלוּת<<זֶה.חֲזִית() << ' n';

האלמנט אינו מוסר מהתור.

קדמית () קבועה

כאשר לבניית התור קודמת const, הביטוי front () const מבוצע במקום הקדמי (). הוא משמש בקוד הבא, למשל.

קבועתוֹר<לָצוּף>זֶה({1.1, 2.2, 3.3, 4.4, 5.5});
עֲלוּת<<זֶה.חֲזִית() << ' n';

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

חזור()

פעולה זו מחזירה הפניה לרכיב האחרון של התור, מבלי להסיר את האלמנט. פלט הקוד הבא הוא 5.5.

תוֹר<לָצוּף>זֶה;
זֶה.לִדחוֹף(1.1);זֶה.לִדחוֹף(2.2);זֶה.לִדחוֹף(3.3);זֶה.לִדחוֹף(4.4);זֶה.לִדחוֹף(5.5);
עֲלוּת<<זֶה.חזור() << ' n';

גב () קבוע

כאשר לבניית התור קודמת const, הביטוי back () const מבוצע במקום back (). הוא משמש בקוד הבא, למשל.

קבועתוֹר<לָצוּף>זֶה({1.1, 2.2, 3.3, 4.4, 5.5});
עֲלוּת<<זֶה.חזור() << ' n';

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

קיבולת תור

גודל () קבוע

- ראה לעיל

ריק () konst

זה מחזיר 1 עבור true אם אין רכיבים בתור, או 0 עבור false אם התור ריק. הקוד הבא ממחיש זאת:

תוֹר<לָצוּף>זה 1({1.1, 2.2, 3.3, 4.4, 5.5});
עֲלוּת<<זה 1.ריק() << ' n';
תוֹר<לָצוּף>זה 2;
עֲלוּת<<זה 2.ריק() << ' n';

הפלט הוא:

0
1

משני תורים

פופ ()

תור הוא FIFO, ולכן יש להסיר כל רכיב שיש להסיר מהחלק העליון (ראש) של התור. פונקציית חבר זו מסירה את האלמנט הראשון מבלי להחזיר אותו. הקוד הבא ממחיש זאת:

תוֹר<לָצוּף>זֶה({1.1, 2.2, 3.3, 4.4, 5.5});
עֲלוּת<<זֶה.חֲזִית() << ' n';
זֶה.פּוֹפּ();
עֲלוּת<<זֶה.גודל() << ' n';

הפלט הוא:

1.1
4

החלפה (ב)

ניתן להחליף שני תורים, כפי שמודגם בקטע קוד זה:

תוֹר<לָצוּף>זה 1({1.1, 2.2, 3.3, 4.4, 5.5});
תוֹר<לָצוּף>זה 2({10, עשרים});
זה 1.לְהַחלִיף(זה 2);
עֲלוּת<< 'האלמנט והגודל הראשון של que1:
'<<זה 1.חֲזִית() <<','<<זה 1.גודל() << ' n';
עֲלוּת<< 'אלמנט וגודל ראשון של que2'<<
זה 2.חֲזִית() <<','<<זה 2.גודל() << ' n';

הפלט הוא:

האלמנט והגודל הראשון של que1: 10, 2

האלמנט והגודל הראשון של que2: 1.1, 5

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

מפעילים שוויון ויחסי תורים

עבור תווים רגילים ב- C ++, בסדר עולה, מספרים מגיעים לפני אותיות גדולות, המגיעות לפני אותיות קטנות. דמות החלל באה לפני האפס וכולן.

מפעילי שוויון

מחזירה 1 עבור true ו- 0 עבור false.

המפעיל ==

מחזירה 1 אם שני התורים בעלי אותו גודל והרכיבים המתאימים שווים; אחרת הוא מחזיר 0. דוגמה:

תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1==זה 2;
עֲלוּת<<על אחד<< ' n';

הפלט הוא: 0.

המפעיל! =

- הפוך מהאמור לעיל. דוגמא:

תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1! =זה 2;
עֲלוּת<<על אחד<< ' n';

הפלט הוא: 1.

מפעילים יחסיים

מחזירה 1 עבור true ו- 0 עבור false.

מחזירה 1 אם התור הראשון הוא קבוצת המשנה הראשונית של התור השני, כאשר האלמנטים של שני החלקים השווים הם זהים ובאותו הסדר. אם שני התורים הם באותו גודל או בגדלים שונים, ועוברים משמאל לימין, נתקל אלמנט בתור הראשון שהוא פחות מהאלמנט המקביל בתור השני, אז עדיין 1 יוחזר. אחרת 0 מוחזר. דוגמא:
תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1<זה 2;
עֲלוּת<<על אחד<< ' n';
הפלט הוא 1.
המפעיל>

- הפוך מהאמור לעיל. דוגמא:
תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1>זה 2;
עֲלוּת<<על אחד<< ' n';
פלט: 0

ה<= Operator

- כמו תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1<=זה 2;
עֲלוּת<<על אחד<< ' n';
פלט: 1

מפעיל> =

- הפוך מהאמור לעיל. דוגמא:
תוֹר<קבוע לְהַשְׁחִיר*>זה 1({'סוג', 'משהו אחר'});
תוֹר<קבוע לְהַשְׁחִיר*>זה 2({'רָשָׁע'});
intעל אחד=זה 1> =זה 2;
עֲלוּת<<על אחד<< ' n';
פלט: 0

קלאס וחפציו הממוסדים

ערך הוא לסוג נתונים, כמו שאובייקט מיידי הוא למחלקה. בניית התור יכולה לקבל גם מחלקה כסוג נתונים. התוכנית הבאה ממחישה זאת:
#לִכלוֹל
#לִכלוֹל
באמצעות מרחב שמות std;
כיתה TheCla
{
פּוּמְבֵּי:
intעל אחד;
סטָטִי לְהַשְׁחִירצ';
בָּטֵלפוּנקצִיָה(לְהַשְׁחִירלא, קבוע לְהַשְׁחִיר *עמ)
{
עֲלוּת<< 'יש ' <<על אחד<< 'ספרים שווים' <<לא<<עמ<< ' בחנות.' << ' n';
}
סטָטִי בָּטֵלכֵּיף(לְהַשְׁחִירצ')
{
אם (צ'== 'ל')
עֲלוּת<< 'פונקציה רשמית של חבר סטטי' << ' n';
}
};
intרָאשִׁי()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
תוֹר<TheCla>זֶה;
זֶה.לִדחוֹף(obj1);זֶה.לִדחוֹף(obj2);זֶה.לִדחוֹף(obj3);זֶה.לִדחוֹף(obj4);זֶה.לִדחוֹף(obj5);
עֲלוּת<<זֶה.גודל() << ' n';
לַחֲזוֹר 0;
}
הפלט הוא 5.

רשימה מקושרת

רשימת התורים נקראת מבחינה טכנית רשימה מקושרת. ישנם שני סוגים של רשימות מקושרות לתור: רשימה מקושרת בנפרד ורשימה מקושרת כפולה.

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

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

יישומי התור

התור הוא מבנה נתונים ראשון-ראשון-החוצה. ישנם מצבים במחשוב כאשר הנתונים מגיעים בצורת תור, המחייבים התנהגות ראשונה-ראשון-החוצה.

שיתוף משאבי מחשב

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

טיפול בהפרעות

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

נהל מידע.

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

סיכום

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

כל מבנה נתוני תורים חייב לספק לפחות את פונקציות החברים של הדחיפה () והפופ (). push () פירושו שליחת אלמנט חדש בחלק האחורי של התור; ופופ () פירושו הסרת האלמנט שנמצא בקדמת התור. למרבה הצער, ב- C ++, פונקציות אלה אינן מחזירות את הערך שנדחק או צץ. לכן, כדי לדעת את האלמנט האחרון לפני הדחיפה, יש להשתמש בפונקציית הגב הנוספת () הנוספת; וכדי לדעת את האלמנט הראשון לפני הקפיצה, יש להשתמש בפונקציה החזית () הנוספת.

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

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

כריס

כיצד להשתמש בתור C ++

מבוא

FIFO

פעולות חיוניות

כיתה וחפצים

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

בְּנִיָה

בנייה עם רשימת אתחול

הורס תור

גישה לרכיב תור

קיבולת תור

משני תורים

מפעילים שוויון ויחסי תורים

מפעילי שוויון

מפעילים יחסיים

קלאס וחפציו הממוסדים

רשימה מקושרת

יישומי התור

שיתוף משאבי מחשב

טיפול בהפרעות

נהל מידע.

סיכום

קטגוריה

רשום פופולרי