ערימות ותורות (תומכות במערך)
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
שתי דרכים לאחסון פריטים
- ערימה ותור שניהם אחסנים סדרה של פריטים, אך הם שונים באיזה פריט יוצא קודם.
- לערימה יש אופי LIFO: אחרון נכנס, ראשון יוצא — כמו ערימת צלחות.
- לתור יש אופי FIFO: ראשון נכנס, ראשון יוצא — כמו תור אנשים.
מאגר הוא LIFO
- push מוסיף פריט בראש. pop מסיר ומחזיר את הפריט הראשון. peek מסתכל בראש מבלי להסירו.
- הפריט האחרון שהוספת הוא הראשון שיצא.
- אנחנו מוחקים את הפריטים במערך
dataואינדקסtopסופר כמה מהם בקיום.
ערימה המבוססת על מערך
- עם
topכספירה, הפריט העליון נמצא ב-data[top - 1]. - push: כתוב ב-
data[top], ולאחר מכן עדכן ב-top++. pop: עדכן ב-top--, ולאחר מכן החזר ב-data[top]. - (למשימות אלו המערך גדול מספיק; אין צורך לבדוק אם הוא "מלא".)
תור הוא FIFO
- enqueue מוסיף פריט באחור. dequeue מסיר ומחזיר את הפריט בראש.
- הפריט הראשון שהוספת הוא הראשון שיצא.
- אנחנו משמרים שני אינדקסים:
front(הבא לצאת) ו-back(החריג הבא הפנוי).
תור המבוסס על מערך
- הוספה לתור (enqueue): כתוב ב
data[back], לאחר מכן בback++. הוצאה מתור (dequeue): קרא בdata[front], לאחר מכן בfront++, והחזר את הערך. frontרודף אחרbackכאשר פריטים נכנסים ויוצאים.- (למשימות אלו המערך גדול מספיק; אין צורך לעטוף או לבדוק "רוק".)
טעויות נפוצות
- ערימה היא אחרון-נכנס-ראשון-יוצא; תור הוא ראשון-נכנס-ראשון-יוצא.
- בדוק שהמבנה אינו ריק לפני ביצוע פעולת הוצאה (pop) או ההוצאה מתור (dequeue).
כעת תנסו בעצמכם
- המבנים
StackוQueueנתונים בקובץ ההתחלתי. השתמש בs->top,q->frontובq->back. - אל תכתוב
main— הבוקר מספק אותו already.
חקור
ערימות ותורות
ערימה היא LIFO; תורה היא FIFO. עבור על הפעולות.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
המבנה Stack (עם data וספירת top) נתון. השלם את void push(Stack *s, int v) וint pop(Stack *s) כך שהמערכת תהיה LIFO. אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
המבנה Stack נתון. השלם את int peek(const Stack *s) כדי להחזיר את הפריט העליון בלי להסירו. הנחה שהערימה אינה ריקה. אל תכתוב פונקציית main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
המבנה Queue (עם data, front, ו-back) נתון. השלם את void enqueue(Queue *q, int v) ו-int dequeue(Queue *q) כך שהתורה תהיה FIFO. אל תכתוב פונקציית main.
לחץ על הרץ כדי לראות את התוצא כאן.