תור
תור במדעי המחשב עובד כמו תור בקופה: מי שנכנס ראשון יוצא ראשון. נכנסים רק בסוף, ויוצאים רק מהראש. לכן תור מתאים לכל בעיה שבה צריך לשמור על סדר ההגעה: הזמנות, חולים בחדר מיון, משימות שמחכות לטיפול.
במדויק: תור הוא טיפוס נתונים מופשט עם נקודת כניסה (הסוף), נקודת יציאה (הראש) וסדר 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>
| פעולה | Java | C# | מה עושה | סיבוכיות |
|---|---|---|---|---|
| בנייה | 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()); // falseq.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.
q.insert(0) מכניס 0 לסוף התור. כל המספרים בתור גדולים מ-0, ולכן ה-0 הוא סימן עצירה: הלולאה רצה עד שהוא מגיע לראש. num = q.head(), כלומר 1, ו-y = 0.y < z, משווים את הראש ל-num: שווה - y גדל ב-1; אחרת - num מקבל את הראש ו-y = 1. בסוף הסיבוב q.insert(q.remove()) מעביר את הראש לסוף.| שלב | התור q | num | y | y < z | q.head() == num |
|---|---|---|---|---|---|
| לפני הלולאה | 1, 3, 1, 1, 1, 2, 0 | 1 | 0 | ||
| 1 | 1, 3, 1, 1, 1, 2, 0 | 1 | 1 | true | true |
| 2 | 3, 1, 1, 1, 2, 0, 1 | 3 | 1 | true | false |
| 3 | 1, 1, 1, 2, 0, 1, 3 | 1 | 1 | true | false |
| 4 | 1, 1, 2, 0, 1, 3, 1 | 1 | 2 | true | true |
| 5 | 1, 2, 0, 1, 3, 1, 1 | 1 | 3 | true | true |
| 6 | 2, 0, 1, 3, 1, 1, 1 | 2 | 1 | true | false |
| סיום | 0, 1, 3, 1, 1, 1, 2 | 2 | 1 |
q.remove() מוציא את ה-0, והתור חוזר ל-1, 3, 1, 1, 1, 2.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 פעמים | כשכבר יודעים כמה איברים יש |
סריקת תור בלי לאבד אותו
Queue<Integer> temp = new Queue<Integer>(), מאותו טיפוס כמו q.while (!q.isEmpty()). מוציאים את x, מעבדים אותו (מונה, סכום, דגל, ומשתנה pos כשהשאלה מדברת על "המקום ה-m"), ומכניסים ל-temp.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).
before + x == cur.m > 1 מונע את הבדיקה. אם m הוא המקום האחרון, לא מגיעים למקום m+1. בשני המקרים magic נשאר false.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;
}| קריאה עם m | before | cur | אחריו | בדיקה | מוחזר |
|---|---|---|---|---|---|
| 1 | - | 5 | 11 | m > 1 לא מתקיים | false |
| 2 | 5 | 11 | 6 | 5 + 6 = 11 | true |
| 3 | 11 | 6 | 9 | 11 + 9 = 20 ≠ 6 | false |
| 7 | 6 | 3 | - | אין איבר אחריו | 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.
בניית תור חדש
new Order(id, total)).בתור של עצמים משווים לפי התכונה שהשאלה מגדירה כמזהה: 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 מוצרים.
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;
}| סבב | הוצאה | total | temp בסוף הסבב | נכנס לתוצאה |
|---|---|---|---|---|
| 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).
בכל סבב מוציאים הזמנה ראשונה, סוכמים את כל ההזמנות של אותו 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.
cur.getPriority() < p.getPriority(), מכניסים קודם את p ומסמנים inserted = true.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());
}מעבירים את q לתור עזר. לפני החולה הראשון שרמת הדחיפות שלו נמוכה ממש מזו של p מכניסים את p. אם אין חולה כזה, p נכנס בסוף. אחר כך מחזירים את כל האיברים מתור העזר ל-q.