Implement Queue Using Stacks

+10

Hãy xây dựng một hàng đợi vào trước, ra trước chỉ dùng hai ngăn xếp để lưu trữ. Mỗi ngăn xếp chỉ có thể thêm một phần tử lên trên cùng, xóa phần tử trên cùng, đọc phần tử trên cùng và cho biết nó có rỗng hay không. Hàng đợi hỗ trợ push x (thêm x vào cuối hàng), pop (xóa và trả về phần tử ở đầu hàng), peek (trả về phần tử ở đầu hàng) và empty (hàng đợi có rỗng không?).

Bạn nhận được các thao tác theo thứ tự trong ops, với args[i] chứa giá trị cho thao tác push và 0 cho mọi thao tác khác. Thực hiện chúng trên một hàng đợi ban đầu rỗng và trả về một chuỗi cho mỗi thao tác: "null" cho thao tác push, số ở dạng văn bản cho thao tác pop hoặc peek, và "true" hoặc "false" cho thao tác empty.

Hàm

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

opsstring-array: các phép toán, theo thứ tự chúng được thực hiện
argsinteger-array: giá trị cho mỗi lần đẩy, 0 cho mọi thao tác khác
Trả vềstring-array: mỗi phép toán một đáp án, dưới dạng văn bản

Ràng buộc

1 ≤ ops.length ≤ 2000
args.length == ops.length
Mỗi ops[i] là push, pop, peek hoặc empty.
-10⁹ ≤ args[i] ≤ 10⁹ đối với thao tác push, và args[i] == 0 đối với mọi thao tác khác.
pop và peek chỉ được gọi khi hàng đợi có ít nhất một phần tử.

Ví dụ

Đầu vào: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Đầu ra: ["null", "null", "1", "1", "false"]
Giải thích: Sau khi đẩy 1 rồi đến 2 vào, phần đầu là 1, nên cả peek và pop đều trả về "1". Số 2 vẫn còn bên trong, nên empty trả về "false".

Đầu vào: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Đầu ra: ["null", "null", "4", "null", "7", "9", "true"]
Giải thích: Lần pop đầu tiên trả về 4, phần tử cũ nhất. 9 được thêm vào khi 7 vẫn đang chờ, và nó được lấy ra sau 7 vì nó được thêm vào sau 7. Sau đó, hàng đợi trống, nên câu trả lời cuối cùng là "true".

Đầu vào: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Đầu ra: ["true", "null", "-3", "-3", "true"]
Giải thích: Hàng đợi bắt đầu ở trạng thái rỗng, nên đáp án đầu tiên là "true". Một số âm được lưu như mọi số khác: peek và pop đều trả về "-3", sau đó hàng đợi lại rỗng.

Câu hỏi mở rộng

Làm thế nào để bạn thêm một thao tác back trả về phần tử mới nhất trong O(1), mà không làm phá vỡ giới hạn khấu hao của các thao tác khác?

Lời giải

Ngăn xếp trả về các phần tử theo thứ tự mới nhất trước, còn hàng đợi trả về theo thứ tự cũ nhất trước. Đổ một ngăn xếp sang ngăn xếp khác sẽ đảo ngược thứ tự, biến thứ tự của ngăn xếp thành thứ tự của hàng đợi. Câu hỏi là khi nào nên đổ: đổ sau mỗi thao tác sẽ tốn O(n) mỗi lần, còn chỉ đổ khi ngăn xếp thứ hai cạn thì mỗi phần tử chỉ được chuyển qua một lần.

Sắp xếp lại toàn bộ ngăn xếp sau mỗi lần thêm phần tử

Ý tưởng

Giữ tất cả phần tử trong một ngăn xếp, main, với phần tử cũ nhất ở trên cùng, để pop, peek và empty đều là thao tác đơn trên ngăn xếp. Khi thêm một phần tử, phải đặt phần tử mới ở dưới cùng: chuyển tất cả phần tử sang helper, thêm phần tử mới vào main đang trống, rồi chuyển tất cả phần tử trở lại. Hai lần đảo ngược sẽ khôi phục thứ tự, với phần tử mới nằm bên dưới.

Mỗi lần thêm, tất cả phần tử đã lưu được di chuyển hai lần. Thêm liên tiếp 1,000 phần tử sẽ tốn khoảng 2 × (0 + 1 + ... + 999), gần một triệu lần di chuyển.

Thuật toán

Duy trì hai ngăn xếp, main có phần tử cũ nhất ở trên cùng và helper rỗng.
Với push x: lấy từng phần tử khỏi main và chuyển sang helper, đẩy x vào main, rồi lấy từng phần tử khỏi helper và chuyển lại vào main.
Với pop và peek: lấy hoặc đọc phần tử trên cùng của main.
Với empty: cho biết main có rỗng hay không.

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

Các ngăn xếp đầu vào và đầu ra với thao tác chuyển dữ liệu trì hoãn

Ý tưởng

Giao cho mỗi ngăn xếp một nhiệm vụ riêng. Các thao tác thêm phần tử đưa phần tử vào inbox. Các thao tác lấy và xem phần tử đọc từ outbox, ngăn xếp này luôn có phần tử cũ nhất ở trên cùng. Khi outbox trống, đổ toàn bộ inbox vào đó: phần tử mới nhất rời inbox trước và nằm ở đáy, vì vậy phần tử cũ nhất nằm trên cùng.

Chỉ đổ khi outbox trống. Khi ngăn xếp này còn phần tử, chúng cũ hơn mọi thứ trong inbox và phải rời đi trước. Trong ví dụ thứ hai, 4 và 7 được đổ sang để thực hiện thao tác lấy đầu tiên, còn 9 chờ trong inbox cho đến khi 7 rời đi.

Mỗi giá trị được thêm vào inbox một lần, chuyển sang outbox một lần và lấy ra một lần, vì vậy tổng chi phí của n thao tác là O(n).

Thuật toán

Giữ hai ngăn xếp trống, inbox và outbox.
Với push x: đẩy x vào inbox.
Với pop hoặc peek: nếu outbox trống, lấy từng phần tử khỏi inbox và đẩy vào outbox. Sau đó lấy ra hoặc đọc phần tử trên cùng của outbox.
Với empty: cho biết cả hai ngăn xếp có trống hay không.

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

Lỗi thường gặp và trường hợp biên

Lấy phần tử ra khi outbox vẫn còn phần tử. Phần tử mới nằm trên phần tử cũ và được lấy ra trước: trong ví dụ thứ hai, 9 sẽ được lấy ra trước 7.
Báo empty chỉ dựa vào outbox. Ngay sau khi thêm phần tử, phần tử nằm trong inbox, nên hàng đợi không rỗng.
Chuyển phần tử sang outbox khi gọi pop nhưng không chuyển khi gọi peek. Trong ví dụ đầu tiên, thao tác peek sau hai lần thêm phần tử sẽ thấy outbox rỗng.
Trả về số hoặc giá trị boolean. Mọi câu trả lời đều là chuỗi, bao gồm cả "null" khi thêm phần tử.

Câu hỏi thường gặp3

Độ phức tạp thời gian của hàng đợi được xây dựng từ hai ngăn xếp là bao nhiêu?

Thao tác đẩy có độ phức tạp O(1), còn thao tác lấy ra và xem phần tử trên cùng có độ phức tạp O(1) tính trung bình. Một lần gọi có thể chuyển tất cả phần tử sang bên kia, nhưng chi phí chuyển đã được bù bằng các thao tác đẩy trước đó, vì mỗi phần tử chỉ được chuyển một lần. Với n thao tác bất kỳ, cần nhiều nhất khoảng 4n bước trên ngăn xếp, và độ phức tạp không gian là O(n).

Tại sao bạn cần hai ngăn xếp thay vì một?

Một ngăn xếp chỉ cho phép truy cập phần tử mới nhất, còn hàng đợi cần phần tử cũ nhất. Muốn lấy phần tử ở đáy, bạn phải bỏ hết các phần tử phía trên, và cần có chỗ để tạm chứa chúng: ngăn xếp thứ hai. Chuyển chúng sang đó sẽ đảo ngược thứ tự, biến thứ tự mới nhất trước thành cũ nhất trước.

Bạn có thể triển khai ngăn xếp bằng hàng đợi thay vì dùng ngăn xếp không?

Có, nhưng không tiết kiệm được chi phí trung bình. Với một hàng đợi, sau khi thêm phần tử mới, hãy lấy từng phần tử cũ từ đầu hàng đợi rồi thêm vào cuối, để phần tử mới nằm ở đầu. Thao tác push có độ phức tạp O(n), còn pop có độ phức tạp O(1).

def queueOps(ops, args):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

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