מבנה נתונים תור Queue - הבנה ויישום בפייתון

תור queue הוא מבנה נתונים המשמש לאחסון רשימה של אלמנטים בסדר מסוים. הוא דומה לאנשים העומדים בתור לקופה בסופר כאשר האדם הראשון אשר הצטרף לתור הוא גם הראשון לקבל שירות, בעוד האדם האחרון בתור הוא האחרון לקבל את השירות.

כאשר משתמשים בתור queue הפריטים מתווספים בצד אחד הידוע כאחורי התור (rear ,tail), ומוסרים מהצד השני, הידוע בתור ראש התור head of the queue. סדר זה של "ראשון נכנס - ראשון יוצא" מכונה FIFO, First-In First-Out.

ב-Queues משתמשים לצורך ניהול משימות ברשת האינטרנט או אירועים events בתוכנה לפי הסדר בו התקבלו. לדוגמה, שרת יכול לקבל פניות request רבות, את ה-request הראשונה הוא ישים בראש התור ואת האחרונה בסוף התור, כדי שיוכל לטפל בכל פנייה על פי הסדר בו התקבלה מתחילת התור ועד סופו.

במדריך זה ניישם queues בפייתון.

2 הפעולות הבסיסיות על queues הם הכנסה insert (enqueue) והסרה delete (dequeue). את האלמנטים מוסיפים לסוף התור ואת המחיקה מבצעים על ראש התור על פי העיקרון המסדר של "ראשון נכנס - ראשון יוצא" FIFO.

נראה דוגמה לתור queue עם 5 מקומות:

נוסיף enqueue את הפריט "A" לסוף התור:

• אמרנו שמוסיפים לסוף התור אבל הפריט נוסף, במקרה זה, לתחילתו בגלל שהתור ריק.

נוסיף את האלמנטים "B" ו-"C" :

• הוספה ל-queue היא תמיד לסוף התור

נסיר אלמנט dequeue מתחילת התור:

• נסיר תמיד את האלמנט הראשון מראש התור. לכן אין צורך שהפונקציה dequeue תקבל ארגומנטים, כפי שנראה בהמשך בחלק המוקדש ליישום.

נוסיף אלמנט "D" לסוף התור:

נסיר אלמנט. תמיד מראש התור:

נסיר אלמנט:

נסיר אלמנט:

• ה-queue ריק עכשיו.

יישום של Queue בפייתון באמצעות מערך

ניתן לייצר מבנה נתונים תור queue בפייתון באמצעות מערך.

ניצור קלאס Queue שהדבר הראשון שהוא יעשה בכל פעם שניצור ממנו אובייקט הוא ליצור משתנה queue ממערך:

class Queue: 
    def __init__(self): 
        self.queue = []

המתודה enqueue() תשמש להוספת אלמנט לסוף התור. נוסיף את המתודה לקלאס:

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        # Add the item to the back of the queue
        self.queue.append(item)

• המתודה enqueue() מוסיפה פריט לסוף התור באמצעות המתודה append().

המתודה dequeue() תסיר אלמנט מראש התור. נוסיף גם אותה:

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        # Add the item to the back of the queue
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            # Remove and return the front element of the queue
            return self.queue.pop(0)
        else:
            raise IndexError("Queue is empty. Cannot dequeue.")

• המתודה dequeue() מסירה ומחזירה אלמנט מראש התור באמצעות pop(0) .

נוסיף לקלאס 3 מתודות נוספות: is_empty() המחזירה ערך בוליאני True או False, peek() כדי להציץ באלמנט בראש התור מבלי להסיר אותו, size() המחזירה את מספר האלמנטים.

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        # Add the item to the back of the queue
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            # Remove and return the front element of the queue
            return self.queue.pop(0)
        else:
            raise IndexError("Queue is empty. Cannot dequeue.")

    def is_empty(self):
        # Check if the queue is empty
        return len(self.queue) == 0

    def size(self):
        # Get the size of the queue
        return len(self.queue)

    def peek(self):
        if not self.is_empty():
            # Return the front element of the queue without dequeuing it
            return self.queue[0]
        else:
            raise IndexError("Queue is empty. Cannot peek.")

• המתודה is_empty() מחזירה True אם התור ריק, אחרת False.
• המתודה peek() מחזירה את האלמנט בראש התור בלי להסיר אותו. אם התור ריק היא זורקת Exception.
• המתודה size() מחזירה את אורך התור.

נבחן את הקלאס Queue:

# Create a new queue
my_queue = Queue()

# Enqueue elements to the queue
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)

# Check the front element of the queue without dequeuing it
print(my_queue.peek())  # Output: 10

# Dequeue elements from the queue
print(my_queue.dequeue())  # Output: 10
print(my_queue.dequeue())  # Output: 20

# Check if the queue is empty
print(my_queue.is_empty())  # Output: False

# Get the size of the queue
print(my_queue.size())  # Output: 1

יישום של Queue בפייתון באמצעות deque

את מבנה הנתונים queue אפשר ליישם בפייתון באמצעות deque שהיא doubly linked list בגלל שזמן ההוספה וההסרה של הפריטים משני צדי ה-deque הוא O(1) היעיל ביותר האפשרי (אם זה לא ברור נא לקרוא על big-O ביטוי ליעילות הקוד).

נייבא את deque ממודול collections:

from collections import deque

ניצור קלאס Queue שהדבר הראשון שהוא יעשה בכל פעם שניצור ממנו אובייקט הוא ליצור משתנה queue מ- collections.deque:

class Queue: 
    def __init__(self): 
        self.queue = deque()

המתודה enqueue() תשמש להוספת אלמנט לסוף התור. נוסיף את המתודה לקלאס:

from collections import deque 

class Queue: 
    def __init__(self): 
        self.queue = deque()

    def enqueue(self, item): 
        self.queue.append(item)

• המתודה enqueue() מוסיפה פריט לסוף התור באמצעות המתודה append() של הקלאס deque.

המתודה dequeue תסיר אלמנט מראש התור. נוסיף גם אותה:

from collections import deque 

class Queue: 
    def __init__(self): 
        self.queue = deque()

    def enqueue(self, item): 
        self.queue.append(item)

    def dequeue(self): 
        return self.queue.popleft() 

• המתודה dequeue() מסירה ומחזירה אלמנט מראש התור באמצעות popleft() .

נוסיף לקלאס 3 מתודות נוספות: is_empty() המחזירה ערך בוליאני True או False, peek() כדי להציץ באלמנט בראש התור מבלי להסיר אותו, size() המחזירה את מספר האלמנטים.

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        else:
            return None

    def is_empty(self):
        return len(self.queue) == 0


    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            return None

    def size(self):
        return len(self.queue)

• המתודה is_empty() מחזירה True אם התור ריק, אחרת False.
• המתודה peek() מחזירה את האלמנט בראש התור בלי להסיר אותו. אם התור ריק מחזירה 0.
• המתודה size() מחזירה את אורך התור.

פתרון לסידור הלו"ז באמצעות queue

תיאור הבעיה: נתונה רשימת משימות שאתה צריך לסדר על פי מידת הדחיפות, כל אחת מהם מיוצגת בתוך טאפל הכולל 2 פריטי מידע:

(task_name, priority)

• שם המשימה
• מידת הדחיפות: "high" או "low"

עליך לסדר את המשימות על פי מידת הדחיפות שלהם. לצורך כך כתוב פונקציה: order_tasks(tasks) אשר מקבלת רשימה של משימות כקלט ומחזירה רשימה מסודרת של המשימות על פי מידת הדחיפות שלהם. הסדר צריך לקיים:

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

דוגמה לקלט ופלט:

Input: tasks = [("task1", "high"), ("task2", "low"), ("task3", "high"), ("task4", "low")] 
Output: [("task1", "high"), ("task3", "high"), ("task2", "low"), ("task4", "low")]

הפתרון נמצא בהמשך. לפני שאתה ממשיך לקרוא הלאה תנסה לפתור בעצמך.

הצעה לפתרון:

def order_tasks(tasks):
    """
    Order a list of tasks by priority.

    Args:
        tasks: A list of tasks, each of which is a tuple of (task_name, task_priority).

    Returns:
        A list of tasks in order of priority.
    """

    # Create two queues, one for high-priority tasks and one for low-priority tasks.
    hi_q = deque()
    lo_q = deque()

    # Iterate through the list of tasks and add each task to the appropriate queue.
    for task in tasks:
        _, task_priority = task
        if task_priority == "low":
            lo_q.append(task)
        else:
            hi_q.append(task)

    # Create a new list to store the ordered tasks.
    order = []

    # While there are still tasks in the high-priority queue, add them to the order list.
    while len(hi_q) > 0:
        order.append(hi_q.popleft())

    # While there are still tasks in the low-priority queue, add them to the order list.
    while len(lo_q) > 0:
        order.append(lo_q.popleft())

    # Return the ordered list of tasks.
    return order


# Create a list of tasks.
tasks = [("task1", "high"), ("task2", "low"), ("task3", "high"), ("task4", "low")]

# Order the tasks by priority.
res = order_tasks(tasks)

# Print the ordered tasks.
print(res)

• הפונקציה order_tasks() מסדרת רשימה של מטלות על פי מידת הדחיפות שלהם.
• הפונקציה מתחילה מיצירת שני תורים queues, אחד למשימות בדחיפות גבוהה והשנייה למשימות בדחיפות נמוכה.
• הפונקציה עוברת בלולאה על רשימת המטלות ומוסיפה כל מטלה לתור המתאים על פי מידת דחיפותו.
• לבסוף, הפונקציה ממזגת את שני התורים ומחזירה תוצאה שהיא הרשימה המסודרת של המטלות.
• השימוש בקלאס deque ליצירת התורים מייעל את ביצועי הפונקציה.
• הפונקציה מסוגלת לטפל אף במקרים בהם רשימת המטלות היא ריקה.

סיכום

במדריך זה הסברנו על queue (תור) שהוא מבנה נתונים יסודי בעולם המחשבים אשר מסדר את המידע על פי העיקרון של "ראשון נכנס - ראשון יוצא" FIFO. השימוש ב-queues נפוץ במגוון תרחישים כדוגמת ניהול ותזמון משימות כאשר חשוב לשמור על הסדר.

למדנו על הפעולות הבסיסיות של queues שהם: enqueue להוספת אלמנט לאחורי התור, ו-dequeue להסרת אלמנט מראש התור. כדי ליישם queue, השתמשנו בקלאס collections.dequeue המובנה של פייתון, המספק אופרציות enqueue ו-dequeue יעילות.

בנוסף, למדנו 2 בעיות שנותנות תחושה לגבי סוג הבעיות שניתן לפתור באמצעות queue.

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

מדריכים נוספים בסדרה ללימוד פייתון

stacks, ערימות וחידות

אלגוריתם Selection Sort מיון בחירה

אלגוריתם חיפוש בינארי - מהבנה ליישום

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים