0

我在这里有一个非常棘手的问题：如何仅使用 FIFO 队列构建 LIFO 堆栈？

所以我已经有了大部分代码，但是如下所示，我不知道如何编写 pop函数

import queue

class MyLifo:
    def __init__(self):
        self.fifo = queue.Queue();
        self.fifoAux = queue.Queue();

    def isEmpty(self):
        return self.fifo.empty()
    
    def push(self, x):
        self.fifo.put(x)

    def pop(self):
        ### your code here.

### for testing the solution:

lifo = MyLifo()
i=0

while (i<30):
    lifo.push(i)
    i+=1

while (lifo.isEmpty() == False):
    print(lifo.pop())


 
lifo.push(3)
lifo.push(5)
print(lifo.pop())
lifo.push(30)
print(lifo.pop())
print(lifo.pop())
print(lifo.pop())

有朋友可以帮忙吗？

4

1 回答 1

1

所以更好的解决方案是使用queue.LifoQueue(). 但是，由于这是一种实践，因此以下解决方案具有push时间复杂度O(1)和pop函数时间复杂度的函数O(N)，这意味着它遍历N队列中的现有元素。

import queue


class MyLifo:
    def __init__(self):
        self.fifo = queue.Queue()

    def isEmpty(self):
        return self.fifo.empty()

    def push(self, x):
        self.fifo.put(x)

    def pop(self):
        for _ in range(len(self.fifo.queue) - 1):
            self.push(self.fifo.get())
        return self.fifo.get()

lifo = MyLifo()
i = 0

while (i < 30):
    lifo.push(i)
    i += 1

while (lifo.isEmpty() == False):
    print(lifo.pop(), end=" ")

输出：

29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
于 2022-02-25T23:43:47.517 回答