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: القيمة لكل عملية دفع، و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 الفارغ، وانقل كل شيء مجددًا. كل عملية نقل تعكس الترتيب، وعملتا نقل تعيدان الترتيب كما كان، فينتهي العنصر الجديد في الأسفل.

هذا صحيح، لكن كل عملية إضافة تلامس كل عنصر مخزّن مرتين. إضافة 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.
الإبلاغ عن أن outbox وحده empty. مباشرةً بعد عملية دفع، يستقر العنصر الجديد في inbox، لذا فالطابور ليس فارغًا رغم أن outbox فارغ.
نسيان أن peek يحتاج إلى إعادة الملء نفسها التي تحتاج إليها pop. فعملية معاينة مباشرةً بعد أول عمليات الدفع تجد outbox فارغًا.
استخدام طابور من مكتبة أو قراءة أسفل المكدس باستخدام فهرس. الهدف هو الحصول على ترتيب الطابور باستخدام عمليات المكدس فقط.
إرجاع أعداد أو قيم منطقية بدلًا من نص. كل إجابة عبارة عن سلسلة نصية، بما في ذلك "null" لعملية الدفع.

أسئلة شائعة4

ما التعقيد الزمني لطابور مُنشأ باستخدام مكدسين؟

تستغرق عملية Push زمنًا من الرتبة O(1). وتستغرق عمليتا Pop وpeek زمنًا من الرتبة 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"]