במדעי המחשב, תור הוא מבנה נתונים ליניארי שבו הרכיבים מוכנסים לקצה אחד ומוסרים מהקצה השני על פי עקרון ה-'first-in, first-out' (FIFO). ניתן להשתמש במבנה נתונים זה לשליטה ברצף פעולה או לאחסון נתונים. C היא שפת מחשב עם יכולת תור המשולבת בצורה של מערכים או רשימות מקושרות.
מאפיינים:
- תור הוא סוג של מבנה נתונים ליניארי שניתן לבנות עם מערך או רשימה מקושרת.
- אלמנטים מועברים לחלק האחורי של התור תוך הסרה מלפנים.
- Enqueue (הוסף אלמנט מאחור) ו-dequeue (הסר אלמנט מלפנים) הן שתי פעולות תור.
- כאשר אלמנטים מתווספים ומוסרים לעתים קרובות, תור עשוי להיבנות כתור מעגלי כדי למנוע בזבוז זיכרון.
שימוש במערך:
כדי ליישם תור ב-C באמצעות מערך, תחילה הגדר את הגודל המקסימלי של התור והכריז על מערך בגודל זה. המספרים השלמים הקדמי והאחורי נקבעו בהתאמה ל-1. המשתנה הקדמי מייצג את האלמנט הקדמי של התור, והמשתנה האחורי מייצג את האלמנט האחורי.
לפני שדוחפים את האלמנט החדש למיקום הסופי של התור, עלינו להגדיל את המשתנה האחורי ב-1. התור מלא כעת ולא ניתן להוסיף עוד אלמנטים נוספים כאשר המיקום האחורי מגיע לקיבולת המקסימלית של התור. אנו מוסיפים אלמנט לקדמת התור ומגדילים את המשתנה הקדמי באחד בלבד כדי להסיר אלמנט מהתור. אם המיקום הקדמי והאחורי שווים ולא ניתן למחוק רכיבים נוספים, מכאן שאנו יכולים לומר שהתור ריק.
חיבור java mysql
להלן מופע של תור שנכתב ב-C שעושה שימוש במערך:
שפת תכנות C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } הפלט של הקוד יהיה:
תְפוּקָה:
compareto ב-java
10 20 30 Queue is empty-1
הֶסבֵּר:
- ראשית, אנו מעמידים שלושה אלמנטים 10, 20 ו-30 בתור.
- לאחר מכן, אנו מעמידים בתור ומדפיסים את הרכיב הקדמי של התור, שהוא 10.
- לאחר מכן, אנו מעמידים את התור ומדפיסים שוב את האלמנט הקדמי של התור, שהוא 20.
- לאחר מכן, אנו מעמידים את התור ומדפיסים שוב את הרכיב הקדמי של התור, שהוא 30.
- לבסוף, אנו עושים תור מתור ריק שמוציא 'תור ריק' ומחזיר -1.
שימוש ברשימה מקושרת:
גישה חלופית נוספת לבניית תור בשפת התכנות C היא שימוש ברשימה מקושרת. כל אחד מהצמתים בתור מבוטא בשיטה זו על ידי צומת המכיל את ערך האלמנט ומצביע לצומת הבא בתור. על מנת לעקוב אחר הצמתים הראשונים והאחרונים בתור, בהתאמה, נעשה שימוש במצביעים קדמיים ואחוריים.
אנו מקימים צומת חדש עם ערך האלמנט ומגדירים את המצביע הבא שלו ל-NULL כדי להוסיף אלמנט לתור. לצומת החדש, אנו מגדירים את המצביעים הקדמיים והאחוריים אם התור ריק. אם לא, אנו מעדכנים את המצביע האחורי ומגדירים את המצביע הבא של הצומת האחורי הישן כך שיצביע על הצומת החדש.
בעת מחיקת צומת מתור, הצומת הקודם נמחק תחילה, לאחר מכן המצביע הקדמי מתעדכן לצומת העוקב בתור, ולבסוף משתחרר הזיכרון שהצומת שהוסר תפס. אם המצביע הקדמי הוא NULL לאחר ההסרה, התור ריק.
מערך מחרוזות ג
הנה דוגמה לתור מיושם ב-C באמצעות רשימה מקושרת:
שפת תכנות C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } הפלט של הקוד יהיה:
תְפוּקָה:
10 20 30 Queue is empty-1
הֶסבֵּר:
- ראשית, אנו מעמידים שלושה אלמנטים 10, 20 ו-30 בתור.
- לאחר מכן, אנו מעמידים בתור ומדפיסים את הרכיב הקדמי של התור, שהוא 10.
- לאחר מכן, אנו מעמידים את התור ומדפיסים שוב את האלמנט הקדמי של התור, שהוא 20.
- לאחר מכן, אנו מעמידים את התור ומדפיסים שוב את הרכיב הקדמי של התור, שהוא 30.
- לבסוף, אנו מנסים לעמוד בתור מהתור הריק, שמדפיס את ההודעה 'תור ריק' ומחזיר -1.
יתרונות:
- תורים שימושיים במיוחד להטמעת אלגוריתמים הדורשים עיבוד של אלמנטים ברצף מדויק, כגון חיפוש ברוחב ראשון ותזמון משימות.
- מכיוון שלפעולות תור יש מורכבות זמן O(1), ניתן לבצע אותן במהירות אפילו בתורים עצומים.
- התורים גמישים במיוחד מכיוון שהם עשויים להיות מיושמים פשוט באמצעות מערך או רשימה מקושרת.
חסרונות:
- תור, שלא כמו מחסנית, לא ניתן לבנות עם מצביע בודד, מה שהופך את יישום התור למעורב מעט יותר.
- אם התור בנוי כמערך, הוא עלול להתמלא בקרוב אם יתווספו יותר מדי אלמנטים, וכתוצאה מכך חששות ביצועים או אולי קריסה.
- כאשר משתמשים ברשימה מקושרת כדי ליישם את התור, תקורה של הזיכרון של כל צומת יכולה להיות משמעותית, במיוחד עבור אלמנטים קטנים.
סיכום:
יישומים המשתמשים בתורים, מבנה נתונים מכריע, כוללות מערכות הפעלה, רשתות ומשחקים, אם להזכיר רק כמה. הם אידיאליים עבור אלגוריתמים שחייבים לטפל באלמנטים בסדר מסוים מכיוון שהם פשוטים ליצירה באמצעות מערך או רשימה מקושרת. עם זאת, לתורים יש חסרונות שיש לקחת בחשבון בעת בחירת מבנה נתונים עבור יישום מסוים, כגון צריכת זיכרון ומורכבות היישום.