Python如何使用FIFO队列构建LIFO堆栈

Question

这里我有一个非常棘手的问题:如何使用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())

有朋友能帮忙吗？

Answer 1

因此，更好的解决方案是使用queue.LifoQueue()。但是，由于这是一种实践，下面的解决方案具有具有时间复杂性O(1)和pop函数时间复杂性O(N)的pop函数，这意味着它通过队列中的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