פרק 13 - תור (Queue)

⏱ 12 דקות קריאה

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

1. עקרון ה-FIFO

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

אנלוגיה: תור לקופה. מי שהגיע ראשון - יוצא ראשון. אף אחד לא "מתפרץ" מהאמצע.

Queue מול Stack (הפרק הקודם) - השוואה מהירה:

Queue - FIFO: הראשון שנכנס הוא הראשון שיוצא, כמו תור לקופה. הפעולות: insert/remove/head.

Stack - LIFO: האחרון שנכנס הוא הראשון שיוצא, כמו ערימת צלחות. הפעולות: push/pop/top.

2. מחלקת Queue - החתימה הסטנדרטית

Java


public class Queue<T> {
    public Queue() { ... }

    public boolean isEmpty() { ... }
    public void insert(T x) { ... }   // מוסיפה x לסוף התור
    public T head() { ... }           // מחזירה את הערך שבראש, בלי להוציא אותו
    public T remove() { ... }         // מוציאה ומחזירה את הערך שבראש
}

שימו לב - זו נקודה שממש כדאי לזכור: ב-Queue של הבגרות שמות המתודות הם insert / remove / head. זה לא enqueue/dequeue (כמו שנהוג לקרוא להן בהרבה ספרי לימוד), ולא push/pop (אלה שייכות ל-Stack). קריאה לשם הלא נכון היא שגיאת קומפילציה - המתודה פשוט לא קיימת במחלקה.

3. דוגמה - עיבוד תור בלי לפגוע בסדר שלו

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

Java


public static boolean containsAtLeast(Queue<Integer> q, int x) {
    int size = 0;
    Queue<Integer> temp = new Queue<>();
    boolean found = false;

    while (!q.isEmpty()) {
        int val = q.remove();
        if (val >= x) {
            found = true;
        }
        temp.insert(val);
    }
    while (!temp.isEmpty()) {           // מחזירים הכל בחזרה, באותו סדר
        q.insert(temp.remove());
    }
    return found;
}

שני שלבים: קודם מרוקנים לגמרי את q לתוך temp תוך כדי בדיקה, ואז מרוקנים את temp בחזרה לתוך q - כך שהתור המקורי חוזר בדיוק לאותו מצב שהיה בו לפני הקריאה לפעולה. זו התבנית הנפוצה ביותר לעבודה עם Queue בבגרות.

4. טעויות נפוצות

שימוש בשם מתודה לא נכון: enqueue, dequeue, push או pop על Queue - שגיאת קומפילציה.

שכחת השחזור: אחרי לולאה ראשונה שמרוקנת את q, אם לא מחזירים את האיברים בלולאה שנייה - התור נשאר ריק בסוף הפעולה, למרות שלא היה אמור להשתנות.

קריאה לתור ריק: remove() או head() בלי לבדוק isEmpty() קודם.

🎓 זווית הבגרות

איך זה מופיע בבגרות: Queue מופיע כמו Stack בחלק א' של 899271, אבל תמיד עם התבנית "לרוקן ולהחזיר" - כי אין ל-Queue גישה ישירה לאמצע.

סוג שאלה טיפוסי: פונקציה שסורקת את כל התור תוך שימוש בתור עזר (temp) כדי לשמר את הסדר המקורי - בדיוק כמו הדוגמה למעלה.

טעות נפוצה: קריאה למתודות בשם הלא נכון (enqueue/dequeue/push/pop) - שגיאת קומפילציה מיידית, בדיוק כמו שהודגש בקופסה האדומה למעלה.

מה לזכור למבחן: כל פונקציה שסורקת Queue וצריכה להשאיר אותו כפי שהיה חייבת שתי לולאות נפרדות - אחת שמרוקנת ובודקת, ושנייה שמחזירה הכל בחזרה.

5. תרגול

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

מה יודפס למסך על ידי הקוד הבא?

Java

Queue<Integer> q = new Queue<>();
q.insert(1);
q.insert(2);
q.insert(3);
q.remove();
System.out.println(q.head());

כתבו את שורת הקוד שמכניסה את הערך x לסוף התור q.

כתבו את שורת הקוד שמוציאה ערך מראש התור q ושומרת אותו במשתנה val מטיפוס int.

כתבו את תנאי הלולאה שממשיכה כל עוד התור q אינו ריק.

→פרק 12 - מחסנית (Stack) פרק 14 - עצים בינריים←