דילוג לתוכן המרכזי

סיכום תור

מדעי המחשב לבגרות · 3 נושאים

כל מה שצריך לדעת בתור: המושגים, הכללים, דרכי פתרון וקוד ב-Java וב-C# עם דוגמאות פתורות משאלוני הבגרות. לחזרה מהירה לפני הבחינה - הסיכום המקוצר או דף כללים.

תור

תור במדעי המחשב עובד כמו תור בקופה: מי שנכנס ראשון יוצא ראשון. נכנסים רק בסוף, ויוצאים רק מהראש. לכן תור מתאים לכל בעיה שבה צריך לשמור על סדר ההגעה: הזמנות, חולים בחדר מיון, משימות שמחכות לטיפול.
במדויק: תור הוא טיפוס נתונים מופשט עם נקודת כניסה (הסוף), נקודת יציאה (הראש) וסדר FIFO (First In, First Out). בבחינה מקבלים את המחלקה Queue<T> מוכנה, ומשתמשים רק בפעולות שבממשק שלה, בלי לממש אותה ובלי לדעת איך היא ממומשת. בשאלון 899271 שאלת התור נמצאת בפרק הראשון (מבני נתונים).

1. המחלקה Queue: הממשק ומה כל פעולה עושה

המחלקה Queue<T>

אין צורך לדעת מה יש "בתוך" התור. מספיק לדעת חמש פעולות: לבנות תור ריק, לבדוק אם הוא ריק, להכניס לסוף, להוציא מהראש ולהציץ בראש בלי להוציא.
במדויק: Queue<T> היא מחלקה גנרית: T הוא טיפוס האיברים. תור של מספרים שלמים: Queue<Integer> ב-Java, Queue<int> ב-C#. תור של עצמים: Queue<Order>, Queue<Patient>. מצב התור משתנה רק דרך הפעולות שבממשק. אין פעולה שמחזירה את מספר האיברים, ואין גישה לאיבר לפי המקום שלו: רואים רק את הראש.

בגלל שרואים רק את הראש, כל שאלה שצריכה איבר במקום מסוים, ספירה או חיפוש עוברת על כל התור (השיעור על סריקת תור). שאלה שמבקשת תור חדש בונה אותו בעזרת insert (השיעור על בניית תור).

פעולות הממשק של Queue<T>

פעולהJavaC#מה עושהסיבוכיות
בנייהnew Queue<Integer>()new Queue<int>()בונה תור ריקO(1)
ריק?q.isEmpty()q.IsEmpty()true אם אין בתור איבריםO(1)
הכנסהq.insert(x)q.Insert(x)מכניס את x לסוף התורO(1)
הוצאהq.remove()q.Remove()מחזיר את הערך שבראש התור ומוציא אותו. תנאי קדם: התור אינו ריקO(1)
הצצהq.head()q.Head()מחזיר את הערך שבראש התור בלי לשנות את התור. תנאי קדם: התור אינו ריקO(1)
תיאורq.toString()q.ToString()[x1, x2, ..., xn]: הראש משמאל, האיבר שנוסף אחרון מופיע אחרוןO(n·|T|)

בתכנית מסמנים ב-|T| את סיבוכיות זמן הריצה של הפעולה toString במחלקה T. בתור של n מספרים שלמים זה O(n).

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

הפעולות בפעולה

Queue<Integer> q = new Queue<Integer>();   // תור ריק
q.insert(3);
q.insert(7);
q.insert(5);
System.out.println(q);            // [3, 7, 5]
System.out.println(q.head());     // 3 - התור לא משתנה
int x = q.remove();               // x = 3, והוא יוצא מהתור
System.out.println(x + " " + q);  // 3 [7, 5]
q.insert(q.remove());             // הראש עובר לסוף
System.out.println(q);            // [5, 7]
System.out.println(q.isEmpty());  // false

q.insert(q.remove()) / q.Insert(q.Remove()) מעביר את האיבר שבראש לסוף התור. n פעמים כאלה מחזירות את התור בדיוק למצב שבו התחיל: זה "סיבוב" של התור.

שים לב

head() ו-remove() על תור ריק הם שגיאה ("תנאי קדם: התור אינו ריק"). לכן כל לולאה שמוציאה מהתור נכתבת while (!q.isEmpty()), וכל הצצה לראש באה אחרי בדיקה שהתור לא ריק.

שים לב

head() לא מוציא. מי שכותב q.head() בתוך לולאת while (!q.isEmpty()) ולא קורא ל-remove() נתקע בלולאה אינסופית: התור אף פעם לא מתרוקן.

דוגמה - מעקב אחר סיבוב תור עם סימן עצירה

לפניכם הפעולה mmm בשפת Java או Mmm בשפת C#, המקבלת תור q ובו מספרים הגדולים מ-0, ומספר שלם z הגדול מ-0:

public static boolean mmm(Queue<Integer> q, int z)
{
    q.insert(0);
    int num = q.head();
    int y = 0;
    while (q.head() > 0)
    {
        if (y < z)
        {
            if (q.head() == num)
            {
                y++;
            }
            else
            {
                num = q.head();
                y = 1;
            }
        }
        q.insert(q.remove());
    }
    q.remove();
    return y == z;
}

נתון התור q, מראשו לסופו: 1, 3, 1, 1, 1, 2.
עקבו בעזרת טבלת מעקב אחר הפעולה mmm(q, 4), וכתבו מה הפעולה מחזירה. בטבלה יש עמודות לתור q, ל-num, ל-y, ל-y < z ול-q.head() == num.

פתרון
1.לפני הלולאה: q.insert(0) מכניס 0 לסוף התור. כל המספרים בתור גדולים מ-0, ולכן ה-0 הוא סימן עצירה: הלולאה רצה עד שהוא מגיע לראש. num = q.head(), כלומר 1, ו-y = 0.
2.בכל סיבוב: אם y < z, משווים את הראש ל-num: שווה - y גדל ב-1; אחרת - num מקבל את הראש ו-y = 1. בסוף הסיבוב q.insert(q.remove()) מעביר את הראש לסוף.
3.הטבלה: התור - כפי שהוא בתחילת הסיבוב (הראש משמאל); num ו-y - אחרי הסיבוב.
שלבהתור qnumyy < zq.head() == num
לפני הלולאה1, 3, 1, 1, 1, 2, 010
11, 3, 1, 1, 1, 2, 011truetrue
23, 1, 1, 1, 2, 0, 131truefalse
31, 1, 1, 2, 0, 1, 311truefalse
41, 1, 2, 0, 1, 3, 112truetrue
51, 2, 0, 1, 3, 1, 113truetrue
62, 0, 1, 3, 1, 1, 121truefalse
סיום0, 1, 3, 1, 1, 1, 221
4.הסיום: בראש התור 0, והלולאה נעצרת. q.remove() מוציא את ה-0, והתור חוזר ל-1, 3, 1, 1, 1, 2.
5.ההחזרה: y == z הוא 1 == 4, כלומר false. הרצף הארוך ביותר של איברים שווים צמודים הוא 1, 1, 1, באורך 3 בלבד.
תשובה

mmm(q, 4) מחזירה false: הרצף הארוך ביותר של איברים שווים צמודים הוא 1, 1, 1, באורך 3. בסוף הפעולה התור חוזר למצבו המקורי.

2. סריקת תור בלי לאבד אותו: תור עזר והחזרת האיברים

סריקת תור

כדי לראות את האיבר השלישי בתור צריך להוציא את שני האיברים שלפניו. אם רק מוציאים - הם אבדו. לכן מעבירים כל איבר שיצא למקום שמור, ובסוף מחזירים אותו.
במדויק: סריקה של תור היא מעבר על כל האיברים מהראש לסוף, בעזרת remove(). תור עזר (temp) הוא תור חדש שאליו מכניסים כל איבר אחרי שעיבדו אותו. כשהתור המקורי מתרוקן, מעבירים את כל האיברים מ-temp בחזרה, והם חוזרים באותו סדר. סריקה כזו עולה O(n).

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

תבנית: סריקה עם תור עזר והחזרת האיברים

הפעולה size / Size מחזירה את מספר האיברים בתור ומשאירה אותו כמו שהיה. במקום count++ מעבדים את x לפי השאלה: סוכמים, משווים, שומרים את המקום.

public static int size(Queue<Integer> q)
{
    Queue<Integer> temp = new Queue<Integer>();
    int count = 0;
    while (!q.isEmpty())
    {
        int x = q.remove();
        count++;              // כאן מעבדים את x
        temp.insert(x);
    }
    while (!temp.isEmpty())   // מחזירים את האיברים לתור, באותו סדר
    {
        q.insert(temp.remove());
    }
    return count;
}

שלוש דרכים לעבור על תור בלי לאבד אותו

דרךאיךמתי היא מתאימה
תור עזרמוציאים כל איבר, מכניסים ל-temp, ובסוף מחזירים הכול מ-temp ל-qתמיד. זו הדרך הבטוחה
סיבוב עם סימן עצירהמכניסים לסוף ערך שלא יכול להופיע בתור (למשל 0 כשכל המספרים גדולים מ-0), ומבצעים q.insert(q.remove()) עד שהוא בראש. בסוף מוציאים אותוכשהשאלה מבטיחה טווח ערכים, כמו בפעולה mmm
סיבוב לפי גודלסופרים קודם את האיברים (size), ומבצעים q.insert(q.remove()) בדיוק size פעמיםכשכבר יודעים כמה איברים יש
דרך הפתרון

סריקת תור בלי לאבד אותו

1.קוראים מה מותר: "בסיום הפעולה חובה לשמור על מבנה התור" - מחזירים את האיברים. "אפשר לשנות את התור שהתקבל" / "אין צורך לשמור על התור" - מותר לרוקן אותו.
2.תור עזר: Queue<Integer> temp = new Queue<Integer>(), מאותו טיפוס כמו q.
3.לולאת הסריקה: while (!q.isEmpty()). מוציאים את x, מעבדים אותו (מונה, סכום, דגל, ומשתנה pos כשהשאלה מדברת על "המקום ה-m"), ומכניסים ל-temp.
4.מחזירים: לולאה שנייה שמעבירה את כל temp בחזרה ל-q.
5.רק עכשיו מחזירים את התשובה (return).
שים לב

אל תכתבו return מתוך לולאת הסריקה, גם כשהתשובה כבר ידועה. האיברים שכבר עברו ל-temp לא יחזרו, והתור המקורי נהרס. שומרים את התשובה במשתנה (למשל magic), ומחזירים אותה אחרי ההחזרה של האיברים.

שים לב

התור מועבר לפעולה כהפניה: כל remove() בתוך הפעולה מוציא איבר מהתור של מי שקרא לה. בזכות זה nMagic יכולה לקרוא ל-isMagic שוב ושוב על אותו תור: isMagic מחזירה את התור למצבו בסוף כל קריאה.

שים לב

סימן עצירה עובד רק כשהוא לא יכול להופיע בתור. בפעולה mmm התור מכיל "מספרים הגדולים מ-0", ולכן 0 מתאים. אחרי הלולאה חייבים להוציא אותו (q.remove()), אחרת הוא נשאר בתור.

שים לב

סריקה אחת עולה O(n). פעולה שקוראת לפעולת סריקה בתוך לולאה משלמת את זה בכל סיבוב: nMagic קוראת ל-isMagic בעבור המקומות n, 2n, 3n... ובמקרה הגרוע (n = 1) היא עולה O(size²).

דוגמה - בדיקה אם האיבר במקום m הוא איבר קסם

"איבר קסם" הוא איבר בתור של מספרים שערכו שווה לסכום הערכים של האיבר שלפניו והאיבר שאחריו. המספר הראשון בתור והמספר האחרון בתור אינם "איברי קסם".
כתבו פעולה ששמה isMagic בשפת Java או IsMagic בשפת C#, המקבלת תור q מטיפוס שלם, ומספר שלם m הגדול מ-0 וקטן או שווה לגודל התור. הפעולה תחזיר true אם האיבר במקום ה-m בתור הוא "איבר קסם", אחרת היא תחזיר false.

•בסיום הפעולה חובה לשמור על מבנה התור כפי שהתקבל.
•אין להשתמש במערך או ברשימה מקושרת.

לדוגמה, בעבור התור (מראשו לסופו) 5, 11, 6, 9, 3, 6, 3: בעבור m = 1 הפעולה תחזיר false, בעבור m = 2 היא תחזיר true (5 + 6 = 11), ובעבור m = 3 היא תחזיר false (11 + 9 ≠ 6).

פתרון
1.אין גישה לפי מקום: עוברים על כל התור, מוציאים איבר-איבר, סופרים את המקום שלו ב-pos, ומכניסים אותו לתור עזר temp.
2.מה שומרים: במקום m-1 - את before; במקום m - את cur; במקום m+1 (הערך x) - בודקים before + x == cur.
3.מקרי הקצה: אם m = 1 אין איבר לפניו, והתנאי m > 1 מונע את הבדיקה. אם m הוא המקום האחרון, לא מגיעים למקום m+1. בשני המקרים magic נשאר false.
4.החזרת התור: מעבירים את temp בחזרה ל-q, ורק אז מחזירים את magic.
public static boolean isMagic(Queue<Integer> q, int m)
{
    Queue<Integer> temp = new Queue<Integer>();
    int pos = 0;            // מקום האיבר הנוכחי בתור
    int before = 0;         // האיבר במקום m-1
    int cur = 0;            // האיבר במקום m
    boolean magic = false;
    while (!q.isEmpty())
    {
        int x = q.remove();
        pos++;
        if (pos == m - 1)
            before = x;
        else if (pos == m)
            cur = x;
        else if (pos == m + 1 && m > 1)
            magic = (before + x == cur);
        temp.insert(x);
    }
    while (!temp.isEmpty())          // החזרת התור למצבו המקורי
        q.insert(temp.remove());
    return magic;
}
5.בדיקה על התור 5, 11, 6, 9, 3, 6, 3:
קריאה עם mbeforecurאחריובדיקהמוחזר
1-511m > 1 לא מתקייםfalse
251165 + 6 = 11true
3116911 + 9 = 20 ≠ 6false
763-אין איבר אחריוfalse

אחרי כל קריאה התור נשאר 5, 11, 6, 9, 3, 6, 3. הפעולה עוברת על התור פעמיים (הוצאה והחזרה), ולכן היא O(n).

תשובה

מעבירים את כל איברי התור לתור עזר תוך ספירת המקום; שומרים את האיבר במקום m-1 ואת האיבר במקום m, וכשמגיעים למקום m+1 בודקים before + x == cur (רק אם m > 1). בסוף מחזירים את האיברים לתור. אם m = 1 או m הוא המקום האחרון - false.

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

בניית תור חדש

הרבה שאלות לא מבקשות תשובה אחת, אלא תור שלם: רק חלק מהאיברים, אותם איברים בסדר אחר, או איבר אחד לכל לקוח. בונים אותו מאפס, איבר אחרי איבר, בעזרת insert.
במדויק: הפעולה יוצרת new Queue<...>(), מכניסה אליו את האיברים לפי הסדר שבו הם צריכים להופיע, ומחזירה אותו (return result). בתור של עצמים (Queue<Order>, Queue<Patient>) כל איבר הוא הפניה לעצם, וניגשים לתכונות שלו בפעולות get. בפעולה של מחלקה שאחת התכונות שלה היא תור (כמו PriorQueue), ניגשים לתור ישירות דרך התכונה q.

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

תבניות של בניית תור

מה מבקשיםאיך בוניםדוגמה בבגרות
סינוןמעבר אחד: איבר שעונה על התנאי נכנס לתוצאה-
פיצול: קודם קבוצה אחת ואחריה השנייהמעבר אחד: קבוצה א ישר לתוצאה, קבוצה ב לתור עזר. בסוף מעבירים את תור העזר לסוף התוצאהpreferredClients: קודם הלקוחות המועדפים, אחריהם הרגילים
איחוד לפי מפתחבכל סבב מוציאים את הראשון, אוספים את כל האיברים עם אותו מפתח, ואת השאר מכניסים לתור עזר שמחליף את התור (qOrder = temp)uniteOrders: הזמנה אחת לכל לקוח
הכנסה למקום לפי סדרמעבירים לתור עזר, ומכניסים את החדש לפני האיבר הראשון שהוא צריך לעמוד לפניו. אם אין כזה - בסוףpriorityInsert: חולה לפי רמת דחיפות
הזזת איברמוציאים אותו (כל השאר עוברים לתור עזר וחוזרים), מעדכנים, ומכניסים מחדש למקום הנכוןupdate: שינוי רמת הדחיפות של חולה

תבנית: פיצול לשתי קבוצות וחיבור בסדר

הפעולה bigFirst / BigFirst מחזירה תור חדש: קודם כל האיברים שגדולים מ-x או שווים לו, ואחריהם כל השאר, כל קבוצה בסדר המקורי. התור q מתרוקן.

public static Queue<Integer> bigFirst(Queue<Integer> q, int x)
{
    Queue<Integer> result = new Queue<Integer>();
    Queue<Integer> small = new Queue<Integer>();   // תור עזר
    while (!q.isEmpty())
    {
        int val = q.remove();
        if (val >= x)
            result.insert(val);    // עונה על התנאי - ישר לתוצאה
        else
            small.insert(val);     // לא עונה - מחכה בתור העזר
    }
    while (!small.isEmpty())       // תור העזר - לסוף התוצאה
    {
        result.insert(small.remove());
    }
    return result;
}

למשל, בעבור התור 4, 12, 7, 15, 3, 10 ו-x = 10 מתקבל התור 12, 15, 10, 4, 7, 3.

דרך הפתרון

בניית תור חדש

1.מה בתוצאה ובאיזה סדר: אילו איברים, כמה פעמים כל אחד, ומה בא קודם. בתור של עצמים - האם מכניסים את העצם שהיה, או עצם חדש עם ערכים מחושבים (new Order(id, total)).
2.אילו תורים: תור תוצאה, ולכל קבוצה ש"מחכה" - תור עזר.
3.מה מותר לשנות: אם "אפשר לשנות את התור שהתקבל", מרוקנים אותו. אחרת - מחזירים אליו את האיברים (השיעור הקודם).
4.סבבים: כשכל איבר צריך להשוות לכל האחרים (איחוד לפי מפתח), יוצרים בכל סבב תור עזר חדש, ובסוף הסבב הוא מחליף את התור שנשאר.
5.בודקים על הדוגמה שבשאלה, ועל תור ריק.
שים לב

בתור של עצמים משווים לפי התכונה שהשאלה מגדירה כמזהה: o.getId() == first.getId(). ההשוואה o == first בודקת אם זה אותו עצם, ושתי הזמנות של אותו לקוח הן שני עצמים שונים.

שים לב

בפעולה uniteOrders יוצרים את temp בתוך הלולאה החיצונית, ובסוף כל סבב כותבים qOrder = temp. מי שיוצר את temp פעם אחת ולא מחליף את qOrder, מרוקן את qOrder כבר בסבב הראשון, וכל שאר הלקוחות "נעלמים".

שים לב

סיווג לפי סך הכול מחייב לאחד קודם. "לקוח מועדף" הזמין "10 מוצרים ומעלה סך הכול": לקוח עם הזמנות של 4 ו-6 מוצרים הוא מועדף, אף שכל הזמנה לבדה קטנה מ-10. ו"ומעלה" הוא >= 10, לא > 10.

שים לב

בהכנסה לפי סדר, הסימן קובע מה קורה בשוויון. בפעולה priorityInsert החולה החדש נכנס לפני החולה הראשון שרמת הדחיפות שלו נמוכה משלו (<). עם <= הוא היה עוקף חולים באותה רמה שהגיעו לפניו.

שים לב

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

דוגמה א - איחוד הזמנות לפי מספר זהות

נתונה המחלקה Order - הזמנה של לקוח, ולה שתי תכונות: id - מספר זהות של הלקוח, ו-count - כמות המוצרים שהוזמנו (שתיהן מטיפוס שלם). יש פעולות get/Get ו-set/Set לתכונות, ופעולה בונה המקבלת ערכים בעבור התכונות.
בתור qOrder מטיפוס Order יכולות להיות כמה הזמנות של אותו לקוח, במקומות שונים בתור.
ממשו את הפעולה public static Queue<Order> uniteOrders(Queue<Order> qOrder) ב-Java או public static Queue<Order> UniteOrders(Queue<Order> qOrder) ב-C#. הפעולה מחזירה תור חדש שבו לכל לקוח הזמנה אחת בלבד, עם סך כל המוצרים שהזמין. למשל, 3 הזמנות של אותו לקוח, של 20, 15 ו-30 מוצרים, הופכות להזמנה אחת של 65 מוצרים.

•אין חשיבות לסדר ההזמנות אחרי האיחוד.
•אין להשתמש במערך או ברשימה מקושרת (או בשום מבנה נתונים אחר פרט לתור).
•אפשר לשנות את התור שהתקבל.
פתרון
1.כל עוד qOrder אינו ריק: מוציאים את ההזמנה הראשונה, first. זה לקוח שעוד לא טופל, ו-total מתחיל בכמות שלה.
2.מעבר על השאר: מוציאים את כל ההזמנות שנשארו. של אותו לקוח (אותו id) - מוסיפים ל-total; של לקוח אחר - נכנסת לתור עזר temp חדש.
3.סוף הסבב: temp מכיל בדיוק את ההזמנות של הלקוחות שעוד לא טופלו, ולכן qOrder = temp. לתוצאה נכנסת הזמנה חדשה new Order(first.getId(), total).
public static Queue<Order> uniteOrders(Queue<Order> qOrder)
{
    Queue<Order> result = new Queue<Order>();
    while (!qOrder.isEmpty())
    {
        Order first = qOrder.remove();          // הזמנה של לקוח חדש
        int total = first.getCount();
        Queue<Order> temp = new Queue<Order>();
        while (!qOrder.isEmpty())               // מעבר על שאר ההזמנות
        {
            Order o = qOrder.remove();
            if (o.getId() == first.getId())
                total += o.getCount();          // אותו לקוח - מצרפים
            else
                temp.insert(o);                 // לקוח אחר - נשאר לסבב הבא
        }
        qOrder = temp;
        result.insert(new Order(first.getId(), total));
    }
    return result;
}
4.בדיקה על התור (id, count), מראשו לסופו: (7, 20), (4, 3), (7, 15), (9, 8), (7, 30), (4, 6).
סבבהוצאהtotaltemp בסוף הסבבנכנס לתוצאה
1(7, 20)20 + 15 + 30 = 65(4, 3), (9, 8), (4, 6)(7, 65)
2(4, 3)3 + 6 = 9(9, 8)(4, 9)
3(9, 8)8ריק(9, 8)

התור המוחזר: (7, 65), (4, 9), (9, 8).

5.סיבוכיות: במקרה הגרוע כל ההזמנות של לקוחות שונים, והלולאה הפנימית עוברת על n-1, n-2, ..., 1 הזמנות - O(n²).
תשובה

בכל סבב מוציאים הזמנה ראשונה, סוכמים את כל ההזמנות של אותו id ומעבירים את השאר לתור עזר שמחליף את qOrder; מכניסים לתוצאה new Order(id, total).

דוגמה ב - הכנסת חולה לתור עדיפויות

נתונה המחלקה Patient - חולה בחדר מיון, ולה שתי תכונות: id - מספר הזהות, ו-priority - רמת הדחיפות, מספר שלם בין 1 ל-10 (גבוה יותר = דחוף יותר). לתכונות יש פעולות get/Get ו-set/Set.
ככל שרמת הדחיפות גבוהה יותר, החולה מטופל מוקדם יותר. כשיש יותר מחולה אחד באותה רמה, מי שהגיע קודם מטופל קודם.
למחלקה PriorQueue - תור עדיפויות - יש תכונה אחת: q, הפניה לתור מטיפוס Patient.
ממשו את הפעולה public void priorityInsert(Patient p) ב-Java או public void PriorityInsert(Patient p) ב-C#, השייכת למחלקה PriorQueue. הפעולה מקבלת חולה חדש p ומכניסה אותו לתור q לפי הכללים.
לדוגמה, התור q מראשו לסופו (id/priority): 13893/7, 28834/7, 72890/6, 12223/4, 13335/4, 33800/4. אחרי הכנסת החולה 11210 עם רמת דחיפות 6 התור הוא: 13893/7, 28834/7, 72890/6, 11210/6, 12223/4, 13335/4, 33800/4.

פתרון
1.איפה p צריך לעמוד: התור ממוין, ו-p הגיע אחרון. לכן הוא עומד אחרי כל החולים שרמת הדחיפות שלהם גבוהה משלו או שווה לה, ולפני החולה הראשון שרמת הדחיפות שלו נמוכה משלו.
2.מעבר עם תור עזר: מוציאים חולה-חולה מ-q ל-temp. כשנתקלים לראשונה בחולה עם cur.getPriority() < p.getPriority(), מכניסים קודם את p ומסמנים inserted = true.
3.אם לא הוכנס: כל החולים דחופים כמוהו או יותר, או שהתור ריק - p נכנס בסוף.
4.החזרה: מעבירים את temp בחזרה ל-q. הפעולה פנימית, ולכן ניגשת לתכונה q ישירות.
public void priorityInsert(Patient p)
{
    Queue<Patient> temp = new Queue<Patient>();
    boolean inserted = false;
    while (!q.isEmpty())
    {
        Patient cur = q.remove();
        // p נכנס לפני החולה הראשון שרמת הדחיפות שלו נמוכה משלו
        if (!inserted && cur.getPriority() < p.getPriority())
        {
            temp.insert(p);
            inserted = true;
        }
        temp.insert(cur);
    }
    if (!inserted)            // אין חולה עם דחיפות נמוכה יותר - p בסוף התור
        temp.insert(p);
    while (!temp.isEmpty())   // העברה חזרה לתור q
        q.insert(temp.remove());
}
5.בדיקה: 13893 (7), 28834 (7) ו-72890 (6) עוברים ל-temp. 12223 (4) הוא הראשון עם דחיפות נמוכה מ-6, ולכן לפניו נכנס 11210. מתקבל 13893/7, 28834/7, 72890/6, 11210/6, 12223/4, 13335/4, 33800/4, כמו בדוגמה. כל חולה עובר לתור העזר וחוזר פעם אחת: O(n).
תשובה

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

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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