מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורים/תרגילים

מימוש תור בעזרת שתי מחסניות

שאלה

אנא הצע מימוש לתור בעזרת שתי מחסניות, כך שאם סך מספר הפעולות על התור הוא $\displaystyle n$, אז סדרת הפעולות תעבוד בזמן $\displaystyle \Theta (n)$.

תשובה

הרעיון הכללי

נממש את התור כך שיכיל שתי מחסניות:

1. in-stack תשמש אותנו להכנסת איברים.
2. out-stack תשמש אותנו להוצאת איברים.

כאשר דוחפים איבר v (לתור), פשוט דוחפים אותו למחסנית in-stack שבתור.

דוגמה: כך ייראה התור בתחילה: מימוש תור בעזרת שתי מחסניות - מצב התחלתי. נניח שלאחר יצירת התור אנו דוחפים את 3 לתוכו. כך ייראה התור: מימוש תור בעזרת שתי מחסניות - דחיפת 3. אם נדחוף לתור כעת 5, כך ייראה התור: מימוש תור בעזרת שתי מחסניות - דחיפת 5.

בפעולת Dequeue, ננסה לבדוק האם אפשר לשלוף מout-stack. אם כן - סיימנו, אם לא, ראשית נעביר את כל האיבר מin-stack לout-stack, ואז נשלוף מתוכו.

דוגמה: נניח שאנו שולפים כעת מהתור. היות שout-stack ריק, ראשית נעביר בלולאה את כל האיברים מin-stack אליו. כך הוא ייראה: מימוש תור בעזרת שתי מחסניות - שליפת 3 - צעד 1. כעת נשלוף מראש out-stack: מימוש תור בעזרת שתי מחסניות - שליפת 3 - צעד 2.

עכשיו תורכם: כיצד ייראה התור אם נדחוף אליו את 11?

פתרון

נדחוף זאת כרגיל לin-stack:

מימוש תור בעזרת שתי מחסניות - דחיפת 11.

עכשיו תורכם: כעת, כיצד ייראה התור אם נשלוף איבר?

פתרון

היות שout-stack אינו ריק, פשוט נשלוף את האיבר הראשון מתוכו (כלומר 5):

מימוש תור בעזרת שתי מחסניות - שליפת 5.

מימוש תור בעזרת שתי מחסניות - שליפת 5.

פסוודו-קוד

להלן מבנה התור (במימוש זה). הוא פשוט מכיל שתי מחסניות.

# A queue (implemented usin-stackg two stacks)
Queue
1	in-stack # A stack to which to Push elements.
2	out-stack # A stack from which to Dequeue elements.

כאשר דוחפים איבר v (לתור), פשוט דוחפים אותו למחסנית in-stack שבתור:

Enqueue(q, v)
1	Push(q.in-stack, v)

בפעולת Dequeue, ננסה לבדוק האם אפשר לשלוף מout-stack. אם כן - סיימנו, אם לא, ראשית נעביר את כל האיבר מin-stack לout-stack, ואז נשלוף מתוכו:

Dequeue(q)
1	if Size(q.out-stack) == 0
2		while Size(q.in-stack) > 0
3			v = Pop(q.in-stack)
4			Push(q.out-stack, v)
		
5	return Pop(q.out-stack)

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

Size(q)
1	return Size(q.in-stack) + Size(q.out-stack)

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

Empty(q)
1	return Empty(q.in-stack) and Empty(q.out-stack)

עכשיו תורכם: כיצד תממש את פעולת Front, המחזירה את האיבר הראשון המועמד להוצאה (אך אינה משנה את תוכן התור)?

פתרון

נממש זאת באופן דומה לזה שבDequeue של התור, אך נשתמש בTop של מחסנית, כך:

Front(q)
1	if Size(q.out-stack) == 0
2		while Size(q.in-stack) > 0
3			v = Dequeue(q.in-stack)
4			Push(q.out-stack, v)
		
5	return Top(q.out-stack)

הוכחת נכונות

משפט: נניח שבin-stack יושבים $\displaystyle \ell$ איברים: $\displaystyle u_{1},\ldots ,u_{\ell }$ ‏ ($\displaystyle u_{1}$ הוא האיבר הראשון שיישלף מהמחסנית , ו$\displaystyle v_{\ell }$ האחרון), ונניח שבout-stack יושבים $\displaystyle m$ איברים: $\displaystyle v_{1},\ldots ,v_{m}$ ‏ ($\displaystyle v_{1}$ הוא האיבר הראשון שיישלף מהמחסנית , ו$\displaystyle v_{\ell }$ האחרון). אז $\displaystyle v_{1},\ldots ,v_{m},u_{\ell },\ldots ,u_{1}$ (לפי סדר זה, משמאל לימין), הם בדיוק $\displaystyle m+\ell$ האיברים האחרונים שהוכנסו לתור וטרם הוצאו (כלומר $\displaystyle v_{1}$ הוא האיבר המוקדם ביותר שהוכנס וטרם נשלף, ו$\displaystyle u_{\ell }$ הוא האיבר המאוחר ביותר שהוכנס וטרם נשלף).

להלן טענת המשפט באופן גרפי:

טענת הנכונות.

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

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

(מעבר האינדוקציה) נניח שהטענה נכונה לאחר מספר פעולות: כעת בin-stack יושבים $\displaystyle u_{1},\ldots ,u_{\ell }$, בout-stack יושבים $\displaystyle v_{1},\ldots ,v_{m}$, והטענה מתקיימת עד כה. נראה שהטענה מתקיימת לאחר הפעולה הבאה:

1. אם הפעולה הבאה היא Size (או Empty) או ‎Top, שום דבר אינו משתנה, והטענה בוודאי נכונה.
2. אם הפעולה הבאה היא Push של איבר u, אז out-stack לא ישתנה, ותוכן in-stack יהפוך להיות $\displaystyle u,u_{1},\ldots ,u_{m}$. ואכן, לפי הנחת האינדוקציה, $\displaystyle v_{1},\ldots ,v_{m},u_{\ell },\ldots ,u_{1},u$ (לפי סדר זה, משמאל לימין), הם בדיוק $\displaystyle m+\ell +1$ האיברים האחרונים שהוכנסו לתור וטרם הוצאו. תוכל לראות זאת בתרשים בהמשך.
3. אם הפעולה הבאה היא ‎Top, יש שתי אפשרויות:
   1. אם out-stack אינה ריקה, אז שום דבר אינו משתנה, והטענה בוודאי נכונה.
   2. אם in-stack ריקה, אז לאחר 2-4 בFront, ‏ in-stack תהיה ריקה, וout-stack תכיל את האיברים $\displaystyle u_{\ell },\ldots ,u_{1}$ (כלומר $\displaystyle u_{\ell }$ האיבר הבא שיישלף). ואכן, לפי הנחת האינדוקציה $\displaystyle u_{\ell },\ldots ,u_{1}$ בדיוק $\displaystyle \ell$ האיברים האחרונים שהוכנסו וטרם הוצאו. תוכל לראות זאת בתרשים בהמשך.
4. אם הפעולה הבאה היא ‎Dequeue, הטענה דומה מאד לטענה ב‎Dequeue.

להלן תיאור גרפי של המצב בPush:

טענת הנכונות במקרה Push.

להלן תיאור גרפי של המצב בTop בו out-stack ריק בתחילה:

טענת הנכונות במקרה top.

ניתוח סיבוכיות

משפט: הסיבוכיות של $\displaystyle n$ פעולות הנה $\displaystyle O(n^{2})$.

הוכחה: מהתבוננות בפונקציות, קל לראות את הדברים הבאים:

1. כל אחת מפעולות התור, למעט Dequeue (וTop), הנה $\displaystyle O(1)$.
2. Dequeue (או לחלופין Top) הנה $\displaystyle \Theta (n')$, כאשר $\displaystyle n'$ הוא מספר הפעולות במחסנית in-stack בעת הקריאה.

אפשר לראות זאת מכך שהלולאה היחידה היא 1-3 בDequeue (או לחלופין Top), וכל אחת מפעולות הרשימה המקושרת היא $\displaystyle O(1)$.

אם מבצעים $\displaystyle n$ פעולות, הרי שבכל קריאה לDequeue יהיו לכל היותר $\displaystyle n$ איברים במחסנית. מכאן נקבל שזמן הריצה חסום מלמעלה על ידי $\displaystyle n\cdot O(n)=O(n^{2})$.

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

משפט: הסיבוכיות של $\displaystyle n$ פעולות הנה $\displaystyle \Theta (n)$.

עכשיו תורכם: וודא שהנך מבין מדוע שני המשפטים אינם סותרים זה את זה.

ראשית, קל לראות כי הסיבוכיות הנה $\displaystyle \Omega (n)$, משום שאנו מבצעים $\displaystyle n$ קריאות לפונקציות, וכל אחת מהן הרי $\displaystyle \Omega (1)$. כל שנותר, לכן, הוא להוכיח חסם $\displaystyle O(n)$. להלן שתי הוכחות לכך.

כדאי לדעת: כל אחת מההוכחות הבאות מסתמכת על צורת ניתוח הידועה בשם amortized analysis. בספר הקורס, הפרק "Amortized Analysis" עוסק בכך.

להלן ההוכחה הראשונה.

הוכחה: נוכיח את הטענה באינדוקציה על אורך סדרת הפעולות, $\displaystyle n$.

(בסיס האינדוקציה) עבור $\displaystyle n=1$ עלינו להוכיח שסדרת הפעולות (שהיא פעולה יחידה במקרה זה) הנה $\displaystyle O(1)$. ואכן, כשעוברים על הקוד של כל אחת מהפונקציות, ברור שכשהיא הפעולה הראשונה (והיחידה) בסדרת פעולות המתחילה בתור ריק - זמנה הוא $\displaystyle O(1)$.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל $\displaystyle n'$ קטן (ממש) מ$\displaystyle n$, ונראה שהיא נכונה ל$\displaystyle n$. כפי שהזכרנו, ברור מהתבוננות בקוד שרק לפעולות Dequeue וFront תתכן סיבוכיות שאיננה $\displaystyle O(1)$ (וגם זאת בהתאם למצב המחסניות) - לכל אחת מהפעולות האחרות בוודאות סיבוכיות $\displaystyle O(1)$. אם בסדרת הפעולות לא נקראה אף אחת משתי פעולות אלו, ברור שהסיבוכיות היא $\displaystyle n\cdot O(1)=O(n)$. אחרת, נגדיר כ$\displaystyle n'$ את מספר הפעולה האחרונה בסדרת הפעולות שהיתה מסוג Dequeue או Front (כל אחת מהפעולות אחריהן יכולה להיות, נניח, Enqueue, אך לא אחת משתי אלו). סיבוכיות סדרת הפעולות מ1 עד (כולל) $\displaystyle n'$ היא $\displaystyle O(n')$, וזאת מהנחת האינדוקציה. סיבוכיות שאר הפעולות היא $\displaystyle (n-n')\cdot O(1)=O(n-n')$. סך הכל, לכן, נקבל $\displaystyle O(n)+O(n-n')=O(n)$.

ולהלן הוכחה חלופית.

הוכחה: כדי לראות שסך הפעולות הן $\displaystyle O(n)$, נשים לב לעובדה הבאה. כל ערך v יכול לעבור לכל היותר פעם אחת את המסלול הבא:

1. Push(q.in-stack, v) (בקריאה לPush של התור).
2. Dequeue(q.in-stack) (בקריאה לDequeue של התור).
3. Push(q.out-stack, v) (בקריאה לDequeue של התור).

לכן כל איבר שנדחף לתור יכול לתרום לכל היותר $\displaystyle O(1)$ לסיבוכיות רצף הפעולות. ברור שברצף של $\displaystyle n$ פעולות, יידחפו לתור לכל היותר $\displaystyle n$ איברים.