Implement Queue Using Stacks

+10

בנו תור מסוג ראשון נכנס, ראשון יוצא, שהאחסון היחיד שלו הוא שתי מחסניות. מחסנית יכולה רק להוסיף איבר לראש המחסנית, להסיר את האיבר שבראש המחסנית, לקרוא את האיבר שבראש המחסנית ולציין אם היא ריקה. התור תומך ב־push x (הוספת x לסוף), ב־pop (הסרת האיבר הראשון והחזרתו), ב־peek (החזרת האיבר הראשון) וב־empty (האם התור ריק?).

הפעולות ניתנות לפי הסדר בתוך ops, כאשר args[i] מכיל את הערך עבור פעולת push ואת 0 עבור כל פעולה אחרת. הריצו אותן על תור אחד שמתחיל ריק והחזירו מחרוזת אחת לכל פעולה: "null" עבור פעולת push, את המספר כטקסט עבור פעולת pop או peek, ואת "true" או "false" עבור empty.

פונקציה

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: הפעולות, לפי סדר ביצוען
argsinteger-array: הערך עבור כל פעולת push, ו־0 עבור כל פעולה אחרת
מחזירהstring-array: תשובה אחת לכל פעולה, כטקסט

אילוצים

1 ≤ ops.length ≤ 2000
args.length == ops.length
כל אחד מהערכים ב־ops[i] הוא push, pop, peek או empty.
-10⁹ ≤ args[i] ≤ 10⁹ עבור פעולת דחיפה, ו-args[i] == 0 עבור כל פעולה אחרת.
pop ו-peek נקראות רק כאשר התור מכיל לפחות פריט אחד.

דוגמאות

קלט: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
פלט: ["null", "null", "1", "1", "false"]
הסבר: אחרי הכנסת 1 ואז 2, החזית היא 1, לכן גם peek וגם pop מחזירות "1". ה־2 עדיין בפנים, לכן empty מחזירה "false".

קלט: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
פלט: ["null", "null", "4", "null", "7", "9", "true"]
הסבר: השליפה הראשונה מחזירה 4, הפריט הישן ביותר. 9 מגיע בזמן ש-7 עדיין ממתין, והוא יוצא אחרי 7 כי הוא נכנס אחריו. התור ריק כעת, ולכן התשובה האחרונה היא "true".

קלט: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
פלט: ["true", "null", "-3", "-3", "true"]
הסבר: התור מתחיל ריק, ולכן התשובה הראשונה היא "true". מספר שלילי נשמר כמו כל מספר אחר: גם peek וגם pop מחזירים "-3", ואז התור שוב ריק.

+15 בדיקות נסתרות בשליחה

שאלת המשך

איך היית מוסיף פעולה back שמחזירה את הפריט החדש ביותר ב־O(1), בלי להפר את החסם האמורטי של שאר הפעולות?

פתרון

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

סדר מחדש את כל המחסנית בכל דחיפה

האינטואיציה

שמרו את כל הפריטים בערימה אחת, main, כך שהפריט הישן ביותר יהיה למעלה. לאחר מכן pop, peek ו־empty הן פעולות בודדות על הערימה.

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

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

אלגוריתם

החזיקו שתי מחסניות: main, כשהפריט הישן ביותר נמצא למעלה, ו-helper ריקה.
עבור push x: הוציאו כל פריט מ-main והעבירו אותו ל-helper, דחפו את x ל-main, ואז הוציאו כל פריט מ-helper והחזירו אותו ל-main.
עבור pop ו-peek: הוציאו או קראו את הפריט העליון של main.
עבור empty: דווחו אם main ריקה.
תעדו כל תשובה כטקסט והחזירו את הרשימה.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

מחסניות קלט ופלט עם העברה עצלה

האינטואיציה

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

כאשר outbox ריק ומגיעה פעולת שליפה או הצצה, העבר את כל הפריטים מ־inbox אליו. הפריט החדש ביותר יוצא ראשון מ־inbox, ולכן נוחת בתחתית outbox, והפריט הוותיק ביותר נוחת בראשו. העבר פריטים רק כאשר outbox ריק: כל עוד יש בו פריטים, הם ותיקים יותר מכל מה שנמצא ב־inbox, ולכן יש להוציא אותם קודם. בדוגמה השנייה, 4 ו־7 מועברים לפני פעולת השליפה הראשונה; לאחר מכן 9 ממתין ב־inbox עד ש־7 יוצא.

פעולת שליפה אחת עשויה להעביר פריטים רבים, אבל יש לספור את העבודה לכל פריט בנפרד: כל ערך נדחף פעם אחת ל־inbox, מועבר פעם אחת ל־outbox ונשלף פעם אחת. לכן n פעולות עולות O(n) בסך הכול, כלומר O(1) בממוצע לכל פעולה. התור ריק כאשר שתי המחסניות ריקות.

אלגוריתם

שמור שתי מחסניות ריקות, inbox ו-outbox.
עבור push x: דחוף את x אל inbox.
עבור pop או peek: אם outbox ריקה, הוצא כל פריט מ-inbox ודחוף אותו אל outbox. לאחר מכן הוצא או קרא את הפריט שבראש outbox.
עבור empty: דווח אם שתי המחסניות ריקות.
תעד כל תשובה כטקסט והחזר את הרשימה.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

מלכודות ומקרי קצה

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

העברת inbox אל outbox בזמן ש-outbox עדיין מכיל פריטים. הפריטים החדשים מונחים מעל הישנים ויוצאים ראשונים, מה שמשבש את סדר התור. בדוגמה השנייה, 9 ייצא לפני 7.
דיווח על empty על סמך outbox בלבד. מיד אחרי פעולת דחיפה, הפריט החדש נמצא ב-inbox, לכן התור אינו ריק אף על פי ש-outbox ריק.
שכחה ש-peek זקוק לאותה העברה מחדש כמו pop. פעולת הצצה מיד אחרי פעולות הדחיפה הראשונות מגלה ש-outbox ריק.
שימוש בתור של ספרייה או קריאת תחתית המחסנית לפי אינדקס. המטרה היא לקבל סדר של תור באמצעות פעולות מחסנית בלבד.
החזרת מספרים או ערכים בוליאניים במקום טקסט. כל תשובה היא מחרוזת, כולל "null" עבור פעולת דחיפה.

שאלות נפוצות4

מהי סיבוכיות הזמן של תור שנבנה משתי מחסניות?

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

מה המשמעות של O(1) אמורטיבי כאן?

המשמעות היא שהעלות הממוצעת לכל פעולה לאורך כל הרצף היא קבועה, אף על פי שפעולה בודדת יכולה להיות איטית. פעולת שליפה ששופכת 1,000 פריטים ממומנת על ידי 1,000 פעולות הדחיפה הזולות שקדמו לה, כי הפריטים האלה לעולם לא יישפכו שוב. העלות של שום רצף הכולל n פעולות אינה עולה על בערך 4n צעדים של המחסנית.

למה צריך שתי מחסניות ולא אחת?

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

האם אפשר לממש מחסנית באמצעות תורים במקום זאת?

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

Python

def queueOps(ops, args):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

צפוי

["null", "null", "1", "1", "false"]