Queues · תורות
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
תור הוא FIFO
- תור הוא היכנס ראשון, יציאה ראשונה (FIFO).
- הפריט הראשון שמוסיפים הוא הראשון שיצא.
- חשבו על תור אנשים: האדם שמולך בתחילה הוא זה שמתקבל לשרות קודם.
enqueue and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
הוספה להורדה עם רשימה
- ניתן לבנות תור מרשימת Python.
- הוספה =
queue.append(x)— הוסף לסוף. - הורדה =
queue.pop(0)— הסר והשב את הראש.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
ראש וריק
- הצץ בראש מבלי להסיר אותו:
queue[0]. - תור הוא ריק כאשר
len(queue) == 0. - בדוק שהוא לא ריק לפני ההורדה.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
הערה על מהירות
pop(0)צריך להזיז כל פריט אחר קדימה במיקום אחד.- עבור תור גדול זה איטי, ולכן משמש יותר זמן.
- מערכות אמיתיות משתמשות בממלא מעגלי עם נדנדים ראש ואחורי במקום זאת.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
בפסאודוקוד קמברידג'
- המבחן בונה תור מארגון עם נדנד
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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
טעויות נפוצות
- תור הוא היכנס ראשון, יציאה ראשונה: הצטרף לסוף, לצא מהראש.
- בדוק שהוא לא ריק לפני ההורדה.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
כעת תנסו בעצמכם
- השתמש ברשימה כתור שלך (
appendלהוספה,pop(0)להורדה). - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
A queue is FIFO · תור הוא FIFO
A queue adds at the back and removes at the front — first in, first out. · תור מוסיף באחור ומסיר בחזית — הראשון שנכנס, הראשון שיצא.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · התחל בתור ריק. הוסף לתור "a", לאחר מכן "b", ואז "c". לאחר מכן הסר מתור פעם אחת, ושמור את הערך המוסר ב-first. (first אמור להיות "a" והתור צריך להיות ["b", "c"].)
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · הוסף לתור 1, 2, 3, ולאחר מכן הסר אותם כולם ל-result. בניגוד לאקדמיה, תור שומר על אותו סדר. (result אמור להיות [1, 2, 3].)
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · כתוב פונקציה serve(queue) שמחזירה את הפריט הקדום ביותר: מסירה מהרשימה וחזרה עליו. הרשימה של הקורא צריכה להפוך לקצרה יותר.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · כתוב פונקציה front(queue) שמחזירה את הפריט הקדום ביותר בלי להסירו, כך שהתור נשאר ללא שינוי. אם התור ריק, החזר None.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.