חיץ מעגלי או תור מעגלי הוא הגרסה המתקדמת של התור הרגיל שבו האינדקס ואינדקס הזנב האחרון מחוברים במבנה מעגלי. מאגר מעגלי ב-C++ עוקב אחר שתי שיטות: enqueue() ו-dequeue(). אנו מבצעים את פעולת המאגר העגול או התור המעגלי על סמך שיטות אלו.
- שיטת enqueue() בודקת אם המאגר מלא. אחרת, ודא שהאינדקס הסופי הוא האחרון. אם כן, הגדר את ערך הזנב ל-0. אם לא, הגדל את ערך הזנב בערך באותו מדד.
- הפונקציה dequeue() לוקחת את הערך מהאינדקס הקדמי בתור המעגלי. אם התור ריק, הודעה תציג את התור הריק הזה. אחרת, הוא מקבל את הערך האחרון ומוחק אותו מהתור.
תוכנית ליישום מאגר מעגלי ב-C++
בעקבות שתי השיטות שהוזכרו, אנו מיישמים את המאגר העגול ב-C++. בואו נשקול את כל השלבים ליישום התור המעגלי ב-C++.
#include
שימוש במרחב שמות std;
מבנה MyQueue
{
int רֹאשׁ , זָנָב ;
int Qsize;
int * NewArr;
התור שלי ( אינט לא ) {
רֹאשׁ = זָנָב = -1 ;
Qsize = גודל;
NewArr = new int [ ס ] ;
}
בטל תור ( int val ) ;
int deQueue ( ) ;
בטל את ה-showQueue ( ) ;
} ;
החל מהקוד, אנו יוצרים תחילה את מבנה 'MyQueue' כדי לאתחל את משתני הראש והזנב. משתנה הראש מייצג את המדדים הקדמיים והזנב מייצג את המדדים האחוריים של מערך. לאחר מכן, גודל התור המעגלי, המסומן במשתנה 'Qsize', מוגדר.
לאחר מכן, אנו מגדירים את המערך המוקצה באופן דינמי של 'NewArr' המאחסן את הערכים של התור המעגלי. לאחר מכן, אנו קוראים ל-MyQueue() שהוא בנאי ומעבירים את הפרמטר 'sz' עבור גודל התור המעגלי. בתוך הבנאי MyQueue() אנו מקצים את הערך '-1' למצביעי הראש והזנב. ערך שלילי זה מציין שהתור ריק כעת. בהמשך, אנו מקצים את הערך 'sz' המייצג את גודל התור המעגלי. התור המעגלי 'NewArr' מוגדר עם מילת מפתח חדשה כדי ליצור את מערך המספרים השלמים בגודל 'sz' שצוין.
לאחר מכן, אנו מגדירים את הפונקציות enQueue() ו-dequeue(). ה-enqueue() מכניס את הערכים לתור המעגלי שהוגדר מהזנב. עם זאת, האלמנטים בראש התור המעגלי בוטלו על ידי הפונקציה dequeue() . הפונקציה showQueue() member מציגה את הערכים של התור המעגלי.
שלב 1: צור פונקציה להכנסת האלמנטים למאגר עגול
בשלב הקודם, אנו מגדירים מחלקה שבה החברים הפרטיים מאותחלים ופונקציות החברים הפרטיות מוגדרות ליישם את התור המעגלי. כעת, אנו מגדירים את הפונקציה ליצירת התור המעגלי ומכניסים את הערכים בתוך התור המעגלי באמצעות האלגוריתם.
void MyQueue::enQueue ( int val ){
אם ( ( רֹאשׁ == 0 && זָנָב == Qsize - 1 ) || ( זָנָב == ( רֹאשׁ - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n התור מלא' ;
לַחֲזוֹר ;
}
אַחֵר אם ( רֹאשׁ == - 1 )
{
רֹאשׁ = זָנָב = 0 ;
NewArr [ זָנָב ] = val;
}
אַחֵר אם ( זָנָב == Qsize - 1 && רֹאשׁ ! = 0 )
{
זָנָב = 0 ;
NewArr [ זָנָב ] = val;
}
אַחֵר {
זָנָב ++;
NewArr [ זָנָב ] = val;
}
}
כאן, אנו קוראים לפונקציה 'enqueue()' מהמחלקה 'MyQueue' כדי להכניס את האלמנט בתור המעגלי אם התור ריק או נמוך. הפונקציה 'enqueue()' מועברת עם הפרמטר 'val' ומכניסה את הערך מהזנב של התור המעגלי. הגדרנו את התנאי 'אם-אחר' כדי להכניס את הערכים לתור המעגלי בשביל זה. המשפט הראשון של 'אם' שהוא 'אם ((ראש == 0 && זנב == Qsize - 1) || (זנב == (ראש - 1) % (Qsize - 1)))' בודק שני תנאים אם הראש נמצא בעמדת ההתחלה והזנב נמצא בעמדת הקצה של התור המעגלי. לאחר מכן, הוא בודק אם הזנב נמצא במצב אחד בחלק האחורי של תנוחת הראש. אם אחד מהתנאים הללו מתקיים, התור אינו ריק וההנחיה יוצרת את ההודעה.
לאחר מכן, יש לנו את התנאי 'אחר-אם' שמזהה אם התור ריק. אם כן, הערך מוכנס לתור. מכיוון שהראש נשמר שווה ל-1, זה מראה שהתור ריק ונדרש להכניס את הערך לתור המעגלי. לשם כך, אנו מגדירים את הראש והזנב שווים ל-0. לאחר מכן, אנו מכניסים את הערך ממיקום הזנב לתור המעגלי 'NewArr'.
לאחר מכן, יש לנו תנאי 'אחר-אם' השלישי שלנו שבודק אם הזנב נמצא במיקום האחרון של התור והראש אינו מיקום ההתחלה של התור. תנאי זה חל כאשר הזנב מגיע לקצה ולמצב ההתחלה עדיין יש מקום. לשם כך, עלינו להגדיר את הראש על 0, והאלמנט מתווסף ממיקום הזנב. לבסוף, אם כל התנאים הנתונים לא מתקיימים, התור לא ריק ולא מלא. במקרה זה, אנו מגדילים את הזנב ב-1 והערך מתווסף ממיקום הזנב החדש.
שלב 2: צור פונקציה למחיקת האלמנטים מהמאגר העגול
הגדרנו את הקוד הקודם ליצור ולהכניס את האלמנטים בתור המעגלי באמצעות הפונקציה enqueue() . כעת, אנו מגדירים את היישום של הסרת האלמנטים מהמאגר העגול אם הוא עולה על גדותיו.
int MyQueue::deQueue ( ){
אם ( רֹאשׁ == - 1 )
{
cout << ' \n התור חופשי' ;
לַחֲזוֹר INT_MIN;
}
int MyData = NewArr [ רֹאשׁ ] ;
NewArr [ רֹאשׁ ] = -1 ;
אם ( רֹאשׁ == זָנָב )
{
רֹאשׁ = -1 ;
זָנָב = -1 ;
}
אַחֵר אם ( רֹאשׁ == Qsize - 1 )
רֹאשׁ = 0 ;
אַחֵר
רֹאשׁ ++;
לַחֲזוֹר הנתונים שלי;
}
בקוד הנתון, אנו קוראים לפונקציה dequeue() מהמחלקה 'Myqueue' כדי להסיר את האלמנט מאינדקס head. אז יש לנו את הצהרת 'אם' שבודקת אם התור ריק. הראש מוגדר עם הערך '-1' המייצג את התור הריק. נוצרת ההודעה שהתור ריק ואז מחזירים את ה-INT_MIN שהוא הערך המינימלי הקבוע עבור int. ההצהרה 'אם' קובעת אם התור אינו תפוס. לשם כך, אנו מגדירים את המשתנה 'MyData' ומגדירים את הערך של האלמנט בראש התור. לאחר מכן, קבענו את הראש במיקום -1 מה שמציין שהערך הזה הוסר מהתור. לאחר מכן, אנו בודקים אם הראש והזנב שווים או לא. אם שניהם שווים, אנו מקצים את הערך '-1' לשניהם, המייצג את התור המעגלי הריק. לבסוף, אנו בודקים אם ה-dequeue() פועל אם הראש נמצא באינדקס האחרון של התור. לשם כך, הגדרנו אותו עם הערך של '0' שמסתובב בלולאה בתחילת המערך. אם אף אחד מהתנאים הנתונים אינו נכון, הערך של ה-head גדל והרכיב שהוצא בתור מוחזר.
שלב 3: צור פונקציה להצגת האלמנטים של המאגר העגול
בסעיף זה, אנו קוראים לפונקציה showQueue() כדי להציג את הרכיבים של התור המעגלי 'NewArr'.
void MyQueue::showQueue ( ){
אם ( רֹאשׁ == - 1 )
{
cout << ' \n התור חופשי' ;
לַחֲזוֹר ;
}
cout << ' \n רכיבי תור מעגלי: ' ;
אם ( זָנָב > = רֹאשׁ )
{
ל ( int i = רֹאשׁ ; אני < = זָנָב ; i++ )
cout << NewArr [ אני ] << '' ;
}
אַחֵר
{
ל ( int i = רֹאשׁ ; אני < Qsize; i++ )
cout << NewArr [ אני ] << '' ;
ל ( int i = 0 ; אני < = זָנָב ; i++ )
cout << NewArr [ אני ] << '' ;
}
}
הסטטוס הריק של התור מאומת תחילה. אם התור פנוי, מוצגת אינדיקציה שהתור המעגלי פנוי. אחרת, הפונקציה תציג את הרכיבים של התור המעגלי. לשם כך, אנו מגדירים את משפט ה'אם' שבו יש לנו את הזנב שגדול או שווה לראש. תנאי זה מוגדר לטפל במקרה כאשר התור המעגלי לא הושלם.
במקרה זה, אנו משתמשים בלולאת 'ל' כדי לחזור מהראש לזנב ולהדפיס את הערכים של התור המעגלי. המקרה הבא הוא שבו הושלם התור המעגלי. לשם כך, אנו בודקים באמצעות מצב 'אם' שבו הזנב קטן מהראש. לאחר מכן, עלינו להשתמש בשתי לולאות שבהן הראשונה חוזרת מהראש לסוף התור והשנייה חוזרת מתחילת הזנב.
שלב 4: צור את הפונקציה Main() של תוכנית התור המעגלי
לבסוף, אנו יוצרים את הפונקציה main() של התוכנית שבה אנו מכניסים חמישה מספרים שלמים לתור המעגלי ומציגים את המספרים השלמים של התור. לאחר מכן, אנו מציגים את המספרים השלמים שנמחקו מהתור המעגלי על ידי קריאה לפונקציה dequeue() . לאחר יציאה מהתור של כמה אלמנטים, אנו ממלאים את התור שוב על ידי הוספת האלמנטים החדשים באמצעות הפונקציה enqueue() .
int main ( ){
MyQueue זה ( 5 ) ;
// הכנסת אלמנטים ב תור מעגלי
que.enQueue ( אחד עשר ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( חֲמֵשׁ עֶשׂרֵה ) ;
// רכיבי תצוגה קיימים ב תור מעגלי
que.showQueue ( ) ;
// מחיקת רכיבים מהתור מעגלי
cout << ' \n רכיב שנמחק = ' << que.deQueue ( ) ;
cout << ' \n רכיב שנמחק = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
לַחֲזוֹר 0 ;
}
תְפוּקָה:
התוצאות של יישום התור המעגלי מוצגות במסך ההנחיה של C++.
סיכום
לסיכום, נושא החיץ המעגלי מוסבר לעומק במאמר זה. יצרנו תחילה את המאגר העגול, לאחר מכן הסברנו כיצד למחוק מהתור המעגלי, ולאחר מכן הצגנו את הרכיבים של העגול ב-C++.