תוֹכֶן

• טבלת השוואה
• הגדרת סטאק
• דוגמא
• הגדרת תור
• דוגמא
• יישום ערימה
• יישום תור
• פעולות בערימה
• פעולות בתור
• יישומים של סטאק
• יישומים של תור
• סיכום

ערימה ותור שניהם הם מבני הנתונים הלא פרימיטיביים. ההבדלים העיקריים בין מחסנית לתור הם שערכת המחסנית משתמשת בשיטת LIFO (אחרונה ראשונה) כדי לגשת ולהוסיף אלמנטים נתונים ואילו התור משתמש בשיטת FIFO (First in first out) כדי לגשת ולהוסיף רכיבי נתונים.

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

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

1. טבלת השוואה
2. הגדרה
3. הבדלים עיקריים
4. יישום
5. פעולות
6. יישומים
7. סיכום

טבלת השוואה

בסיס להשוואה	ערימה	תור
עקרון עבודה	LIFO (אחרון בפעם הראשונה)	FIFO (ראשון ראשונה)
מבנה	אותו קצה משמש להכנסה ומחיקה של אלמנטים.	קצה אחד משמש להחדרה, כלומר קצה אחורי וקצה אחר משמש למחיקת אלמנטים, כלומר קצה קדמי.
מספר המצביעים ששימשו	אחד	שניים (במקרה תור פשוט)
פעולות שבוצעו	דחיפה ופופ	אנקווה וסגירה
בחינת מצב ריק	למעלה == -1	חזית == -1 || קדמי == אחורי + 1
בחינת מצב מלא	למעלה == מקסימום - 1	אחורי == מקס - 1
וריאנטים	אין בו גרסאות.	יש לו גרסאות כמו תור מעגלי, תור עדיפות, תור שהסתיים כפליים.
יישום	פשוט יותר	מורכב יחסית

הגדרת סטאק

ערימה היא מבנה נתונים לינארי לא פרימיטיבי. זוהי רשימה מסודרת בה מתווסף הפריט החדש והרכיב הקיים נמחק מקצה אחד בלבד, הנקרא כראש הערימה (TOS). מכיוון שכל המחיקה וההכנסה בערימה נעשית מראש הערימה, האלמנט האחרון שנוסף יהיה הראשון שיוסר מהערימה. זו הסיבה מדוע מחסנית נקראת סוג LIFO (Last-in-First-out).

שימו לב כי האלמנט אליו ניגשים לעיתים קרובות בערימה הוא האלמנט העליון ביותר, ואילו האלמנט האחרון הזמין נמצא בתחתית הערימה.

דוגמא

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

הגדרת תור

תור הוא מבנה נתונים ליניארי מגיע בקטגוריה מהסוג הלא פרימיטיבי. זהו אוסף של אלמנטים מסוג דומה. תוספת של אלמנטים חדשים מתרחשת בקצה אחד הנקרא קצה אחורי. באופן דומה, מחיקת האלמנטים הקיימים מתרחשת בקצה השני המכונה Front-end, והיא הגיונית סוג רשימה ראשונה ראשונה (FIFO).

דוגמא

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

1. הערימה עוקבת אחר מנגנון LIFO מצד שני התור עוקב אחר מנגנון ה- FIFO כדי להוסיף ולהסיר אלמנטים.
2. בערימה, אותו קצה משמש להכנסה ולמחיקה של האלמנטים. נהפוך הוא, שני תורים שונים משמשים בתור בכדי להכניס ולמחוק את האלמנטים.
3. כמו לערימה יש רק קצה פתוח אחד וזו הסיבה לשימוש רק במצביע אחד להתייחס לראש הערימה. אך התור משתמש בשתי מצביעות בכדי להתייחס לחזית ולקצה האחורי של התור.
4. סטאק מבצעת שתי פעולות הידועות כ- push and pop ואילו בתור שלה מכונה enqueue and dequeue.
5. יישום הערימה קל יותר ואילו יישום התורים הוא מסובך.
6. לתור יש גרסאות כמו תור מעגלי, תור עדיפות, תור שהסתיים כפליים וכו ', לעומת זאת, לערימה אין גרסאות.

יישום ערימה

ניתן ליישם את הערימה בשתי דרכים:

1. יישום סטטי משתמש במערכים כדי ליצור ערימה. יישום סטטי הוא אמנם טכניקה ללא מאמץ אך אינו דרך יצירתית גמישה, מכיוון שצריך לעשות את ההכרזה על גודל הערימה במהלך תכנון התוכנית, לאחר מכן לא ניתן יהיה לשנות את הגודל. בנוסף, יישום סטטי אינו יעיל במיוחד בכל הנוגע לניצול הזיכרון. מכיוון שמוצהרים מערך (ליישום ערימה) לפני תחילת הפעולה (בזמן תכנון התוכנית). כעת אם מספר האלמנטים שיש למיין הוא פחות מאוד בערימה, הזיכרון שהוקצה סטטי יתבזבז. מצד שני, אם יש יותר אלמנטים שיש לאחסן בערימה אז לא נוכל לשנות את גודל המערך כדי להגדיל את הקיבולת שלו, כך שהוא יכול להכיל אלמנטים חדשים.
2. יישום דינמי נקרא גם ייצוג רשימת מקושרים ומשתמש במצבים כדי ליישם את סוג הערימה של מבנה הנתונים.

יישום תור

ניתן ליישם תור בשתי דרכים:

1. יישום סטטי: אם מיושם תור באמצעות מערכים, יש להבטיח את המספר המדויק של האלמנטים שברצוננו לאחסן בתור לפני כן, מכיוון שצריך להכריז על גודל המערך בזמן העיצוב או לפני תחילת העיבוד. במקרה זה, תחילת המערך תהפוך לחזית התור, והמיקום האחרון של המערך ישמש כקצה האחורי של התור. הקשר הבא נותן את כל האלמנטים להתקיים בתור כאשר הם מיושמים באמצעות מערכים:
   קדמי - אחורי + 1
   אם "אחורי <קדמי" אז לא יהיה אלמנט בתור או שתור תמיד יהיה ריק.
2. יישום דינמי: הטמעת תורים באמצעות מצביעים, החיסרון העיקרי הוא שצומת בייצוג מקושר גוזל יותר שטח זיכרון מאשר אלמנט מתאים בייצוג המערך. מכיוון שיש לפחות שני שדות בכל צומת אחד לשדה הנתונים ואחרים לאחסון הכתובת של הצומת הבא ואילו בייצוג מקושר רק שדה נתונים נמצא שם. הכשרון בשימוש בייצוג המקושר מתברר כשנדרש להכניס או למחוק אלמנט באמצע קבוצה של אלמנטים אחרים.

פעולות בערימה

הפעולות הבסיסיות שניתן להפעיל על הערימה הן כדלקמן:

1. לדחוף: כאשר מתווסף אלמנט חדש לראש הערימה נקרא פעולת PUSH. דחיקת אלמנט בערימה קוראת להוסיף את האלמנט, שכן האלמנט החדש יוכנס בחלקו העליון. לאחר כל פעולת דחיפה, החלק העליון מוגדל באחת. אם המערך מלא, ולא ניתן להוסיף אלמנט חדש, הוא נקרא מצב STACK-FULL או STACK OVERFLOW. פעולה לדחוף - פונקציה ב- C:
   שוקל הערימה מוכרז כ-
   int stack, למעלה = -1;
דחיפה בטלה ()
{
פריט int;
אם (למעלה <4)
{
f ("הזן את המספר");
סריקה ("% d", ופריט);
למעלה = למעלה + 1;
ערימה = פריט;
}
אחר
{
f ("הערימה מלאה");
}
}
2. POP: כאשר אלמנט מוחק מראש הערימה הוא מכונה פעולת POP. הערימה מצטמצמת באחת, לאחר כל פעולת פופ. אם לא נותר אלמנט בערימה והפופ מבוצע, הדבר יביא למצב STACK UNDERFLOW שפירושו שהערימה שלכם ריקה. POP OPERATION - פונקציות ב- C:
   שוקל הערימה מוכרז כ-
   int stack, למעלה = -1;
פופ ריק ()
{
פריט int;
אם (למעלה> = 4)
{
פריט = ערימה;
למעלה = למעלה - 1;
f ("המספר שנמחק הוא =% d", פריט);
}
אחר
{
f ("הערימה ריקה");
}
}

פעולות בתור

הפעולות הבסיסיות שניתן לבצע בתור הן:

1. אנקואה: להכנסת אלמנט בתור. פונקצית פעולת חיסכון ב- C:
   התור מוכרז כ-
   תור int, קדמי = -1 ומאחור = -1;
להוסיף ריק ()
{
פריט int;
אם (אחורי <4)
{
f ("הזן את המספר");
סריקה ("% d", ופריט);
אם (קדמי == -1)
{
חזית = 0;
אחורי = 0;
}
אחר
{
אחורי = אחורי + 1;
}
תור = פריט;
}
אחר
{
f ("התור מלא");
}
}

2. Dequeue: למחיקת אלמנט מהתור. פונקצית פעולת חיסכון ב- C:
   התור מוכרז כ-
   תור int, קדמי = -1 ומאחור = -1;
מחיקה בטלה ()
{
פריט int;
אם (קדמי! = -1)
{
פריט = תור;
אם (קדמי == אחורי)
{
חזית = -1;
אחורי = -1;
}
אחר
{
קדמי = קדמי + 1;
f ("המספר שנמחק הוא =% d", פריט);
}
}
אחר
{
f ("התור ריק");
}
}

יישומים של סטאק

• ניתוח בתוך מהדר.
• מכונה וירטואלית של ג'אווה.
• בטל במעבד תמלילים.
• כפתור חזרה בדפדפן אינטרנט.
• שפת PostScript עבור ers.
• יישום שיחות פונקציה במהדר.

יישומים של תור

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

סיכום

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