Stacks and queues (array-backed) · ערימות ותורות (תומכות במערך)
Two ways to hold items
- A stack and a queue both hold a line of items, but they differ in which item comes out next.
- A stack is LIFO: Last In, First Out — like a pile of plates.
- A queue is FIFO: First In, First Out — like a line of people.
שתי דרכים לאחסון פריטים
- ערימה ותור שניהם אחסנים סדרה של פריטים, אך הם שונים באיזה פריט יוצא קודם.
- לערימה יש אופי LIFO: אחרון נכנס, ראשון יוצא — כמו ערימת צלחות.
- לתור יש אופי FIFO: ראשון נכנס, ראשון יוצא — כמו תור אנשים.
A stack is LIFO
- push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
- The last item you pushed is the first one you pop.
- We store the items in an array
dataand an indextopthat counts how many are in.
מאגר הוא LIFO
- push מוסיף פריט בראש. pop מסיר ומחזיר את הפריט הראשון. peek מסתכל בראש מבלי להסירו.
- הפריט האחרון שהוספת הוא הראשון שיצא.
- אנו מאחסנים את הפריטים במערך ⟨
data⟩ ומייצג ⟨top⟩ הסופר כמה יש בהם.
Array-backed stack
- With
topas the count, the top item is atdata[top - 1]. - push: write at
data[top], thentop++. pop:top--, then returndata[top]. - (For these tasks the array is big enough; you do not need to check for "full".)
ערימה המבוססת על מערך
- כאשר ⟨
top⟩ הוא הספירה, הפריט הראשון נמצא בdata[top - 1]. - push: כתוב ב-
data[top], ולאחר מכן עדכן ב-top++. pop: עדכן ב-top--, ולאחר מכן החזר ב-data[top]. - (למשימות אלו המערך גדול מספיק; אין צורך לבדוק אם הוא "מלא".)
A queue is FIFO
- enqueue adds an item at the back. dequeue removes and returns the item at the front.
- The first item you enqueue is the first one you dequeue.
- We keep two indexes:
front(next to leave) andback(next free slot).
תור הוא FIFO
- enqueue מוסיף פריט באחור. dequeue מסיר ומחזיר את הפריט בראש.
- הפריט הראשון שהוספת הוא הראשון שיצא.
- אנו שומרים שני מייצגים: ⟨
front⟩ (הבא ליציאה) וback(החלל החופשי הבא).
Array-backed queue
- enqueue: write at
data[back], thenback++. dequeue: readdata[front], thenfront++, and return it. frontchasesbackas items come and go.- (For these tasks the array is big enough; you do not need to wrap around or check for "empty".)
תור המבוסס על מערך
- הוספה לתור (enqueue): כתוב ב
data[back], לאחר מכן בback++. הוצאה מתור (dequeue): קרא בdata[front], לאחר מכן בfront++, והחזר את הערך. frontרודף אחרbackכאשר פריטים נכנסים ויוצאים.- (למשימות אלו המערך גדול מספיק; אין צורך לעטוף או לבדוק "רוק".)
Common mistakes
- A stack is last-in-first-out; a queue is first-in-first-out.
- Check the structure is not empty before you pop or dequeue.
טעויות נפוצות
- ערימה היא אחרון-נכנס-ראשון-יוצא; תור הוא ראשון-נכנס-ראשון-יוצא.
- בדוק שהמבנה אינו ריק לפני ביצוע פעולת הוצאה (pop) או ההוצאה מתור (dequeue).
Now you try
- The
StackandQueuestructs are given in the starter. Uses->top,q->front, andq->back. - Do not write a
main— the checker provides one.
כעת תנסו בעצמכם
- המבנים
StackוQueueנתונים בקובץ ההתחלתי. השתמש בs->top,q->frontובq->back. - אל תכתוב
main— הבוקר מספק אותו already.
Stacks and queues · ערימות ותורות
A stack is LIFO; a queue is FIFO. Step through the operations. · ערימה היא LIFO; תורה היא FIFO. עבור על הפעולות.
The Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and int pop(Stack *s) so the stack is LIFO. Do not write a main. · המבנה (struct) Stack (כולל ⟨⟩data ומניין ⟨⟩top) נתון. שלים את void push(Stack *s, int v) ו-int pop(Stack *s) כך שהסטק יהיה LIFO. אל תכתוב main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
The Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not write a main. · המבנה Stack נתון. השלם את int peek(const Stack *s) כדי להחזיר את הפריט העליון בלי להסירו. הנחה שהערימה אינה ריקה. אל תכתוב פונקציית main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
The Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and int dequeue(Queue *q) so the queue is FIFO. Do not write a main. · המבנה Queue (עם data, front, ו-back) נתון. השלם את void enqueue(Queue *q, int v) ו-int dequeue(Queue *q) כך שהתורה תהיה FIFO. אל תכתוב פונקציית main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.