תורות
תור הוא FIFO
- תור הוא היכנס ראשון, יציאה ראשונה (FIFO).
- הפריט הראשון שמוסיפים הוא הראשון שיצא.
- חשבו על תור אנשים: האדם שמולך בתחילה הוא זה שמתקבל לשרות קודם.
הוספה להורדה עם רשימה
- ניתן לבנות תור מרשימת Python.
- הוספה =
queue.append(x)— הוסף לסוף. - הורדה =
queue.pop(0)— הסר והשב את הראש.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
ראש וריק
- הצץ בראש מבלי להסיר אותו:
queue[0]. - תור הוא ריק כאשר
len(queue) == 0. - בדוק שהוא לא ריק לפני ההורדה.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
הערה על מהירות
pop(0)צריך להזיז כל פריט אחר קדימה במיקום אחד.- עבור תור גדול זה איטי, ולכן משמש יותר זמן.
- מערכות אמיתיות משתמשות בממלא מעגלי עם נדנדים ראש ואחורי במקום זאת.
בפסאודוקוד קמברידג'
- המבחן בונה תור מארגון עם נדנד
frontונדנדrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
טעויות נפוצות
- תור הוא היכנס ראשון, יציאה ראשונה: הצטרף לסוף, לצא מהראש.
- בדוק שהוא לא ריק לפני ההורדה.
כעת תנסו בעצמכם
- השתמש ברשימה כתור שלך (
appendלהוספה,pop(0)להורדה). - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
A queue is FIFO
A queue adds at the back and removes at the front — first in, first out.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Start with an empty queue. Enqueue "a", then "b", then "c". Then הסרה מתור once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].)
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the אותו order. (result should be [1, 2, 3].)
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Write serve(queue) that dequeues the front item: remove it from the list and תשואה it. The caller's list should get shorter.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
Write front(queue) that החזרים the front item without removing it, so the queue is unchanged. If the queue is empty, return None.
לחץ על הרץ כדי לראות את התוצא כאן.